Erdös on Graphs

His Legacy of Unsolved Problems

Fan Chung, Ron Graham, At&T Labs

• Publisher: A K Peters/CRC Press
• Year: 2020
• eBook ISBN: 9781000151817
• Edition: 1
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

This book is a tribute to Paul Erdos, the wandering mathematician once described as the " prince of problem solvers and the absolute monarch of problem posers." It examines the legacy of open problems he left to the world after his death in 1996.

CHAPTER 1

Introduction

One of the main treasures Paul Erdős left us is his collection of problems, most of which are still open today. These problems are seeds that Paul sowed during his unceasing travels throughout the world during the past 60 years. As is well known, solutions to many of these problems (or often, attempts to solve them) have frequently led to substantial advances in the relevant areas, and on occasion, completely new branches within these disciplines (e.g., random graph theory, combinatorial set theory, and the probabilistic method). While Paul’s interests (and therefore, problems) ranged over a wide spectrum of mathematics, it is our purpose in this monograph to collect many of his most interesting (in our opinion) problems in graph theory. Our interpretation of graph theory will be inclusive and will include hypergraphs and infinite graphs, for example. In this monograph, all problems placed within boxes are due to Erdős (and his collaborators).

Another tradition for which Paul Erdős was well known was his offers of various cash rewards for some of his favorite problems. We have decided to honor this tradition. For each problem for which Paul had offered a prize, we attach the corresponding amount to the problem, and the appropriate reference (when known). As usual, a requirement for collecting any such prize is the acceptance of the solution in a recognized refereed journal.

We are also very pleased to include three short contributions from Andy Váz-sonyi, in which he brilliantly illustrates various aspects of Paul’s unique personality. As Andy points out, he and Erdős knew each other as teenagers (actually coau-thoring a paper in 1936), and maintained periodic contact throughout the next 60 years.

1.1. Definitions and Notation

A graph G consists of a vertex set V and an edge set E, which is a set of some prescribed (unordered) pairs of V. For a vertex v in V, we say v is adjacent to u if there is an edge {u, v} in E. Throughout this monograph, by a graph we mean a finite graph without multiple edges or loops, unless otherwise specified.

For a graph G with vertex set V and edge set E, a subgraph G′ has vertex set V′ ⊂ V and edge set E′ ⊂ E. An induced subgraph on the vertex set S ⊂ V is a subgraph with vertex set S and edge set consisting of all edges of G with both endpoints in S.

We say u is a neighbor of v if u is adjacent to v. The number of neighbors of v is called the degree of v. If the degrees of all vertices in G are equal, we say that G is regular.

Next we define some special graphs:

• The complete graph K_n has n vertices and all #### possible edges. A complete graph is sometimes called a clique.

• The complete bipartite graph K_n,m has vertex set being the disjoint union of a set A of n vertices and a set B of m vertices. All edges {u, v} with u ∈ A and v ∈ B are in K_n,m. A bipartite graph is a subgraph of a complete bipartite graph. In general, the complete multipartite graph K_n1,…, n_r has the vertex set being the disjoint union of sets A_i, 1 ≤ i ≤ r, and the edge set consisting of all edges {u, v} with u 6 A_i and v ∈ A_j, and i ≠ j.

• A path P_n in a graph G is a sequence of distinct vertices v_i,… ,v_n with v_i adjacent to v_i+1 for i = 1,… , n − 1. A graph G is said to be connected if for any two vertices u and v, there is a path joining u and v.

• A cycle C_n consists of vertices v₁,… ,v_n and edges {v_i,v_i+1} where the index addition is taken modulo n.

• A connected graph containing no cycle is said to be a tree. We often write T_n to represent a tree on n vertices.

• An n-cube, denoted by Q_n, has 2ⁿ vertices consisting of all (0, 1)-tuples of length n. Two vertices in Q_n are adjacent if they differ in exactly one coordinate.

For an integer r, an r-uniform hypergraph H (or r-graph, for short) has a vertex set V together with an edge set V which consists of some prescribed r-subsets of V, called hyperedges or r-edges. A complete r-graph on n vertices, denoted by ####has a vertex set V of size n and edge set consisting of all r-subsets of V. A complete r-partite r-graph has a vertex set equal to the disjoint union of sets A₁,… ,A_r and edge set consisting of all r-sets containing exactly one vertex in each A_i, for i = 1,… , r. Clearly, graphs are special cases of r-graphs with r = 2.

For undefined graph-theoretical terminology, the reader is referred to Bollobás.¹ Throughout this paper, the constants c,c′,c₁,c₂, …. and extremal functions f(n), f(n,k), ƒ(n, k,r,t), g(n),… are used extensively (and repeatedly), although within the context of each problem, the notation is consistent.

1.2. About the References

There is a huge bibliography of almost 1500 papers written by Paul Erdős and his (more than 460) collaborators. Various lists of Erdős’ papers have appeared in the following journals and books:

• Combinatorial 3 (1983): 247–280.

• Combinatorics, Paul Erdős is Eighty, (D. Miklós, V. T. Sós, and T. Szônyi, eds.), Bolyai Soc. Math. Studies, Vol. 1, 1990, 471–527, Vol. 2, 1993, 507–516.

• The Mathematics of Paul Erdős, II, (R. L. Graham and J. Nešetřil, eds.), 477–573. Berlin: Springer-Verlag, 1996.

An electronic file is maintained by Jerry Grossman at [email protected]. There are quite a few survey papers on the influence of Paul’s work in various areas. We list some of these here:

• L. Babai. In and out of Hungary: Paul Erdős, his friends, and times, in Combinatorics, Paul Erdős is Eighty,...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Dedication
• Table of Contents
• Preface
• Acknowledgements
• Chapter 1. Introduction
• Chapter 2. Ramsey Theory
• Chapter 3. Extremal Graph Theory
• Chapter 4. Coloring, Packing, and Covering
• Chapter 5. Random Graphs and Graph Enumeration
• Chapter 6. Hypergraphs
• Chapter 7. Infinite Graphs
• Erdős Stories as told by Andy Vázsonyi
• Index