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     

Another Look at the Erdős–Hajnal–Pósa Results on Partitioning Edges of the Rado Graph

Dedicated to the memory of Paul Erdős Erdős, Hajnal and Pósa exhibited in [1] a partition (U,D) of the edges of the Rado graph which is a counterexample to . They also obtained that if every vertex of a graph has either in or in the complement of finite degree then . We will characterize all graphs so that . Received October 29, 1999 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Subdivisions of a Graph of Maximal Degree n + 1 in Graphs of Average Degree and Large Girth

Dedicated to the memory of Paul Erdős It is proved that for every finite graph H of maximal degree and every , there is an integer such that every finite graph of average degree at least and of girth at least contains a subdivision of H. Received May 5, 1999     

Independence,clique size and maximum degree

It was shown before that ifG is a graph of maximum degreep containing no cliques of the sizeq then the independence ratio is greater than or equal to 2 / (p +q). We shall discuss here some extreme cases of this inequality. Dedicated to Paul Erdős on his seventieth birthday     

On the lattice property of the plane and some problems of Dirac,Motzkin and Erdős in combinatorial geometry

LetS be a set ofn non-collinear points in the Euclidean plane. It will be shown here that for some point ofS the number ofconnecting lines through it exceedsc · n. This gives a partial solution to an old problem of Dirac and Motzkin. We also prove the following conjecture of Erdős: If any straight line contains at mostn−x points ofS, then the number of connecting lines determined byS is greater thanc · x · n. Dedicated to Paul Erdős on his seventieth birthday     

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     

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.     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

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.     

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     

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday     

On Erdős's Eulerian Trail Game

 Paul Erdős proposed the following graph game. Starting with the empty graph on n vertices, two players, Trailmaker and Breaker, draw edges alternatingly. Each edge drawn has to start at the endpoint of the previously drawn edge, so the sequence of edges defines a trail. The game ends when it is impossible to continue the trail, and Trailmaker wins if the trail is eulerian. For all values of n, we determine which player has a winning strategy. Received: November 6, 1996 / Revised: May 2, 1997     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.     

On the density of integers of the form 2 k + p in arithmetic progressions

Consider all the arithmetic progressions of odd numbers, no term of which is of the form 2^k ＋ p, where k is a positive integer and p is an odd prime. ErdSs ever asked whether all these progressions can be obtained from covering congruences. In this paper, we characterize all arithmetic progressions in which there are positive proportion natural numbers that can be expressed in the form 2^k ＋ p, and give a quantitative form of Romanoff＇s theorem on arithmetic progressions. As a corollary, we prove that the answer to the above Erdos problem is affirmative.     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

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     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999