Erdős measures,sofic measures,and Markov chains

We consider the random variable ζ = ξ₁ρ+ξ₂ρ²+…, where ξ₁, ξ₂, … are independent identically distibuted random variables taking the values 0 and 1 with probabilities P(ξ_i = 0) = p₀, P(ξ_i = 1) = p₁, 0 < p₀ < 1. Let β = 1/ρ be the golden number. The Fibonacci expansion for a random point ρζ from [0, 1] is of the form η₁ρ + η₂ρ² + … where the random variables η_k are {0, 1}-valued and η_kη_k+1 = 0. The infinite random word η = η₁η₂ … η_n … takes values in the Fibonacci compactum and determines the so-called Erdős measure μ(A) = P(η ∈ A) on it. The invariant Erdős measure is the shift-invariant measure with respect to which the Erdős measure is absolutely continuous. We show that the Erdős measures are sofic. Recall that a sofic system is a symbolic system that is a continuous factor of a topological Markov chain. A sofic measure is a one-block (or symbol-to-symbol) factor of the measure corresponding to a homogeneous Markov chain. For the Erdős measures, the corresponding regular Markov chain has 5 states. This gives ergodic properties of the invariant Erdős measure. We give a new ergodic theory proof of the singularity of the distribution of the random variable ζ. Our method is also applicable when ξ₁, ξ₂, … is a stationary Markov chain with values 0, 1. In particular, we prove that the distribution of ζ is singular and that the Erdős measures appear as the result of gluing together states in a regular Markov chain with 7 states. Bibliography: 3 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 28–47.     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

Mangoes and Blueberries

Dedicated to the memory of Paul Erdős We prove the following conjecture of Erdős and Hajnal: For every integer k there is an f(k) such that if for a graph G, every subgraph H of G has a stable set containing vertices, then G contains a set X of at most f(k) vertices such that G−X is bipartite. This conjecture was related to me by Paul Erdős at a conference held in Annecy during July of 1996. I regret not being able to share the answer with him. Received: August 20, 1997     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

Probabilistic constructions of B 2[g] sequences

We use the probabilistic method to prove that for any positive integer g there exists an infinite B2[g] sequence A = {ak} such that ak ≤ k^2＋1/g（log k）^1/g＋0（1） as k→∞. The exponent 2＋1/g improves the previous one, 2 ＋ 2/g, obtained by Erdos and Renyi in 1960. We obtain a similar result for B2 [g] sequences of squares.     

The Erdős-Heilbronn problem in Abelian groups

Solving a problem of Erdős and Heilbronn, in 1994 Dias da Silva and Hamidoune proved that ifA is a set ofk residues modulo a primep,p≥2k−3, then the number of different elements of ℤ/pℤ that can be written in the forma+a′ wherea, a′ ∈A,a∈a′, is at least 2k−3. Here we extend this result to arbitrary Abelian groups in which the order of any nonzero element is at least 2k−3. Visiting the Rényi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research Grants OTKA T043623 and T043631 and the CRM, University of Montreal.     

Five consecutive positive odd numbers none of which can be expressed as a sum of two prime powers II

In this paper, we find two integers k0, m of 159 decimal digits such that if k ≡ k0 （mod m）, then none of five consecutive odd numbers k, k - 2, k - 4, k - 6 and k - 8 can be expressed in the form 2^n ± p^α, where p is a prime and n, α are nonnegative integers.     

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.     

An inverse theorem for the restricted set addition in Abelian groups

Let A be a set of k5 elements of an Abelian group G in which the order of the smallest nonzero subgroup is larger than 2k−3. Then the number of different elements of G that can be written in the form a+a^′, where a,a^′A, a≠a^′, is at least 2k−3, as it has been shown in [Gy. Károlyi, The Erdős–Heilbronn problem in Abelian groups, Israel J. Math. 139 (2004) 349–359]. Here we prove that the bound is attained if and only if the elements of A form an arithmetic progression in G, thus completing the solution of a problem of Erdős and Heilbronn. The proof is based on the so-called ‘Combinatorial Nullstellensatz.’     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

Additive Completion of Lacunary Sequences

To the memory of Pál Erdős Thirty years ago I read the following question of Erdőos [4]: "Does there exist a sequence with so that every sufficiently large number is of the form ? $10" I sent my solution to Erdős in a letter (in Hungarian). He translated my letter into English and sent it to the Canadian Math. Bulletin; this became my first paper to appear. In this paper we will find, among others, the best value of the constant c in the above question, which was also asked by Erdős. Received March 30, 2000 RID="*" ID="*" Supported by Hungarian National Foundation for Scientific Research, Grants No. T 025617 and T 29759.     

Disjoint cycles in digraphs

We show that, for each natural numberk, these exists a (smallest) natural numberf(k) such that any digraph of minimum outdegree at leastf(k) containsk disjoint cycles. We conjecture thatf(k)=2k−1 and verify this fork=2 and we show that, for eachk≧3, the determination off(k) is a finite problem. Dedicated to Paul Erdős on his seventieth birthday     

Packing nearly-disjoint sets

De Bruijn and Erdős proved that ifA ₁, ...,A _k are distinct subsets of a set of cardinalityn, and |A _i ∩A _j |≦1 for 1≦i<j ≦k, andk>n, then some two ofA ₁, ...,A _k have empty intersection. We prove a strengthening, that at leastk /n ofA ₁, ...,A _k are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary. Partially supported by N. S. F. grant No. MCS—8103440     

Independent sets ink-chromatic graphs

A graph is said to have propertyP _k if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP _k . With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP _k orP _k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP _k or is a circuit of length 7. Dedicated to Paul Erdős on his seventieth birthday     

Alternating group covers of the affine line

For an odd prime p t= 2 mod 3, we prove Abhyankar’s Inertia Conjecture for the alternating group A _p+2, by showing that every possible inertia group occurs for a (wildly ramified) A _p+2-Galois cover of the projective k-line branched only at infinity where k is an algebraically closed field of characteristic p > 0. More generally, when 2 ≤ s < p and gcd(p−1, s+1) = 1, we prove that all but finitely many rational numbers which satisfy the obvious necessary conditions occur as the upper jump in the filtration of higher ramification groups of an A _p+s -Galois cover of the projective line branched only at infinity.     

Zero-sum problems for abelian <Emphasis Type="Italic">p</Emphasis>-groups and covers of the integers by residue classes

Zero-sum problems for abelian groups and covers of the integers by residue classes, are two different active topics initiated by P. Erdős more than 40 years ago and investigated by many researchers separately since then. In an earlier announcement [S03b], the author claimed some surprising connections among these seemingly unrelated fascinating areas. In this paper we establish further connections between zero-sum problems for abelian p-groups and covers of the integers. For example, we extend the famous Erdős-Ginzburg-Ziv theorem in the following way: If { a _s (mod n_s)}_s=1^k covers each integer either exactly 2q − 1 times or exactly 2q times where q is a prime power, then for any c ₁,...,c _k ∈ ℤ/qℤ there exists an I ⊆ {1,...,k} such that ∑ _s∈I 1/n _s = q and ∑ _s∈I c _s = 0. The main theorem of this paper unifies many results in the two realms and also implies an extension of the Alon-Friedland-Kalai result on regular subgraphs. The author is supported by the National Science Foundation (grant 10871087) of China.     

Point Sets with Many k -Sets

For any n , k , n\geq 2k>0 , we construct a set of n points in the plane with k -sets. This improves the bounds of Erdős, Lovász, et al. As a consequence, we also improve the lower bound for the number of halving hyperplanes in higher dimensions. Received September 10, 1999, and in revised form January 27, 2000.     

Some geometric applications of Dilworth’s theorem

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are collinear. We settle an old question of Avital, Hanani, Erdős, Kupitz, and Perles by showing that every geometric graph withn vertices andm>k ⁴ n edges containsk+1 pairwise disjoint edges. We also prove that, given a set of pointsV and a set of axis-parallel rectangles in the plane, then either there arek+1 rectangles such that no point ofV belongs to more than one of them, or we can find an at most 2·10⁵ k ⁸ element subset ofV meeting all rectangles. This improves a result of Ding, Seymour, and Winkler. Both proofs are based on Dilworth’s theorem on partially ordered sets. The research by János Pach was supported by Hungarian National Foundation for Scientific Research Grant OTKA-4269 and NSF Grant CCR-91-22103.     

On the threshold for k-regular subgraphs of random graphs

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor.