The Mathematics of Paul Erdös II

Erdős ’ work in graph theory started early and arose in connection with D. König, his teacher in prewar Budapest. The classic paper of Erdős’ and Szekeres from 1935 also contains a proof in “graphotheoretic terms.” The investigation of the Ramsey function led Erdős to probabilistic methods and seminal papers in 1947, 1958 and 1960. It is perhaps interesting to note that three other very early contributions of Erdős’ to graph theory (before 1947) were related to infinite graphs: infinite Eulerian graphs (with Gallai and Vászoni) and a paper with Kakutani On nondenumerable graphs (1943). Although the contributions of Erdős to graph theory are manifold, and he proved (and always liked) beautiful structural results such as the Friendship Theorem (jointly with V. T. Sós and Kövári), and compactness results (jointly with N. G. de Bruijn), his main contributions were in asymptotic analysis, probabilistic methods, bounds and estimates. Erdős was the first who brought to graph theory the experience and rigor of number theory (perhaps being preceded by two papers by V. Jarnik, one of his early coauthors). Thus he contributed in an essential way to lifting graph theory up from the “slums of topology.” This chapter contains a “special” problem paper not by Erdős but by his frequent coauthors from Memphis: R. Faudree, C. C. Rousseau and R. Schelp (well, there is actually an Erdős supplement there as well). We encouraged the authors to write this paper and we are happy to include it in this volume.

This is a summary of problems and results coming out of the 20 year collaboration between Paul Erdős and the authors.

A bipartite covering of order k of the complete graph K _n on n vertices is a collection of complete bipartite graphs so that every edge of K _n lies in at least 1 and at most k of them. It is shown that the minimum possible number of subgraphs in such a collection is Θ(kn1/k). This extends a result of Graham and Pollak, answers a question of Felzenbaum and Perles, and has some geometric consequences. The proofs combine combinatorial techniques with some simple linear algebraic tools.

Let G bea triangle-free graph of order n and minimum degree δ > n/3. We will determine all lengths of cycles occurring in G. In particular, the length of a longest cycle or path in G is exactly the value admitted by the independence number of G. This value can be computed in time O(n2.5) using the matching algorithm of Micali and Vazirani. An easy consequence is the observation that triangle-free non-bipartite graphs with $$\delta \geqslant \frac{3} {8}n$$ are hamiltonian.

Associate to a finite directed graph G(V, E) its out-degree resp. in degree sequences d+, d− and the corresponding neighborhood lists N+, N− (when G is a labeled graph). We discuss various problems when sequences resp. lists of sets can be realized as degree sequences resp. neighborhood lists of a directed graph.

The random graph order P _{n, p} is obtained from a random graph G _{n, p} on [n] by treating an edge between vertices i and j, with i ≺ j in [n], as a relation i < j, and taking the transitive closure. This paper forms part of a project to investigate the structure of the random graph order P _{n, p} throughout the range of p = p(n). We give bounds on the dimension of P _{n, p} for various ranges. We prove that, if p log log n → ∞ and ε > 0 then, almost surely, $$\left( {1 - \in } \right)\sqrt {\frac{{\log n}} {{\log (1/q)}}} \leqslant \dim P_{n,p} \leqslant (1 + \in )\sqrt {\frac{{4\log n}} {{3\log (1/q)}}} .$$We also prove that there are constants c₁, c₂ such that, if p log n → 0 and p ≥ log n/n, then $$c_1 p^{ - 1} \leqslant \dim P_{n,p} \leqslant c_2 p^{ - 1} .$$We give some bounds for various other ranges of p(n), but several questions are left open.

Given a hereditary graph property Ρ let Ρ _n be the set of those graphs in Ρ on the vertex set {1, …, n}. Define the constant c _n by $$\left| {P^n } \right| = 2^{cn(_2^n )} .$$ We show that the limit lim_{n → ∞} c _n always exists and equals 1 − 1/r, where r is a positive integer which can be described explicitly in terms of Ρ. This result, obtained independently by Alekseev, extends considerably one of Erdős, Frankl and Rödl concerning principal monotone properties and one of Prömel and Steger concerning principal hereditary properties.AMS Subject Classification: Primary 05C35, Secondary 05C30.

We answer the following question: Let P and Q be graded posets having some property and let ∘ be some posets operation. Is it true that P ∘ Q has also this property? The considered properties are: being Sperner, a symmetric chain order, Peck, LYM, and rank compressed. The studied operations are: direct product, direct sum, ordinal sum, ordinal product, rankwise direct product, and exponentiation.

A p-representation of the complete graph Κ _{n, n} is a collection of sets {S₁, S₂, …, S_2n } such that |S _i ∩ S _j | ≥ p if and only if i ≤ n < j. Let υ _p (Κ _{n, n} ) be the smallest cardinality of ∪S _i . Using the Frankl-Rödl theorem about almost perfect matchings in uncrowded hypergraphs we prove the following conjecture of Chung and West. For fixed p while n → ∞ we have υ _p (Κ _{n, n} ) = (1 + º(1))n2/p. Several problems remain open.

We consider some problems suggested by special cases of a conjecture of Erdős and Hajnal.

A two-packing of a graph G is a bijection σ : V(G) → V(G) such that for every two adjacent vertices a, b € V(G) the vertices σ(a)) and σ(b) are not adjacent. It is known [2], [6] that every forest G which is not a star has a two packing σ. If F _σ is the graph whose vertices are the vertices of G and in which two vertices a, b are adjacent if and only if a, b or σ−1(a), σ−1(b) are adjacent in G then it is easy to see that the chromatic number of F _σ is either 1, 2, 3 or 4. We characterize, for each number n between one and four, all forests F which have a two-packing σ such that F _σ has chromatic number n.

Two parties are said to “share a secret” if there is a question to which only they know the answer. Since possession of a shared secret allows them to communicate a bit between them over an open channel without revealing the value of the bit, shared secrets are fundamental in cryptology.We consider below the problem of when two parties with shared knowledge can use that knowledge to establish, over an open channel, a shared secret. There are no issues of complexity or probability; the parties are not assumed to be limited in computing power, and secrecy is judged only relative to certainty, not probability. In this context the issues become purely combinatorial and in fact lead to some curious results in graph theory.Applications are indicated in the game of bridge, and for a problem involving two sheriffs, eight suspects and a lynch mob.

All (undirected) graphs and digraphs considered are assumed to be finite (if not otherwise stated) and loopless. Multiple edges (arcs) are permitted. For a graph G, let V(G), E(G) and X(G) denote the vertex set, the edge set, and the chromatic number of G, respectively. If X ⊆ V(G) and F ⊆ E(G) then G − X − F denotes the subgraph H of G satisfying V(H) = V(G) − X and E(H) = {xy | xy ∈ E(G) − F and x, y ∉ X}.

It is perhaps evident from several places of this volume that Ramsey theorem played a decisive role in Erdős’ combinatorial activity. And perhaps no other part of combinatorial mathematics is so dear to him as Ramsey theory and extremal problems. He was not creating or even aiming for a theory. However, a complex web of results and conjectures did, in fact, give rise to several theories. They all started with modest short papers by Erdős, Szekeres and Turán in the thirties. How striking it is to compare these initial papers with the richness of the later development, described, E.g., by the survey articles of Miki Simonovits (extremal graph theory) and Jeff Kahn (extremal set theory). In addition, the editors of these volumes tried to cover in greater detail the development of Ramsey theory mirrored and motivated by Erdős’ papers. In a way (and this certainly is one of the leitmotivs of Erdős’ work), there is little difference between, say, density Ramsey type results and extremal problems.

Paul Erdős is 801 and the mathematical community is celebrating him in various ways. Jarik Neřetšil also organized a small conference in Prague in his honour, where we, combinatorists and number theorists attempted to describe in a limited time the enourmous influence Paul Erdős made on the mathematics of our surrounding (including our mathematics as well). Based on my lecture given there, I shall to survey those parts of Extremal Graph Theory that are connected most directly with Paul Erdős’s work.In Turán type extremal problems we usually have some sample graphs L₁, …, L_r, and consider a graph G _n on n vertices not containing any L _i . We ask for the maximum number of edges such a G _n can have. We may ask similar questions for hypergraphs, multigraphs and digraphs.We may also ask, how many copies of forbidden subgraphs L _i must a graph G _n contain with a given number of edges superseding the maximum in the corresponding extremal graph problems. These are the problems on Supersaturated Graphs.We can mix these questions with Ramsey type problems, (Ramsey-Turán Theory). This topic is the subject of a survey by V. T. Sós [162].These topics are definitely among the favourite areas in Paul Erdős’s graph theory.

Ramsey’s theorem was not discovered by P. Erdős. But perhaps one could say that Ramsey theory was created largely by him. This paper will attempt to demonstrate this claim.

I am one of the very few mathematicians who knew Paul’s aunt Irma before I knew him. She and my grandmother were neighbors during World War II. Aunt Irma was one of the few Jews in Budapest who survived the holocaust. This is how I met her since I was raised from this time by my grandmother and my aunt. Aunt Irma must have had good memories about my grandmother since they kept a good relationship, she regularly visited my grandmother even after her move to another place. She learned about my interest in mathematics and suggested I meet her nephew Pali who happened to be a mathematician. “Of course” I had never heard of him, but I was very glad to meet an old “real mathematician”. He was a very respectful old man (46!). I immediately understood that I was seeing an extraordinary personality.

There are two central themes to research involving applications of probabilistic methods to partially ordered sets. The first of these can be described as the study of random partially ordered sets. Among the specific models which have been studied are: random labelled posets; random t-dimensional posets; and the transitive closure of random graphs. A second theme concentrates on the adaptation of random methods so as to be applicable to general partially ordered sets. In this paper, we concentrate on the second theme. Among the topics we discuss are fibers and co-fibers; the dimension of subposets of the subset lattice; the dimension of posets of bounded degree; and fractional dimension. This last topic leads to a discussion of ramsey theoretic questions for probability spaces.

P. Erdős and R. Rado defined a Δ-system as a family in which every two members have the same intersection. Here we obtain a new upper bound of the maximum cardinality φ(n) of an n-uniform family not containing any Δ-system of cardinality 3. Namely, we prove that for any α > 1, there exists C = C(α) such that for any n, φ(n) ≤ C n!α−n.

Let k be an integer. A graph G is k-arrangeable (concept introduced by Chen and Schelp) if the vertices of G can be numbered υ₁, υ₂, …, υ_n in such a way that for every integer i with 1 ≤ i ≤ n, at most k vertices among {υ₁, υ₂, …, υ_n} have a neighbor υ∈{υ_i+1, υ_i+2, …, υ_n} that is adjacent toυ_i. We prove that for every integer p ≥ 1, if a graph G is not p8-arrangeable, then it contains a K_p-subdivision. By a result of Chen and Schelp this implies that graphs with no K_p-subdivision have “linearly bounded Ramsey numbers, ” and by a result of Kierstead and Trotter it implies that such graphs have bounded “game chromatic number”.

We prove that double exponentiation is an upper bound to Ramsey’s theorem for colouring of pairs when we want to predetermine the order of the differences of successive members of the homogeneous set.The following problem was raised by Jouko Vaananen for model theoretic reasons (having a natural example of the difference between two kinds of quantifiers, actually his question was a specific case), and propagated by Joel Spencer: Is there for any n, c an m such that(*) for every colouring f of the pairs from {0, 1, …, m − 1} by 2 (or even c) colours, there is a monochromatic subset {a₀, …, a _n−1}, a₀ < a₁ < … such that the sequence (a _i+1 − a _i : i < n − 1) is with no repetition and is with any pregiven order.Noga Alon [Al] and independently Janos Pach proved that for every n, c there is such an m as in (*); Alon used van der Waerden numbers (see [Sh:329]) (so obtained weak bounds).Later Alon improved it to iterated exponential (Alan Stacey and also the author have later and independently obtained a similar improvement). We get a double exponential bound. The proof continues [Sh:37]. Within the ”realm” of double exponential in c, n we do not try to save.We thank Joel Spencer for telling us the problem, and Martin Goldstern for help in proofreading.

Erdős’ love for geometry and elementary or discrete geometry in particular, dates back to his beginnings. The Erdős-Szekeres paper has been influential and certainly helped to create discrete geometry as we know it today. But Erdős also put geometry to the service to other branches, giving definition to various geometrical graphs and proving bounds on their chromatic and independence numbers. We are happy to include papers by Moshe Rosenfeld, Pavel Valtr, Janos Pach, Jiří Matoušek and, in particular, a paper by Miklós Laczkovich and Imre Ruzsa on the number of homothetic sets. While the paper of Peter Fishburn is closely related to Erdős’ favorite theme, the papers of N. G. de Bruijn (on Penrose tiling) and J. Aczél and L. Losonczi (on functional equations) cover broader related aspects. It is perhaps fitting to complement this introduction by a few related Erdős problems in his own words:Let x₁, …, x _n be n points in the plane, not all on a line, and join every two of them. Thus we get at least n distinct lines. This follows from Gallai-Sylvester but also from a theorem of de Bruijn and myself.

Extension theorems are common in various areas of mathematics. In topology continuous extensions of continuous functions are studied. In functional analysis one is interested mainly in linear extensions of linear operators preserving continuity or some other properties like bounds or norm. In algebra extensions of homomorphisms and isomorphisms are investigated. The latter can be considered as extensions of functional equations.

This paper will cover some details on Penrose tilings presented in lectures over the years but never published in print before. The main topics are: (i) the characterizability of Penrose tilings by means of a local rule that does not refer to arrows on the edges of the tiles, and (ii) the fact that the Ammann quasigrid of the inflation of a Penrose tiling is topologically equivalent to the pentagrid that generates the original tiling.

One of Paul Erdős’s many continuing interests is distances between points in finite sets. We focus here on conjectures and results on intervertex distances in convex polygons in the Euclidean plane. Two conjectures are highlighted. Let t(x) be the number of different distances from vertex x to the other vertices of a convex polygon C, let T(C) = Σt(x), and take T_n = min{T(C) : C has n vertices}. The first conjecture is $$T_n = \left( {_2^n } \right)$$. The second says that if $$T\left(C\right) = \left( {_2^n } \right)$$ for a convex n-gon, then the n-gon is regular if n is odd, and is what we refer to as bi-regular if n is even. The conjectures are confirmed for small n.

We investigate the maximal number S(P, n) of subsets of a set of n elements homothetic to a fixed set P. Elekes and Erdős proved that S(P, n) > cn2 if |P| = 3 or the elements of P are algebraic. For |P| ≥ 4 we show that S(P, n) > cn2 if and only if every quadruple in P has an algebraic cross ratio. Moreover, there is a sequence S _n of numbers such that S(P, n) ≍ S _n whenever |P| = 4 and the cross ratio of P is transcendental.

Recently Preiss [4] proved that every subset of the plane of a positive Lebesgue measure can be mapped onto a square by a Lipschitz map. In this note we give an alternative proof of this result, based on a well-known combinatorial lemma of Erdős and Szekeres. The validity of an appropriate generalization of this lemma into higher dimensions remains as an open problem.

In his classical monograph published in 1935, Dénes König [K] included one of Paul Erdös’s first remarkable results: an infinite version of the Menger theorem. This result (as well as the König-Hall theorem for bipartite graphs, and many related results covered in the book) can be reformulated as a statement about transversals of certain hypergraphs.Let H be a hypergraph with vertex set V(H) and edge set E(H). A subset T C V(H) is called a transversal of H if it meets every edge E E E(H). The transversal number, r(iJ), is defined as the minimum cardinality of a transversal of H. Clearly, r(H) > v(H), where v(H) denotes the maximum number of pairwise disjoint edges of H. In the above mentioned examples, r(H) = v(H) holds for the corresponding hypergraphs. However, in general it is impossible to bound r from above by any function of u, without putting some restriction on the structure of H.

We use the Gram matrix to prove that the largest number of points in Rd such that the distance between all pairs is an odd integer (the square root of an odd integer) is ≤ d + 2 and we characterize all dimensions d for which the upper bound is attained. We also use the Gram matrix to obtain an upper bound for the smallest angle determined by sets of n lines through the origin in Rd.

Two finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of anyone of these two sets does not intersect the convex hull of the other set. For any integer n, we construct a set of n points in general position in the plane which contains no pair of mutually avoiding sets of size more than $$O\left( {\sqrt n } \right)$$ each. The given bound is tight up to a constant factor, since Aronov et al. [1] showed a polynomial-time algorithm for finding two mutually avoiding sets of size $$\Omega \left( {\sqrt n } \right)$$ each in any set of n points in general position in the plane.

Paul Erdős was always interested in infinity. One of his earliest results is an infinite analogue of (the then very recent) Menger’ s theorem (which was included in a classical book of his teacher Denes König). Two out of his earliest three combinatorial papers are devoted to infinite graphs. According to his personal recollections, Erdős always had an interest in “large cardinals” although his earliest work on this subject are joint papers with A. Tarski from the end of thirties. These interests evolved over the years into the Giant Triple Paper, with the Partition Calculus forming a field rightly called here Erdősian Set Theory.

Erdős and Rényi showed the paradoxical result that there is a unique (and highly symmetric) countably infinite random graph. This graph, and its automorphism group, form the subject of the present survey.

Paul Erdős has published more than one hundred research papers in set theory. It is my rough estimate that these contain more than one thousand theorems, many having an interest in their own right. Although most of his problems and results have a combinatorial flavour, and the subject now known as “combinatorial set theory ” is one he helped to create, it is also true to say that his work has had a very important impact upon the direction of research in many parts of present day set theory. Whole theories have developed out of basic questions which he formulated.

We discuss a few issues concerning Erdős’ conjecture on the extension of Menger’s theorem to infinite graphs. A key role is given to a lemma to which the conjecture can probably be reduced. The paper is intended to be expository, so rather than claim completeness of proofs, we chose to prove the reduction only for graphs of size ℵ₁. We prove the lemma (and hence the ℵ₁ case of the conjecture) in two special cases: graphs with countable out-degrees, and graphs with no unending paths. We also present new versions of the proofs of the (already known) cases of countable graphs and graphs with no infinite paths. A main tool used is a transformation converting the graph into a bipartite graph.

We investigate the property of certain well-founded orderings to have a chain of maximal ordinal length. We show that Hey ting algebras and countable modular lattices have this property, but we also present an example of a ”well-behaved” lattice which does not have it. We prove a general necessary and sufficient condition for modular lattices to have the property in a hereditary form. This hereditary form is called order-perfectness, being analogous to perfectness of finite graphs. Certain well-known theorems of D.H.J, de Jongh, R. Parikh, D. Schmidt, E.C. Milner, N. Sauer, and N. Zaguia turn out to be order-perfectness results.

Thepcf theorem (of the possible cofinability theory) was proved for reduced products$$\prod\limits_{i < k} {{\lambda _i}/I}$$, where κ < min _i<κ λ _i . Here we prove this theorem under weaker assumptions such as wsat(I) < min _i<κ λ _i , where wsat(I) is the minimal θ such that κ cannot be divided to θ sets ∉ I (or even slightly weaker condition). We also look at the existence of exact upper bounds relative to < _I (< _I —eub) as well as cardinalities of reduced products and the cardinals T _D (λ). Finally we apply this to the problem of the depth of ultraproducts (and reduced products) of Boolean algebras.

In this Chapter we consider P. Erdős’ research on what can be called as the borderlines of set theory with some of the more classical branches of mathematics as geometry and real analysis. His continuing interest in these topics arose from the world view in which the prime examples of sets are those which are subsets of some Euclidean spaces. ‘Abstract’ sets of arbitrary cardinality are of course equally existing. Paul only uses his favorite game for inventing new problems; having solved some problems find new ones by adding and/or deleting some structure on the sets currently under research. A good example is the one about set mappings. This topic was initiated by P. Turán who asked if a finite set f(x) is associated to every point x of the real line does necessarily exist an infinite free set, i.e., when x ∉ f(y) holds for any two distinct elements. Clearly the underlying structure has nothing to do with the question and eventually a nice theory emerged which culminated in the results of Erdős, G. Fodor, and A. Hajnal. But Paul and his collaborators kept returning to the original setup when the condition is e.g. changed to: let f(x) be nowhere dense, etc. Several nice and hard results have recently been proved. (See Section 8. in this Chapter.)