Who Would Have Thought It? and Bipartite dimension: Difference between pages

Content deleted Content added

Inline

Revision as of 20:55, 10 October 2008

In the mathematical field of graph theory, the bipartite dimension of an graph G=(V,E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).

Bipartite dimension of some special graphs

Fishburn and Hammer determine the bipartite dimension for some special graphs. For example, the path $P_{n}$ has $d(P_{n})=\lfloor n/2\rfloor$ , the cycle $C_{n}$ has $d(C_{n})=\lceil n/2\rceil$ , and the complete graph $K_{n}$ has $d(K_{n})=\lceil \log n\rceil$ .

Computational complexity

Determining d(G) is an optimization problem. The decision problem for bipartite dimension can be phrased as:

INSTANCE: A graph

G=(V,E)

and a positive integer

k

.

QUESTION: Does G admit a biclique edge cover containing at most

k

bicliques?

This problem is NP-complete, even for bipartite graphs, as proved by Orlin. It appears as problem GT18 in Garey and Johnson's classical book on NP-completeness. This decision problem is a rather straightforward reformulation of another decision problem on families of finite sets, the set basis problem, proved to be NP-complete earlier by Stockmeyer, and appearing as problem SP7 in Garey and Johnson's book.

INSTANCE: A collection of finite sets

S_{1},\ldots ,S_{n}

and a positive integer

k

.

QUESTION: Can we choose at most

k

subsets such that their union equals

\bigcup _{i=1}^{n}S_{i}

, the union of all

S_{i}

?

References

P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degrees of graphs. Discrete Mathematics, 160:127-148, 1996
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
S. Monson, N. Pullman, and R. Rees: A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bulletin of the ICA, vol 14, pp. 17--86, 1995.
J. Orlin. Contentment in Graph Theory: Covering Graphs with Cliques. Indagationes Mathematicae, 80:406–424, 1977.
Larry J. Stockmeyer. The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975.

External Links

blog entry about bipartite dimension by David Eppstein

@@ Line 1: / Line 1: @@
+In the mathematical field of [[graph theory]], the '''bipartite dimension''' of an [[graph]] G=(V,E) is the minimum number of [[biclique]]s, that is, complete bipartite subgraphs, needed to [[covering (graph theory)|cover]] all edges in E. A collection of bicliques covering all edges in G is called a '''biclique edge cover''', or sometimes '''biclique cover'''. The bipartite dimension of G is often denoted by the symbol d(G).
-{{Plot}}
+==Bipartite dimension of some special graphs==
-'''''Who Would Have Thought It?''''' is a novel written by [[María Ruiz de Burton]] and published in 1872.
+Fishburn and Hammer determine the bipartite dimension for some special graphs. For example, the path <math>P_n</math>
+has <math>d(P_n) = \lfloor n/2 \rfloor</math>, the cycle <math>C_n</math> has <math>d(C_n)=\lceil n/2\rceil</math>,
+and the complete graph <math>K_n</math> has <math>d(K_n) = \lceil\log n \rceil</math>.
+==Computational complexity==
-This novel was the first to be written in English by a Mexican living in the United States.<ref>{{Harvnb|Rivera|2006|p= 82}}</ref> It details the struggles of a Mexican-born girl, Lola, in an American society obsessed with class, money, race, gender, and religion.
+Determining d(G) is an [[optimization problem]]. The [[decision problem]] for bipartite dimension can be phrased as:
+:INSTANCE: A graph <math>G=(V,E)</math> and a positive integer <math>k</math>.
-According to critics Rosaura Sánchez and Beatrice Pita, in the novel "Ruiz de Burton carries out an aggressive demystification of a series of national foundational ideologies.  By variously deploying allegory, satire and parody, the author effects a critique driven by a perceived crisis in the body politic of the United States itself."<ref>{{Harvnb|Sánchez|Pita|1995|p= viii}}</ref>
+:QUESTION: Does G admit a biclique edge cover containing at most <math>k</math> bicliques?
+This problem is [[NP-complete]], even for [[bipartite graph]]s, as proved by Orlin. It appears as problem '''GT18''' in
-== Critical History==
+Garey and Johnson's classical book on NP-completeness. This decision problem is a rather straightforward reformulation of
+another decision problem on families of finite sets, the ''set basis problem'', proved
+to be NP-complete earlier by Stockmeyer, and appearing as problem '''SP7''' in Garey and Johnson's book.
+:INSTANCE: A collection of finite sets <math>S_1,\ldots,S_n</math> and a positive integer <math>k</math>.
-''Who Would Have Thought It?'' was published in 1872 anonymously by María Ruiz de Burton. One of the author's hesitations in revealing her name came from an anxiety that readers would be prejudiced towards her work. Rosaura Sánchez and Beatrice Pita note that "Ruiz de Burton was concerned that readers knowing that English was not her native language would be more inclined perhaps to find fault with the text".<ref>{{Harvnb|Sánchez|Pita|1995|p= vi}}</ref> It is critical that Ruiz de Burton's novel be read in the context of the American Civil war, a time of "dramatic economic, political and social changes to the United States" <ref>{{Harvnb|Sánchez|Pita|1995|p= viii}}</ref> As a native of Baja California who moved to Alta California in 1847, Ruiz de Burton's background allowed her to incorporate several insights and different points of view in her novel.
+:QUESTION: Can we choose at most <math>k</math> subsets such that their union equals <math>\bigcup_{i=1}^n S_i</math>, the union of all <math>S_i</math>?
+<!-- too technical?
-== Period ==
+To transform a bipartite graph <math>G=(U,V,E)</math> into an instance of the latter problem, simply take
-The story is intimately connected to the displacement of borders.{{fact}} The territorial boundaries are constantly negotiated. The civil war was ongoing and the nation was splitting apart. People were removing themselves from the nation in the hopes of establishing independence. Ruiz de Burton found herself greatly involved. "In 1849, one year after the signing of the Treaty of Guadalupe Hildago, she married Colonel Henry S. Burton, who was sent to Baja California to quell a Mexican uprising".<ref>{{Harvnb|Rivera|2006|p= 83}}</ref>
+<math>U = \bigcup_{i=1}^n S_i</math>, <math>V=\{S_1,\ldots, S_n\}</math>,
+and <math> \{\{u,S_i\} \mid u \in S_i\}</math> as edge set. The converse direction is similar.
-==Plot summary==
+-->
-The novel begins in the middle of a conversation between the Reverend Mr. Hackwell and his crony the Reverend Mr. Hammerhard as they make their way to the railroad depot of a small New England town. During their conversation the two men show themselves to have some rather questionable attributes though they are the so-called "Reverends" of the town. For example, at one point Mr. Hammerhard says, in reference to their desire to replace their decrepit wagon, "All the rich people of our town belong to your congregation--all the rich and good. Make them shell out, Hack. You are the fashion".<ref>{{harvnb|Ruiz de Burton|1995|p= 10}}</ref> As they continue on their way to the depot where they are to meet Dr. Norval--who they insinuate is thought of as a "social delinquent" by the people of the town--we are introduced to Mrs. Cackle, to Mrs. Norval, and to several other characters. We learn much about Mrs. Cackle through the leisurely and derisive conversation of the Reverends. Mr. Hackwell quotes her as saying, "'To me they are all alike--Indians, Mexicans, or Californians--they are all horrid. But my son Beau says that our just laws and smart lawyers will soon "''freeze them out''".<ref>{{harvnb|Ruiz de Burton|1995|p= 11}}</ref> She is portrayed as ignorantly jingoistic and bigoted.
-Dr. Norval is returning from a trip to the Southwest of the United States. From the railroad depot he rides to his house in a separate wagon, loaded with large boxes, following the Reverends. The first thing that Mrs. Norval, her daughters, and the other women notice is a figure wrapped in a red shawl who is in the arms of the doctor. Mrs. Norval originally imagines that it the figure is a tall woman and feels jealous that this is how her husband has returned home after fours years of being away. As Dr. Norval carries the figure to the house the shawl falls off and the women see that it is a little girl who appears to be black. Mrs. Norval is immediately even more astonished and disgusted. She and everyone else other than Dr. Norval begin commenting on her "blackness," making many bigoted remarks. Because of certain characteristics noted by the Reverends and women--such as the whiteness of her palms and her "red and prettily-cut lips"--they believe she must be some sort of mix of "Indian and negro".<ref>{{harvnb|Ruiz de Burton|1995|pp= 15-20}}</ref> These comments only further reflect their notions of race and the depth of their prejudice. Mrs. Norval seems especially disturbed by the little girl's blackness and treats her grudgingly and coldly. For some reason Dr. Norval has withheld from the group the little girl's name, her background, why she is with him, and that she speaks English. At dinner he finally hints to them that she has understood everything they have been saying, and they discover that her name is María Dolores Medina, though she goes by Lola or Lolita.<ref>{{harvnb|Ruiz de Burton|1995|p= 21}}</ref> Yet, Dr. Norval reveals ironically that Mrs. Norval is a strict adherent and admirer of the teachings of the famous abolitionists of the day, while he is a Democrat who "doesn't believe in Sambo but believe[s] in Christian charity and human mercy".<ref>{{harvnb|Ruiz de Burton|1995|p= 18}}</ref> This is one of the first moments in the novel in which irony reflects the hypocrisy of many of the "good" characters. Ruiz de Burton portrays every character but Dr. Norval in this moral New England town as being racist to at least some degree. . Also, it is here that we discover why Dr. Norval is considered to be a "social delinquent" in the words of the Reverends: he is a Democrat with supposed Southern sympathies at a time in which there was increasing tension between the North and the South. This made him party to the South's support of slavery in their minds, though as we later learn he was the only person in the town to aid black people who went from house to house looking for help.
-Lola's treatment continues as before with only Mattie (the Norvals' youngest daughter) and Lavinia (Mrs. Norval's sister) treating her with any kindness and the doctor protecting her from Mrs. Norval's abuse as much as possible. Matters change course quite suddenly when it is revealed by Dr. Norval to his wife that Lola is rich, the heir of an enormous fortune, and that she is from an aristocratic Mexican family. Lola's mother gave the doctor guardianship of Lola before she died. She had been a prisoner to a tribe of Native Americans in the Southwest after being captured by them while pregnant with Lola. She had Lola as a captive and collected a fortune over the years after discovering large amount of gold and precious gems. It was these that filled the large boxes loaded on the wagon Dr. Norval rode from the railroad depot. After the doctor has told this to Mrs. Norval she is already scheming up ways to keep Lola with them and to get her money.
-==Characters==
-*Dr. Norval
-*Mrs. Norval
-*Reverend Hackwell
-*Julian
-*Lola- For the first ten years of her life, Lola and her mother lived in captivity. The Indians insisted they be painted with a special dye that would change the color of their skin from white to black. Their skin mimicked their captors. When she moved to New England, the dye eventually faded and her skin soon resembled the Norvals. She seems to constantly adapt yet never really fits in. "... she undergoes numerous changes in racial status which overlap and effectively generate her simultaneous acquisition of material wealth and cultural capital. Yet, as Lola racially changes, so too does the economic position that the Norvals hold in New England culture, metaphorically representing how Anglo America and the northern United States economically prospered economically from Mexican lands after the treaty."<ref>{{Harvnb|Rivera|2006|p= 91}}</ref> Although Lola is the rightful heir to the gold and jewels, she never controls her fortune. The Norvals provide her with a comfortable lifestyle yet deprive her of the luxuries that her fortune has supplied the family. Despite being the financer of the Norval family, she is never fully accepted. Lola is the example of a mestizo position where she is neither in or out. Even with her immense fortune, her money is unable to buy her acceptance. Lola searches for her identity, through the pursuit of the letter, but we are unable to see to where and to whom she belongs to.
-*Lavinia
-*Emma Hackwell
-*Cackles
-==Allusions==
-*Renaissance Period:
-==Virtues of the book==
-'''Class'''
-'''Race'''
-'''Money'''
-'''Social Status'''
-'''Gender'''
-* Feminist novel?
-'''Religion'''
-==Technical Devices==
-'''Irony'''
-'''Satire'''
-'''Allegory'''
-'''Anonymity
-==Criticism==
-==Publication History==
-==Notes==
-{{reflist|2}}
 ==References==
+* P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degrees of graphs. ''Discrete Mathematics'', 160:127-148, 1996
+* M. R. Garey and D. S. Johnson. ''[[Computers and Intractability: A Guide to the Theory of NP-Completeness]]''. Freeman, 1979.
+* S. Monson, N. Pullman, and R. Rees: A survey of clique and biclique coverings and factorizations of (0,1)-matrices. ''Bulletin of the ICA'', vol 14, pp. 17--86, 1995.
+* J. Orlin. Contentment in Graph Theory: Covering Graphs with Cliques. ''Indagationes Mathematicae'', 80:406–424, 1977.
+* Larry J. Stockmeyer. The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975.
-*{{citation|last= Rivera |first= John-Michael |title= The Emergence of Mexican America: Recovering Stories of Mexican Peoplehood in U.S. Culture |place= New York |publisher= New York University Press |year= 2006 |isbn= 978-0814775578 }}.
+==See also==
-*{{citation|last=Ruiz de Burton |first= María Amparo |title= Who Would Have Thought It? |editor1-last= Sánchez |editor1-first= Rosaura |editor2-first= Beatrice |editor2-last= Pita |place= Houston |publisher= Arte Público |year= 1995 |pages= vii-lxv |isbn= 978-1558850811 }}.
+[[List of NP-complete problems]]
-*{{citation|last1=Sánchez |first1=Rosaura |first2= Beatrice |last2= Pita |chapter= Introduction |title= Who Would Have Thought It? |place= Houston |publisher= Arte Público |year= 1995 |pages= vii-lxv |isbn= 978-1558850811 }}.
-[[Category:1872 novels]]
-[[Category:American novels]]
-[[Category:Hispanic American literature]]
+==External Links==
-{{19thC-novel-stub}}
+[http://11011110.livejournal.com/134829.html blog entry about bipartite dimension by David Eppstein]