Erdős–Szekeres Theorem for Lines

According to the Erd?s–Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd?s–Szekeres theorem.     

Vertex-minors and the Erdős–Hajnal conjecture

We prove that for every graph $H$, there exists $\epsilon >0$ such that every $n$-vertex graph with no vertex-minors isomorphic to $H$ has a pair of disjoint sets $A$, $B$ of vertices such that $\left|A\right|,\left|B\right|\ge \epsilon n$ and $A$ is complete or anticomplete to $B$. We deduce this from recent work of Chudnovsky, Scott, Seymour, and Spirkl (2018). This proves the analog of the Erd?s–Hajnal conjecture for vertex-minors.     

Probabilistic Extensions of the Erdős–Ko–Rado Property

The classical Erdős–Ko–Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size , then the largest possible pairwise intersecting family has size . We consider the probability that a randomly selected family of size t=t _n has the EKR property (pairwise nonempty intersection) as n and k=k _n tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson’s inequality. Using the Stein–Chen method we show that the distribution of X ₀, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for X _i , the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution (X ₀, X ₁, ..., X _b ) can be approximated by a multidimensional Poisson vector with independent components.      

The Erdős–Ko–Rado Theorem for Integer Sequences

n , q, t we determine the maximum number of integer sequences which satisfy for , and any two sequences agree in at least t positions. The result gives an affirmative answer to a conjecture of Frankl and Füredi. Received: January 26, 1998     

On a problem of Erdős

Let s≥2 be an integer. Denote by f ₁(s) the least integer so that every integer l>f ₁(s) is the sum of s distinct primes. Erd?s proved that f ₁(s)<p ₁+p ₂+?+p _s +Cslogs, where p _i is the ith prime and C is an absolute constant. In this paper, we prove that f ₁(s)=p ₁+p ₂+?+p _s +(1+o(1))slogs=p ₂+p ₃+?+p _s+1+o(slogs). This answers a question posed by P. Erd?s.     

Tauberian Theorem of Erdős Revisited

Dedicated to the memory of Paul Erdős In connection with the elementary proof of the prime number theorem, Erdős obtained a striking quadratic Tauberian theorem for sequences. Somewhat later, Siegel indicated in a letter how a powerful "fundamental relation" could be used to simplify the difficult combinatorial proof. Here the author presents his version of the (unpublished) Erdős–Siegel proof. Related Tauberian results by the author are described. Received December 20, 1999     

Proof of the Erdős–Faudree Conjecture on Quadrilaterals

In this paper, we prove the Erdős–Faudree’s conjecture: If G is a graph of order 4k and the minimum degree of G is at least 2k then G contains k disjoint cycles of length 4.     

A General Darling–Erdős Theorem in Euclidean Space

We provide an improved version of the Darling–Erd?s theorem for sums of i.i.d. random variables with mean zero and finite variance. We extend this result to multidimensional random vectors. Our proof is based on a new strong invariance principle in this setting which has other applications as well such as an integral test refinement of the multidimensional Hartman–Wintner LIL. We also identify a borderline situation where one has weak convergence to a shifted version of the standard limiting distribution in the classical Darling–Erd?s theorem.     

An Erdős–Fuchs theorem for ordered representation functions

The Ramanujan Journal - Let $$k\ge 2$$ be a positive integer. We study concentration results for the ordered representation functions $$r^{{ \le }}_k({\mathcal {A}},n) = \# \big \{ (a_1 \le \dots...     

Phase transitions for modified Erdős–Rényi processes

A fundamental and very well studied region of the Erdős–Rényi process is the phase transition at m∼n/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman–Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.     

Asymptotics for Erdős–Solovej Zero Modes in Strong Fields

We consider the strong field asymptotics for the occurrence of zero modes of certain Weyl–Dirac operators on \({\mathbb{R}^3}\). In particular, we are interested in those operators \({\mathcal{D}_B}\) for which the associated magnetic field \({B}\) is given by pulling back a two-form \({\beta}\) from the sphere \({\mathbb{S}^2}\) to \({\mathbb{R}^3}\) using a combination of the Hopf fibration and inverse stereographic projection. If \({\int_{\mathbb{s}^2} \beta \neq 0}\), we show that

$$\sum_{0 \leq t \leq T} {\rm dim Ker} \mathcal{D}{tB}=\frac{T^2}{8\pi^2}\,\Big| \int_{\mathbb{S}^2}\beta\Big|\,\int_{\mathbb{S}^2}|{\beta}| +o(T^2)$$

as \({T\to+\infty}\). The result relies on Erd?s and Solovej’s characterisation of the spectrum of \({\mathcal{D}_{tB}}\) in terms of a family of Dirac operators on \({\mathbb{S}^2}\), together with information about the strong field localisation of the Aharonov–Casher zero modes of the latter.

     

The Erdős–Pósa Property For Long Circuits

We show that, for every l, the family of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk²).