Graphs having circuits with at least two chords

All 2-connected non-bipartite graphs are characterized which have a minimal valency ≥3 and which have no odd circuit with two or more chords. From this it is derived that in each graph with chromatic number ≥4 containing no complete 4-graph there is an odd circuit with two or more chords. This result was conjectured by P. Erdös. Corresponding results for even circuits and for circuits with a fixed edge are obtained. Some related problems of the Turán type are solved.     

Construction of sets of positive measure not containing an affine image of a given infinite structure

This paper deals with the problem of existence of infinite structures in euclidean space such that every set of positive measure contains an affine image of it. We contribute to P. Erdös’ question about sequences in the real line, by showing that no triple sum of infinite sets has this property.     

On maximal circuits in directed graphs

An exact bound is obtained for the number of edges in a directed graph which ensures the existence of a circuit exceeding a prescribed length.Another proof of an analogous result of Erdös and Gallai for undirected graphs is supplied in the Appendix.     

Definable Ramsey and definable Erdös ordinals

This paper studies the relation between definable Ramsey ordinals and constructible sets which have a certain set of indiscernibles. It is shown that an ordinal κ is Σ₁-Ramsey if and only if κ is ∑_ω-Ramsey. Similar results are obtained for definable Erdös ordinals.     

On coloring graphs with locally small chromatic number

In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc _k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc _k n ^1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc _k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.     

Representing powers of 2 by a sum of four integers

We solve an arithmetic problem due to Erdös and Freud (1986) investigated also by Freiman, Nathanson and Sárközy: How many elements from a given set of integers one must take to represent a power of 2 by their sum?     

Monotone additive functions on shifted primes

Generalising a sixty year old result of Erdös, it is proved that an additive arithmetic function that is non-decreasing on the shifted primes is essentially a logarithm.     

Function solutions to certain Diophantine equations

We investigate whether certain Diophantine equations have or have not solutions in entire or meromorphic functions defined on a non-Archimedean algebraically closed field of characteristic zero. We prove that there are no non-constant meromorphic functions solving the Erdös–Selfridge equation except when the corresponding curve is a conic. We also show that there are infinitely many non-constant entire solutions to the Markoff–Hurwitz equation.     

On cross-bandwidth

The notion of cross-bandwidth is introduced, and it is shown that any graph that is suitably contractible to a k-connected graph has cross-bandwidth at least k. The contracted edges must induce in the original graph a subgraph of maximum degree at most one. This is used to resolve a conjecture of Erdös and Chinn on the bandwidth of certain graphs.     

The maximum number of disjoint pairs in a family of subsets

Let ? be a family of 2 ⁿ⁺¹ subsets of a 2n-element set. Then the number of disjoint pairs in ? is bounded by (1+o(1))2²ⁿ . This proves an old conjecture of Erdös. Let ? be a family of 2^1/(k+1)+δ)n subsets of ann-element set. Then the number of containments in ? is bounded by (1-1/k+o(1))( ₂ ^|?| ). This verifies a conjecture of Daykin and Erdös. A similar Erdös-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets.     

Length and denominators of Egyptian fractions

We say that an algorithm which could yield a short unit fraction expansion in which the denominators do not get too large is an ideal expansion. It is shown that Bleicher and Erdös algorithm can be modified to be an ideal algorithm.     

On the number of unique subgraphs of a graph

A question of Entringer and Erdös concerning the number of unique subgraphs of a graph is answered.     

Statistics and characterization of matrices by determinant and trace

The Ramanujan Journal - Answering a question of Erdös, Komlós proved in 1968 that almost all $$n\times n$$ Bernoulli matrices are nonsingular as $$n\rightarrow \infty $$ . In this paper,...     

On Substructure Densities of Hypergraphs

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.     

Functional Erdös-Rényi laws for processes indexed by sets

We consider a process X(A) indexed by some sets A∈A, where A is a collection of sets. We prove a functional form of the Erdös-Rényi laws. The result may be specialized to get back and sometimes improve previous versions of the classical Erdös-Rényi laws.     

A canonical partition relation for finite subsets of ω

We prove a canonical partition relation for finite subsets of ω that generalizes Hindman's theorem in much the same way that the Erdös-Rado canonical partition relation generalizes Ramsey's theorem. As an application of this we establish a generalized pigeon-hole principle for infinite dimensional vector spaces over the two element field.     

Cooperation in changing environments: Irreversibility in the transition to cooperation in complex networks

In the framework of the evolutionary dynamics of the Prisoner’s Dilemma game on complex networks, we investigate the possibility that the average level of cooperation shows hysteresis under quasi-static variations of a model parameter (the “temptation to defect”). Under the “discrete replicator” strategy updating rule, for both Erdös–Rényi and Barabási–Albert graphs we observe cooperation hysteresis cycles provided one reaches tipping point values of the parameter; otherwise, perfect reversibility is obtained. The selective fixation of cooperation at certain nodes and its organization in cooperator clusters, that are surrounded by fluctuating strategists, allows the rationalization of the “lagging behind” behavior observed.     

On a theorem of de Bruijn and Erdös

A theorem of de Bruijn and Erdös [2] asserts that every finite geometry (see section 1 for definition) has at least as many lines as points. The present paper uses linear algebra as a technique to establish the de Bruijn-Erdös result and a particular higher dimensional generalization. These results are special cases of theorems due to Basterfield and Kelly [1] and Green [3].     

Integers with consecutive divisors in small ratio

An elementary construction of a sequence of positive integers is given. The sequence settles a question of Erdös concerning integers with consecutive divisors in small ratio.     

Sperner's theorem on maximal-sized antichains and its generalization

This paper generalizes previous work by Sperner [8], Erdös [2], Kleitman [5], Katona [3], DeBruijn et al. [1], and Schönheim [7]. Such generalization not only leads to simple proofs of known results but also sharpens some of these results.