Erdős Centennial

Frontmatter

Paul Erdős and Probabilistic Reasoning

Abstract

One of the major contributions of Paul Erdős is the development of the Probabilistic Method and its applications in Combinatorics, Graph Theory, Additive Number Theory and Combinatorial Geometry. This short paper describes some of the beautiful applications of the method, focusing on the long-term impact of the work, questions and results of Erdős. This is mostly a survey, but it contains a few novel results as well.

Noga Alon

Euclidean vs. Graph Metric

Abstract

The theory of sparse graph limits concerns itself with versions of local convergence and global convergence, see e.g. [44]. Informally, in local convergence we look at a large neighborhood around a random uniformly chosen vertex in a graph and in global convergence we observe the whole graph from afar. In this note rather than surveying the general theory we will consider some concrete examples and problems of global and local convergence, with a geometric viewpoint. We will discuss how well large graphs approximate continuous spaces such as the Euclidean space. Or how properties of Euclidean space such as scale invariance and rotational invariance can appear in large graphs.

Itai Benjamini

The Phase Transition in the Erdős-Rényi Random Graph Process

Abstract

We shall review the foundation of the theory of random graphs by Paul Erdős and Alfréd Rényi, and sketch some of the later developments concerning the giant component, including some very recent results.

Béla Bollobás, Oliver Riordan

Around the Sum-product Phenomenon

Abstract

The purpose of this exposé is to give a sample of P. Erdős many contributions to combinatorics that turned out to be unexpectedly seminal. He was indeed a master in recognizing seemingly elementary questions which require new insights, often with far reaching consequences. The results discussed below originate from his papers “Problems and results in combinatorial number theory, III” ([32]), “On sums and products of integers”, ([33]), jointly with Szemerédi, and “Additive Gruppen mit vorgegebener Hausdorffscher Dimension” ([34]), jointly with Volkmann. These papers led to numerous developments over the past decade and influenced other parts of mathematics, including number theory, theoretical computer science, ergodic theory and group theory. Giving a fair account of them would be a considerable task and we limit ourselves to citing just a few. The choice only reflects the author’s interests and research; many related contributions and contributors will not be cited and the bibliography strictly serves this presentation.

Jean Bourgain

Small Doubling in Groups

Abstract

Let A be a subset of a group G = (G; ·). We will survey the theory of sets A with the property that |A · A|≤K|A|, where A · A = {a1a2: a1; a2 ∈ A}. The case G = (ℤ; +) is the famous Freiman-Ruzsa theorem.

Emmanuel Breuillard, Ben Green, Terence Tao

Erdős and Multiplicative Number Theory

Abstract

Paul Erdős was a prolific writer of letters as well as articles. Along with many other mathematicians in areas such as number theory, combinatorics, and set theory, I was on his “mailing list.“ Paul’s letters arrived several times a year from mathematics centers near and far. They typically began, I hope you are well and things are OK in Samland. I am visiting A right now, and leave next week to preach in B. Let f(n) be a function … . This article reviews some of the topics we discussed: estimates of prime number counts, distribution questions for the Euler φ function, and elementary methods in prime number theory.

Harold G. Diamond

The History of Degenerate (Bipartite) Extremal Graph Problems

Abstract

This paper is a survey on Extremal Graph Theory, primarily focusing on the case when one of the excluded graphs is bipartite. On one hand we give an introduction to this field and also describe many important results, methods, problems, and constructions.

Zoltán Füredi, Miklós Simonovits

Erdős and Arithmetic Progressions

Abstract

Two of Erdős’s most famous conjectures concern arithmetic progressions. In this paper we discuss some of the progress that has been made on them.

W. Timothy Gowers

Paul Erdős and Egyptian Fractions

Abstract

One of Paul Erdős’ earliest mathematical interests was the study of so-called Egyptian fractions, that is, finite sums of distinct fractions having numerator 1. In this note we survey various results in this subject, many of which were motivated by Erdős’ problems and conjectures on such sums. This note complements the excellent treatment of this topic given by A. Schinzel in 2002.¹

Ronald L. Graham

Perfect Powers in Products with Consecutive Terms from Arithmetic Progressions, II

Abstract

There is a very rich literature on perfect powers or almost perfect powers in products of the form m(m + d) …: (m + (k − 1)d), where m, d are coprime positive integers and k ≥ 3. By a conjecture, such a product is never a perfect n-th power if k > 3, n ≥2 or k = 3, n > 2. In the classical case d = 1 the conjecture has been proved by Erdős and Selfridge [11]. The general case d ≥ 1 seems to be very hard, then there are only partial results; for survey papers on results obtained before 2006 we refer to Tijdeman [46]– [48], Shorey and Tijdeman [43, 44], Shorey [38]–[42]_and Győry [15, 16].

Kálmán Győry

Erdős’s Work on Infinite Graphs

Abstract

The theory of infinite graphs was one of Erdös’s favorite topics, and it is no exaggeration to state that the major results and notions were created by him and his collaborators. As one of the few persons equally versed in finite as well as in infinite sets, upon hearing a result on finite graphs, he always eagerly checked if it has a reasonable counterpart for infinite graphs.

Péter Komjáth

The Impact of Paul Erdős on Set Theory

Abstract

This is a brief survey of some areas in set theory where the impact of Paul Erdős is strongly felt today. We omit topics in partition theory and graph theory, which are covered in the article by Péter Komjáth in this volume.

Kenneth Kunen

Some Problems and Ideas of Erdős in Analysis and Geometry

Abstract

I review a meager few of the many problems and ideas Erdős proposed over the years involving a mixture of measure theory, geometry, and set theory.

R. Daniel Mauldin

L 2 Majorant Principles

Abstract

In this short historical note, we discuss an important majorant principle introduced by Erdős & Fuchs [1].

Hugh L. Montgomery

A Combinatorial Classic — Sparse Graphs with High Chromatic Number

Abstract

It seems that combinatorics, and graph theory in particular, reached mathematical maturity relatively recently. Perhaps as a result of this there are not too many essential stories which have determined the course of the subject over a long period, enduring stories which appear again and again as a source of inspiration and motivate and challenge research.

Jaroslav Nešetřil

Small Ball Probability, Inverse Theorems, and Applications

Abstract

Let ξ be a real random variable with mean zero and variance one and A ={a ₁; …; a _n } be a multi-set in R ^d . The random sum

$$S_A : = a_1 \xi _1 + \cdots + a_n \xi _n$$

where ξ _i are iid copies of ξ is of fundamental importance in probability and its applications.

We discuss the small ball problem, the aim of which is to estimate the maximum probability that S _A belongs to a ball with given small radius, following the discovery made by Littlewood-Offord and Erdős almost 70 years ago. We will mainly focus on recent developments that characterize the structure of those sets A where the small ball probability is relatively large. Applications of these results include full solutions or significant progresses of many open problems in different areas.

Hoi H. Nguyen, Van H. Vu

The Beginnings of Geometric Graph Theory

Abstract

Geometric graphs (topological graphs) are graphs drawn in the plane with possibly crossing straight-line edges (resp., curvilinear edges). Starting with a problem of Heinz Hopf and Erika Pannwitz from 1934 and a seminal paper of Paul Erdős from 1946, we give a biased survey of Turán-type questions in the theory of geometric and topological graphs. What is the maximum number of edges that a geometric or topological graph of n vertices can have if it contains no forbidden subconfiguration of a certain type? We put special emphasis on open problems raised by Erdős or directly motivated by his work.

János Pach

Paul Erdős and the Difference of Primes

Abstract

In the present work we discuss several problems concerning the difference of primes, primarily regarding the difference of consecutive primes. Most of them were either initiated by Paul Erdős (sometimes with coauthors), or were raised ahead of Erdős; nevertheless he was among those who reached very important results in them (like the problem of the large and small gaps between consecutive primes).

János Pintz

Paul Erdős and the Rise of Statistical Thinking in Elementary Number Theory

Abstract

It might be argued that elementary number theory began with Pythagoras who noted two-and-a-half millennia ago that 220 and 284 form an amicable pair. That is, if s(n) denotes the sum of the proper divisors of n (“proper divisor” means d │ n and 1 ≤ d < n), then

$$s(220) = 284\quad and\quad s(284) = 220.$$

When faced with remarkable examples such as this it is natural to wonder how special they are. Through the centuries mathematicians tried to find other examples of amicable pairs, and they did indeed succeed. But is there a formula? Are there infinitely many? In the first millennium of the common era, Thâbit ibn Qurra came close with a formula for a subfamily of amicable pairs, but it is far from clear that his formula gives infinitely many examples and probably it does not.

Paul Pollack, Carl Pomerance

Extremal Results in Random Graphs

Abstract

According to Paul Erdős au][Some notes on Turán’s mathematical work, J. Approx. Theory 29 (1980), page 4]_it was Paul Turán who “created the area of extremal problems in graph theory”. However, without a doubt, Paul Erdős popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this field can be traced back to Paul Erdős, Paul Turán, as well as their collaborators and students. Paul Erdős also established the probabilistic method in discrete mathematics, and in collaboration with Alfréd Rényi, he started the systematic study of random graphs. We shall survey recent developments at the interface of extremal combinatorics and random graph theory.

Vojtěch Rödl, Mathias Schacht

Erdős’s Work on the Sum of Divisors Function and on Euler’s Function

Abstract

The following notation will be used throughout

log _r x is the r times iterated logarithm of x,

$$\begin{gathered}\sigma _1 (n) = \sigma (n),\quad \sigma _k (n) = \sigma (\sigma _{k - 1} (n)), \hfill \\\phi _1 (n) = \phi (n),\quad \phi _k (n) = \phi (\phi _{k - 1} (n)), \hfill \\s_1 (n) = s(n) = \quad \sigma (n) - n,\quad s_i (n) = s_1 (s_{i - 1} (n)); \hfill \\\end{gathered}$$

ψ is Euler’s constant, \(\alpha _0 = \log \Pi _p \;prime\;(1 - \frac{1}{p})^{ - 1/p}\). Density is always the asymptotic density.

Andrzej Schinzel

Some Results and Problems in the Theory of Word Maps

Abstract

In recent years there has been much interest in word maps on groups, with various motivations and applications. Substantial progress has been made and many fundamental questions were solved, using a wide spectrum of tools, including representation theory, probability and geometry. This paper is an extended survey of the various developments in this field. We also suggest remaining open problems, conjectures and possible directions for further research.

Aner Shalev

Some of Erdős’ Unconventional Problems in Number Theory, Thirty-four Years Later

Abstract

There are many ways to recall Paul Erdős’ memory and his special way of doing mathematics. Ernst Straus described him as “the prince of problem solvers and the absolute monarch of problem posers”. Indeed, those mathematicians who are old enough to have attended some of his lectures will remember that, after his talks, chairmen used to slightly depart from standard conduct, not asking if there were any questions but if there were any answers.

Gérald Tenenbaum

Erdős on Polynomials

Abstract

Some results of Erdős on polynomials and some later developments are reviewed. The topics that this survey covers are: discrepancy estimates for zero distribution, orthogonal polynomials, distribution and spacing of their zeros and critical points of polynomials.

Vilmos Totik

Paul Erdős and Interpolation: Problems, Results, New Developments

Abstract

Pál (Paul) Erdős was born 100 years ago (March 26, 1913 in Budapest). He died on September 20, 1996 in Warsaw, when he attended a conference. He wrote about 1500 papers mainly with coauthors including those more than 80 works which are closely connected with approximation theory (interpolation, mean convergence, orthogonal polynomials, a.s.o.).

Peter Vertesi