Paul Erdős was a renowned Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century, he was known both for his eccentric lifestyle. He devoted his waking hours to mathematics into his years—indeed, his death came only hours after he solved a geometry problem at a conference in Warsaw. Erdős pursued and proposed problems in discrete mathematics, graph theory, number theory, mathematical analysis, approximation theory, set theory, probability theory. Much of his work centered around discrete mathematics, cracking many unsolved problems in the field, he championed and contributed to Ramsey theory, which studied the conditions in which order appears. Overall, his work leaned towards solving open problems, rather than developing or exploring new areas of mathematics. Erdős published around 1,500 mathematical papers during his lifetime, a figure that remains unsurpassed, he believed mathematics to be a social activity, living an itinerant lifestyle with the sole purpose of writing mathematical papers with other mathematicians.
Erdős's prolific output with co-authors prompted the creation of the Erdős number, the number of steps in the shortest path between a mathematician and Erdős in terms of co-authorships. Paul Erdős was born in Budapest, Austria-Hungary, on 26 March 1913, he was the only surviving child of Lajos Erdős. His two sisters, aged 3 and 5, both died of scarlet fever a few days, his parents were both Jewish mathematics teachers. His fascination with mathematics developed early—he was left home by himself because his father was held captive in Siberia as an Austro-Hungarian POW during 1914–1920, causing his mother to have to work long hours to support their household, he taught himself to read through mathematics texts. By the age of four, given a person's age, he could calculate in his head how many seconds they had lived. Due to his sisters' deaths, he had a close relationship with his mother, with the two of them sharing the same bed until he left for college. Both of Erdős's parents were high school mathematics teachers, Erdős received much of his early education from them.
Erdős always remembered his parents with great affection. At 16, his father introduced him to two of his lifetime favorite subjects—infinite series and set theory. During high school, Erdős became an ardent solver of the problems proposed each month in KöMaL, the Mathematical and Physical Monthly for Secondary Schools. Erdős entered the University of Budapest at the age of 17. By the time he was 20, he had found a proof for Chebyshev's Theorem. In 1934, at the age of 21, he was awarded a doctorate in mathematics. Erdős's thesis advisor was Lipót Fejér, the thesis advisor for John von Neumann, George Pólya, Paul Turán; because he was a Jew, Erdős decided. Many members of Erdős' family, including two of his aunts, two of his uncles, his father, died in Budapest during the Holocaust, his mother survived in hiding. He was working at the Princeton Institute for Advanced Study at the time. Described by his biographer, Paul Hoffman, as "probably the most eccentric mathematician in the world," Erdős spent most of his adult life living out of a suitcase.
Except for some years in the 1950s, when he was not allowed to enter the United States based on the pretense that he was a Communist sympathizer, his life was a continuous series of going from one meeting or seminar to another. During his visits, Erdős expected his hosts to lodge him, feed him, do his laundry, along with anything else he needed, as well as arrange for him to get to his next destination. On 20 September 1996, at the age of 83, he had a heart attack and died while attending a conference in Warsaw; these circumstances were close to the way. He once said, I want to be giving a lecture, finishing up an important proof on the blackboard, when someone in the audience shouts out,'What about the general case?'. I'll turn to the audience and smile,'I'll leave that to the next generation,' and I'll keel over. Erdős never had no children, he is buried next to his father in grave 17A-6-29 at Kozma Utcai Temető in Budapest. For his epitaph, he suggested "I've stopped getting dumber.". His life was documented in the film N Is a Number: A Portrait of Paul Erdős, made while he was still alive, posthumously in the book The Man Who Loved Only Numbers.
Erdős' name contains the Hungarian letter "ő", but is incorrectly written as Erdos or Erdös either "by mistake or out of typographical necessity". Possessions meant little to Erdős. Awards and other earnings were donated to people in need and various worthy causes, he spent most of his life traveling between scientific conferences and the homes of colleagues all over the world. He earned enough in stipends from universities as a guest lecturer, from various mathematical awards, to fund his travels and basic needs, he would show up at a colleague's doorstep and announce "my brain is open", staying long enough to collaborate on a few papers before moving on a few days later. In many cases, he would ask the c
In the mathematical field of graph theory, the Harries graph or Harries -cage is a 3-regular undirected graph with 70 vertices and 105 edges. The Harries graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is Hamiltonian, it is a 3-vertex-connected and 3-edge-connected non-planar cubic graph. It has book thickness 3 and queue number 2; the characteristic polynomial of the Harries graph is 4 4 5 4 5. In 1972, A. T. Balaban published a -cage graph, a cubic graph that has as few vertices as possible for girth 10, it was the first -cage discovered but it was not unique. The complete list of -cage and the proof of minimality was given by O'Keefe and Wong in 1980. There exist three distinct -cage graphs—the Balaban 10-cage, the Harries graph and the Harries–Wong graph. Moreover, the Harries–Wong graph and Harries graph are cospectral graphs
In mathematics, systolic geometry is the study of systolic invariants of manifolds and polyhedra, as conceived by Charles Loewner and developed by Mikhail Gromov, Michael Freedman, Peter Sarnak, Mikhail Katz, Larry Guth, others, in its arithmetical and topological manifestations. See a slower-paced Introduction to systolic geometry; the systole of a compact metric space X is a metric invariant of X, defined to be the least length of a noncontractible loop in X. In more technical language, we minimize length over free loops representing nontrivial conjugacy classes in the fundamental group of X; when X is a graph, the invariant is referred to as the girth since the 1947 article on girth by W. T. Tutte. Inspired by Tutte's article, Loewner started thinking about systolic questions on surfaces in the late 1940s, resulting in a 1950 thesis by his student Pao Ming Pu; the actual term "systole" itself was not coined until a quarter century by Marcel Berger. This line of research was given further impetus by a remark of René Thom, in a conversation with Berger in the library of Strasbourg University during the 1961-62 academic year, shortly after the publication of the papers of R. Accola and C.
Blatter. Referring to these systolic inequalities, Thom exclaimed: Mais c'est fondamental! Subsequently, Berger popularized the subject in a series of articles and books, most in the March 2008 issue of the Notices of the American Mathematical Society. A bibliography at the Website for systolic geometry and topology contains over 160 articles. Systolic geometry is a developing field, featuring a number of recent publications in leading journals; the link with the Lusternik–Schnirelmann category has emerged. The existence of such a link can be thought of as a theorem in systolic topology; every convex centrally symmetric polyhedron P in R3 admits a pair of opposite points and a path of length L joining them and lying on the boundary ∂P of P, satisfying L 2 ≤ π 4 a r e a. An alternative formulation is. Any centrally symmetric convex body of surface area A can be squeezed through a noose of length π A, with the tightest fit achieved by a sphere; this property is equivalent to a special case of Pu's inequality, one of the earliest systolic inequalities.
To give a preliminary idea of the flavor of the field, one could make the following observations. The main thrust of Thom's remark to Berger quoted above appears to be the following. Whenever one encounters an inequality relating geometric invariants, such a phenomenon in itself is interesting; the classical isoperimetric inequality is a good example. In systolic questions about surfaces, integral-geometric identities play a important role. Speaking, there is an integral identity relating area on the one hand, an average of energies of a suitable family of loops on the other. By the Cauchy–Schwarz inequality, energy is an upper bound for length squared; such an approach works both for the Loewner inequality s y s 2 ≤ 2 3 ⋅ a r e a for the torus, where the case of equality is attained by the flat torus whose deck transformations form the lattice of Eisenstein integers, for Pu's inequality for the real projective plane P2: s y s 2 ≤ π 2 ⋅ a r e a,with equality characterizing a metric of constant Gaussian curvature.
An application of the computational formula for the variance in fact yields the following version of Loewner's torus inequality with isosystolic defect: a r e a − 3 2 s y s 2 ≥ v a r, where f is the conformal factor of the metric with respect to a unit area flat metric in its conformal class. This inequality can be thought of as analogous to Bonnesen's inequality with isoperimetric defect, a strengthening of the isoperimetric inequality. A number of new inequalities of this type have been discovered, including universal volume lower bounds. More details appear at systoles of surfaces; the deepest result in the field is Gromov's inequality for the homotopy 1-systole of an essential n-manifold M: s y s π 1 n ≤ C n vol , where Cn is a universal constant only depending on the dimension of M. Here the homotopy systole sysπ1 is by definition the least length of a noncontractible lo
In the mathematical field of graph theory, the Harries–Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges. The Harries–Wong graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is Hamiltonian, it is a 3-vertex-connected and 3-edge-connected non-planar cubic graph. It has book thickness 3 and queue number 2; the characteristic polynomial of the Harries–Wong graph is 4 4 5 4 5. In 1972, A. T. Balaban published a -cage graph, a cubic graph that has as few vertices as possible for girth 10, it was the first -cage discovered but it was not unique. The complete list of -cages and the proof of minimality was given by O'Keefe and Wong in 1980. There exist three distinct -cage graphs—the Balaban 10-cage, the Harries graph and the Harries–Wong graph. Moreover, the Harries–Wong graph and Harries graph are cospectral graphs
In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e; the definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs there may be multiple dual graphs, depending on the choice of planar embedding of the graph; the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a topological generalization of the geometric concepts of dual polyhedra and dual tessellations, is in turn generalized algebraically by the concept of a dual matroid. Variations of planar graph duality include a version of duality for directed graphs, duality for graphs embedded onto non-planar two-dimensional surfaces.
However, these notions of dual graphs should not be confused with a different notion, the edge-to-vertex dual or line graph of a graph. The term "dual" is used because the property of being a dual graph is symmetric, meaning that if H is a dual of a connected graph G G is a dual of H; when discussing the dual of a graph G, the graph G itself may be referred to as the "primal graph". Many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, simple graphs are dual to 3-edge-connected graphs. Graph duality can help explain the structure of mazes and of drainage basins. Dual graphs have been applied in computer vision, computational geometry, mesh generation, the design of integrated circuits; the unique planar embedding of a cycle graph divides the plane into only two regions, the inside and outside of the cycle, by the Jordan curve theorem.
However, in an n-cycle, these two regions are separated from each other by n different edges. Therefore, the dual graph of the n-cycle is a multigraph with two vertices, connected to each other by n dual edges; such a graph is called a dipole graph. Conversely, the dual to an n-edge dipole graph is an n-cycle. According to Steinitz's theorem, every polyhedral graph must be planar and 3-vertex-connected, every 3-vertex-connected planar graph comes from a convex polyhedron in this way; every three-dimensional convex polyhedron has a dual polyhedron. Whenever two polyhedra are dual, their graphs are dual. For instance the Platonic solids come in dual pairs, with the octahedron dual to the cube, the dodecahedron dual to the icosahedron, the tetrahedron dual to itself. Polyhedron duality can be extended to duality of higher dimensional polytopes, but this extension of geometric duality does not have clear connections to graph-theoretic duality. A plane graph is said to be self-dual; the wheel graphs provide an infinite family of self-dual graphs coming from self-dual polyhedra.
However, there exist self-dual graphs that are not polyhedral, such as the one shown. Servatius & Christopher describe two operations and explosion, that can be used to construct a self-dual graph containing a given planar graph, it follows from Euler's formula that every self-dual graph with n vertices has 2n − 2 edges. Every simple self-dual planar graph contains at least four vertices of degree three, every self-dual embedding has at least four triangular faces. Many natural and important concepts in graph theory correspond to other natural but different concepts in the dual graph; because the dual of the dual of a connected plane graph is isomorphic to the primal graph, each of these pairings is bidirectional: if concept X in a planar graph corresponds to concept Y in the dual graph concept Y in a planar graph corresponds to concept X in the dual. The dual of a simple graph need not be simple: it may have self-loops or multiple edges connecting the same two vertices, as was evident in the example of dipole multigraphs being dual to cycle graphs.
As a special case of the cut-cycle duality discussed below, the bridges of a planar graph G are in one-to-one correspondence with the self-loops of the dual graph. For the same reason, a pair of parallel edges in a dual multigraph corresponds to a 2-edge cutset in the primal graph. Therefore, a planar graph is only if its dual has no 1 - or 2-edge cutsets; the simple planar graphs whose duals are simple are the 3-edge-connected simple planar graphs. This class of graphs includes, but is not the same as, the class of 3-vertex-connected simple planar graphs. For instance, the figure showing a self-dual graph is 3-edge-connected but is not 3-vertex-connected; because the dual graph depends on a particular embedding, the dual graph of a p