Three utilities problem
The classical mathematical puzzle known as the three utilities problem. Without using a third dimension or sending any of the connections through another company or cottage, is there a way to make all nine connections without any of the lines crossing each other? The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation, it is part of the mathematical field of topological graph theory which studies the embedding of graphs on surfaces. In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph K3,3 is planar; this graph is referred to as the utility graph in reference to the problem. A review of the history of the three utilities problem is given by Kullman, he states that most published references to the problem characterize it as "very ancient". In the earliest publication found by Kullman, Henry Dudeney names it "water and electricity". However, Dudeney states that the problem is "as old as the hills...much older than electric lighting, or gas".
Dudeney published the same puzzle in The Strand Magazine in 1913. Another early version of the problem involves connecting three houses to three wells, it is stated to a different puzzle that involves three houses and three fountains, with all three fountains and one house touching a rectangular wall. Mathematically, the problem can be formulated in terms of graph drawings of the complete bipartite graph K3,3; this graph makes an early appearance in Henneberg. It has six vertices, split into two subsets of three vertices, nine edges, one for each of the nine ways of pairing a vertex from one subset with a vertex from the other subset; the three utilities problem is the question of. As it is presented, the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other. In other words, the graph K3,3 is not planar. Kazimierz Kuratowski stated in 1930 that K3,3 is nonplanar, from which it follows that the problem has no solution. Kullman, states that "Interestingly enough, Kuratowski did not publish a detailed proof that non-planar".
One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem. In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding. Alternatively, it is possible to show that any bridgeless bipartite planar graph with V vertices and E edges has E ≤ 2V − 4 by combining the Euler formula V − E + F = 2 with the observation that the number of faces is at most half the number of edges. In the utility graph, E = 9 and 2V − 4 = 8, violating this inequality, so the utility graph cannot be planar. Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are the graphs that contain neither K3,3 nor the complete graph K5 as a subdivision, Wagner's theorem that the planar graphs are the graphs that contain neither K3,3 nor K5 as a minor, make use of and generalize the non-planarity of K3,3.
K3,3 is a toroidal graph. In terms of the three cottage problem this means the problem can be solved by punching two holes through the plane and connecting them with a tube; this changes the topological properties of the surface and using the tube allows the three cottages to be connected without crossing lines. An equivalent statement is that the graph genus of the utility graph is one, therefore it cannot be embedded in a surface of genus less than one. A surface of genus one is equivalent to a torus. A toroidal embedding of K3,3 may be obtained by replacing the crossing by a tube, as described above, in which the two holes where the tube connects to the plane are placed along one of the crossing edges on either side of the crossing. Another way of changing the rules of the puzzle is to allow utility lines to pass through the cottages or utilities. Pál Turán's "brick factory problem" asks more for a formula for the minimum number of crossings in a drawing of the complete bipartite graph Ka,b in terms of the numbers of vertices a and b on the two sides of the bipartition.
The utility graph K3,3 may be drawn with only one crossing, but not with zero crossings, so its crossing number is one. The utility graph K3,3 is a circulant graph, it is the smallest triangle-free cubic graph. Like all other complete bipartite graphs, it is a well-covered graph, meaning that every maximal independent set has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, they are equal. K3,3 is one of only seven 3-regular 3-connected well-covered graphs, it is a Laman graph, meaning that it forms a minimally rigid system when it is embedded in the plane. It is the smallest example of a nonplanar
Kazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. Kazimierz Kuratowski was born in Warsaw, Vistula Land, on 2 February 1896, into an assimilated Jewish family, he was a son of Marek Kuratow, a barrister, Róża Karzewska. He completed a Warsaw secondary school, named after general Paweł Chrzanowski. In 1913, he enrolled in an engineering course at the University of Glasgow in Scotland, in part because he did not wish to study in Russian, he completed only one year of study when the outbreak of World War I precluded any further enrollment. In 1915, Russian forces withdrew from Warsaw and Warsaw University was reopened with Polish as the language of instruction. Kuratowski restarted his university education there the same year, this time in mathematics, he obtained his Ph. D. in 1921, in newly independent Poland. In autumn 1921 Kuratowski was awarded the Ph. D. degree for his groundbreaking work. His thesis statement consisted of two parts.
One was devoted to an axiomatic construction of topology via the closure axioms. This first part has been cited in hundreds of scientific articles; the second part of Kuratowski's thesis was devoted to continua irreducible between two points. This was the subject of a French doctoral thesis written by Zygmunt Janiszewski. Since Janiszewski was deceased, Kuratowski's supervisor was Stefan Mazurkiewicz. Kuratowski's thesis solved certain problems in set theory raised by a Belgian mathematician, Charles-Jean Étienne Gustave Nicolas, Baron de la Vallée Poussin. Two years in 1923, Kuratowski was appointed deputy professor of mathematics at Warsaw University, he was appointed a full professor of mathematics at Lwów Polytechnic in Lwów, in 1927. He was the head of the Mathematics department there until 1933. Kuratowski was dean of the department twice. In 1929, Kuratowski became a member of the Warsaw Scientific Society While Kuratowski associated with many of the scholars of the Lwów School of Mathematics, such as Stefan Banach and Stanislaw Ulam, the circle of mathematicians based around the Scottish Café he kept close connections with Warsaw.
Kuratowski left Lwów for Warsaw in 1934, before the famous Scottish Book was begun, hence did not contribute any problems to it. He did however, collaborate with Banach in solving important problems in measure theory. In 1934 he was appointed the professor at Warsaw University. A year Kuratowski was nominated as the head of Mathematics Department there. From 1936 to 1939 he was secretary of the Mathematics Committee in The Council of Science and Applied Sciences. During World War II, he gave lectures at the underground university in Warsaw, since higher education for Poles was forbidden under German occupation. In February 1945, Kuratowski started to lecture at the reopened Warsaw University. In 1945, he became a member of the Polish Academy of Learning, in 1946 he was appointed vice-president of the Mathematics department at Warsaw University, from 1949 he was chosen to be the vice-president of Warsaw Scientific Society. In 1952 he became a member of the Polish Academy of Sciences, of which he was the vice-president from 1957 to 1968.
After World War II, Kuratowski was involved in the rebuilding of scientific life in Poland. He helped to establish the State Mathematical Institute, incorporated into the Polish Academy of Sciences in 1952. From 1948 until 1967 Kuratowski was director of the Institute of Mathematics of the Polish Academy of Sciences, was a long-time chairman of the Polish and International Mathematics Societies, he was president of the Scientific Council of the State Institute of Mathematics. From 1948 to 1980 he was the head of the topology section. One of his students was Andrzej Mostowski. Kazimierz Kuratowski was one of a celebrated group of Polish mathematicians who would meet at Lwów's Scottish Café, he was a member of the Warsaw Scientific Society. What is more, he was chief editor in "Fundamenta Mathematicae", a series of publications in "Polish Mathematical Society Annals". Furthermore, Kuratowski worked as an editor in the Polish Academy of Sciences Bulletin, he was one of the writers of the Mathematical monographs, which were created in cooperation with the Institute of Mathematics of the Polish Academy of Sciences.
High quality research monographs of the representatives of Warsaw's and Lwów’s School of Mathematics, which concerned all areas of pure and applied mathematics, were published in these volumes. Kazimierz Kuratowski was an active member of many scientific societies and foreign scientific academies, including the Royal Society of Edinburgh, Germany, Hungary and the Union of Soviet Socialist Republics. In 1981, IMPAN, the Polish Mathematical Society, Kuratowski's daughter Zofia Kuratowska established a prize in his name for achievements in mathematics to people under the age of 30 years; the prize is considered the most prestigious of awards for young Polish mathematicians. Kuratowski’s research focused on abstract topological and metric structures, he implemented the closure axioms. This was fundamental for the development of topological space theory and irreducible continuum theory between two points; the most valuable results, which were obtained by Kazimierz K
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3; the Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs, preserved by deletions and edge contractions. For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time. Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors.
An edge contraction is an operation which removes an edge from a graph while merging the two vertices it used to connect. An undirected graph H is a minor of another undirected graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, deleting some isolated vertices; the order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H. Graph minors are studied in the more general context of matroid minors. In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed; this point of view has the advantage that edge deletions leave the rank of a graph unchanged, edge contractions always reduce the rank by one. In other contexts it makes more sense to allow the deletion of a cut-edge, to allow disconnected graphs, but to forbid multigraphs. In this variation of graph minor theory, a graph is always simplified after any edge contraction to eliminate its self-loops and multiple edges.
A function f is referred to as "minor-monotone". In the following example, graph H is a minor of graph G: H. G; the following diagram illustrates this. First construct a subgraph of G by deleting the dashed edges, contract the gray edge: It is straightforward to verify that the graph minor relation forms a partial order on the isomorphism classes of undirected graphs: it is transitive, G and H can only be minors of each other if they are isomorphic because any nontrivial minor operation removes edges or vertices. A deep result by Neil Robertson and Paul Seymour states that this partial order is a well-quasi-ordering: if an infinite list G1, G2... of finite graphs is given there always exist two indices i < j such that Gi is a minor of Gj. Another equivalent way of stating this is that any set of graphs can have only a finite number of minimal elements under the minor ordering; this result proved a conjecture known as Wagner's conjecture, after Klaus Wagner. In the course of their proof and Robertson prove the graph structure theorem in which they determine, for any fixed graph H, the rough structure of any graph which does not have H as a minor.
The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a clique-sum of smaller graphs that are modified in small ways from graphs embedded on surfaces of bounded genus. Thus, their theory establishes fundamental connections between graph minors and topological embeddings of graphs. For any graph H, the simple H-minor-free graphs must be sparse, which means that the number of edges is less than some constant multiple of the number of vertices. More if H has h vertices a simple n-vertex simple H-minor-free graph can have at most O edges, some Kh-minor-free graphs have at least this many edges. Thus, if H has h vertices H-minor-free graphs have average degree O and furthermore degeneracy O. Additionally, the H-minor-free graphs have a separator theorem similar to the planar separator theorem for planar graphs: for any fixed H, any n-vertex H-minor-free graph G, it is possible to find a subset of O vertices whose removal splits G into two subgraphs with at most 2n/3 vertices per subgraph.
Stronger, for any fixed H, H-minor-free graphs have treewidth O. The Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on k vertices G has a proper coloring with k − 1 colors
Not to be confused with László M. Lovász, a different combinatorial mathematician who works with Jacob Fox. László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, the Kyoto Prize in 2010, he is the current president of the Hungarian Academy of Sciences. He served as president of the International Mathematical Union between January 1, 2007 and December 31, 2010. Lovász was born on March 1948 in the city of Budapest, his father was a surgeon. When Lovász was 14 he found a mathematical article written by Paul Erdős. One year he became acquainted with Erdős, they talked about mathematics and other subjects. This experience inspired Lovász in searching for more knowledge. In high school, Lovász won gold medals at the International Mathematical Olympiad. Lovász received his Candidate of Sciences degree in 1970 at the Hungarian Academy of Sciences, his advisor was Tibor Gallai. Until 1975, Lovász worked at Eötvös Loránd University, between 1975–1982, he led the Department of Geometry at the University of Szeged.
In 1982, he returned to the Eötvös University. The former and current scientists of the department include György Elekes, András Frank, József Beck, Éva Tardos, András Hajnal, Lajos Pósa, Miklós Simonovits, Tamás Szőnyi. Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006, he returned to Eötvös Loránd University, where he was the director of the Mathematical Institute. In 2014 he was elected the President of the Hungarian Academy of Sciences. Lovász is married to Katalin Vesztergombi. Lovász was awarded the Brouwer Medal in 1993, the Wolf Prize in 1999, the Bolyai prize in 2007 and Hungary's Széchenyi Grand Prize, he received the Advanced Grant of the European Research Council. He was elected foreign member of the Royal Netherlands Academy of Arts and Sciences and Royal Swedish Academy of Sciences, honorary member of the London Mathematical Society, he received the Kyoto Prize for Basic Science. In 2012 he became a fellow of the American Mathematical Society.
Lovász is listed as an ISI cited researcher. Topological combinatorics Lovász conjecture Erdős–Faber–Lovász conjecture Lovász local lemma Lenstra–Lenstra–Lovász lattice basis reduction algorithm Geometry of numbers Perfect graph theorem Greedoid Bell number Lovász number Graph limit Lovász's Homepage László Lovász at the Mathematics Genealogy Project "László Lovász's results". International Mathematical Olympiad
Paul Seymour (mathematician)
Paul Seymour is a professor at Princeton University. His research interest is in discrete mathematics graph theory, he was responsible for important progress on regular matroids and unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs. Many of his recent papers are available from his website, he won a Sloan Fellowship in 1983, the Ostrowski Prize in 2004. He received an honorary doctorate from the University of Waterloo in 2008 and one from the Technical University of Denmark in 2013. Seymour was born in Plymouth, England, he was a day student at Plymouth College, studied at Exeter College, gaining a BA degree in 1971, D. Phil in 1975. From 1974–1976 he was a college research fellow at University College of Swansea, returned to Oxford for 1976–1980 as a Junior Research Fellow at Merton College, with the year 1978–79 at University of Waterloo, he became an associate and a full professor at Ohio State University, Ohio, between 1980 and 1983, where he began research with Neil Robertson, a fruitful collaboration that continued for many years.
From 1983 until 1996, he was at Bellcore, New Jersey. He was an adjunct professor at Rutgers University from 1984–1987 and at the University of Waterloo from 1988–1993, he became professor at Princeton University in 1996. He is Editor-in-Chief for the Journal of Graph Theory, he married Shelley MacDonald of Ottawa in 1979, they have two children and Emily. The couple separated amicably in 2007, his brother Leonard W. Seymour is Professor of gene therapy at Oxford University. Combinatorics in Oxford in the 1970s was dominated by matroid theory, due to the influence of Dominic Welsh and Aubrey William Ingleton. Much of Seymour's early work, up to about 1980, was on matroid theory, included three important matroid results: his D. Phil. Thesis on matroids with the max-flow min-cut property. There were several other significant papers from this period: a paper with Welsh on the critical probabilities for bond percolation on the square lattice. In 1980 he moved to Ohio State University, began work with Neil Robertson.
This led to Seymour's most important accomplishment, the so-called "Graph Minors Project", a series of 23 papers, published over the next thirty years, with several significant results: the graph minors structure theorem, that for any fixed graph, all graphs that do not contain it as a minor can be built from graphs that are of bounded genus by piecing them together at small cutsets in a tree structure. In about 1990 Robin Thomas began to work with Seymour, their collaboration resulted in several important joint papers over the next ten years: a proof of a conjecture of Sachs, characterizing by excluded minors the graphs that admit linkless embeddings in 3-space. In 2000 the trio were supported by the American Institute of Mathematics to work on the strong perfect graph conjecture, a famous open question, raised by Claude Berge in the early 1960s. Seymour's student Maria Chudnovsky joined them in 2001, in 2002 the four jointly proved the conjecture. Seymour continued to work with Chudnovsky, obtained several more results about induced subgraphs, in particular a polynomial-time algorithm to test whether a graph is perfect, a general description of all claw-free graphs
U. S. R. Murty
Uppaluri Siva Ramachandra Murty, or U. S. R. Murty, is a Professor Emeritus of the Department of Combinatorics and Optimization, University of Waterloo. U. S. R. Murty received his Ph. D. in 1967 from the Indian Statistical Institute, with a thesis on extremal graph theory. Murty is well known for his work in matroid theory and graph theory, for being a co-author with J. A. Bondy of a textbook on graph theory. Murty has served as a managing editor and co-editor-in-chief of the Journal of Combinatorial Theory, Series B. John Adrian Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland. Book's page at the University of Paris VI. John Adrian Bondy and U. A. R. Murty, "Graph Theory and Related Topics." Academic Press Inc. ISBN 978-0121143503. U. S. R. Murty How Many Magic Configurations are There? The American Mathematical Monthly. U. S. R. Murty Equicardinal matroids. Journal of Combinatorial Theory, Series B U. S. R. Murty Matroids with Sylvester property. Aequationes Mathematicae. Murty, U. S. R.
"On some extremal graphs", Acta Mathematica Academiae Scientiarum Hungaricae, 19: 69–74, doi:10.1007/BF01894681, MR 0224509 de Carvalho, Marcelo H.. "On a conjecture of Lovász concerning bricks. II. Bricks of finite characteristic", Journal of Combinatorial Theory, Series B, 85: 137–180, doi:10.1006/jctb.2001.2092, MR 1900684
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography and bioinformatics. A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph; this drawing should not be confused with the graph itself: different layouts can correspond to the same graph. In the abstract, all that matters is. In the concrete, the arrangement of these vertices and edges within a drawing affects its understandability, fabrication cost, aesthetics; the problem gets worse if the graph changes over time by adding and deleting edges and the goal is to preserve the user's mental map. Graphs are drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as line segments, polylines, or curves in the Euclidean plane.
Node–link diagrams can be traced back to the 13th century work of Ramon Llull, who drew diagrams of this type for complete graphs in order to analyze all pairwise combinations among sets of metaphysical concepts. In the case of directed graphs, arrowheads form a used graphical convention to show their orientation. Upward planar drawing uses the convention that every edge is oriented from a lower vertex to a higher vertex, making arrowheads unnecessary. Alternative conventions to node–link diagrams include adjacency representations such as circle packings, in which vertices are represented by disjoint regions in the plane and edges are represented by adjacencies between regions. Many different quality measures have been defined for graph drawings, in an attempt to find objective means of evaluating their aesthetics and usability. In addition to guiding the choice between different layout methods for the same graph, some layout methods attempt to directly optimize these measures; the crossing number of a drawing is the number of pairs of edges.
If the graph is planar it is convenient to draw it without any edge intersections. However, nonplanar graphs arise in applications, so graph drawing algorithms must allow for edge crossings; the area of a drawing is the size of its smallest bounding box, relative to the closest distance between any two vertices. Drawings with smaller area are preferable to those with larger area, because they allow the features of the drawing to be shown at greater size and therefore more legibly; the aspect ratio of the bounding box may be important. Symmetry display is the problem of finding symmetry groups within a given graph, finding a drawing that displays as much of the symmetry as possible; some layout methods automatically lead to symmetric drawings. It is important that edges have shapes that are as simple as possible, to make it easier for the eye to follow them. In polyline drawings, the complexity of an edge may be measured by its number of bends, many methods aim to provide drawings with few total bends or few bends per edge.
For spline curves the complexity of an edge may be measured by the number of control points on the edge. Several used quality measures concern lengths of edges: it is desirable to minimize the total length of the edges as well as the maximum length of any edge. Additionally, it may be preferable for the lengths of edges to be uniform rather than varied. Angular resolution is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high degree it will have small angular resolution, but the angular resolution can be bounded below by a function of the degree; the slope number of a graph is the minimum number of distinct edge slopes needed in a drawing with straight line segment edges. Cubic graphs have slope number at most four, but graphs of degree five may have unbounded slope number. There are many different graph layout strategies: In force-based layout systems, the graph drawing software modifies an initial vertex placement by continuously moving the vertices according to a system of forces based on physical metaphors related to systems of springs or molecular mechanics.
These systems combine attractive forces between adjacent vertices with repulsive forces between all pairs of vertices, in order to seek a layout in which edge lengths are small while vertices are well-separated. These systems may perform gradient descent based minimization of an energy function, or they may translate the forces directly into velocities or accelerations for the moving vertices. Spectral layout methods use as coordinates the eigenvectors of a matrix such as the Laplacian derived from the adjacency matrix of t