Induced Ramsey-type theorems

We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Erd?s-Hajnal, Prömel-Rödl, Nikiforov, Chung-Graham, and ?uczak-Rödl. The proofs are based on a simple lemma (generalizing one by Graham, Rödl, and Ruciński) that can be used as a replacement for Szemerédi's regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.     

Some Ramsey-type theorems for countably determined sets

 Let X be an infinite internal set in an ω¹-saturated nonstandard universe. Then for any coloring of [X] ^k , such that the equivalence E of having the same color is countably determined and there is no infinite internal subset of [X] ^k with all its elements of different colors (i.e., E is condensating on X), there exists an infinite internal set Z⊆X such that all the sets in [Z] ^k have the same color. This Ramsey-type result is obtained as a consequence of a more general one, asserting the existence of infinite internal Q-homogeneous sets for certain Q ⊆ [[X] ^k ] ^m , with arbitrary standard k≥ 1, m≥ 2. In the course of the proof certain minimal condensating countably determined sets will be described. Received: 17 October 2000 / Published online: 12 July 2002     

Density theorems for bipartite graphs and related Ramsey-type results

In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in graph Ramsey theory and improve and generalize earlier results of various researchers. The proofs combine probabilistic arguments with some combinatorial ideas. In addition, these techniques can be used to study properties of graphs with a forbidden induced subgraph, edge intersection patterns in topological graphs, and to obtain several other Ramsey-type statements. Research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Research supported in part by NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.     

Induced restricted Ramsey theorems for spaces

The induced restricted versions of the vector space Ramsey theorem and of the Graham-Rothschild parameter set theorem are proved.     

Ramsey-type constructions for arrangements of segments

Improving a result of Károlyi, Pach and Tóth, we construct an arrangement of n segments in the plane with at most n^log8/log169 pairwise crossing or pairwise disjoint segments. We use the recursive method based on flattenable arrangements which was established by Larman, Matoušek, Pach and Tör?csik.     

Ramsey-type results for oriented trees

For a graph G and a digraph (RIGHT ARROW ABOVE H), we write G → (RIGHT ARROW ABOVE H) (respectively, G (A ABOVE RIGHT ARROW)(RIGHT ARROW ABOVE H) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of (RIGHT ARROW ABOVE H). In this note we study how small the graphs G such that G → (RIGHT ARROW ABOVE H) or such that G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE H) may be, if (RIGHT ARROW ABOVE H) is a given oriented tree (RIGHT ARROW ABOVE T)ⁿ on n vertices. We show that there is a graph on O(n⁴ log n) vertices and O(n⁶(log n)²) edges such that G → Tⁿ for every n-vertex oriented tree (RIGHT ARROW ABOVE T)ⁿ. We also prove that there exists a graph G with O(n² log n) vertices and O(n³(log n)²) edges such that G → (RIGHT ARROW ABOVE T)ⁿ for any such tree (RIGHT ARROW ABOVE T)ⁿ. This last result turns out to be nearly best possible as it is shown that any graph G with G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE P)ⁿ, where (RIGHT ARROW ABOVE P)ⁿ is the directed path of order n, has more than n²/2 vertices and more than [n/3]³ edges if n ≥ 3. © 1996, John Wiley & Sons, Inc.     

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 three zero-sum Ramsey-type problems

For a graph G whose number of edges is divisible by k, let R(G,Z_k) denote the minimum integer r such that for every function f: E(K_r) ? Z_k there is a copy G¹ of G in K_r so that Σe∈E(G¹) f(e) = 0 (in Z_k). We prove that for every integer k₁ R(K_n, Z_k) ≤ n + O(k³ log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(K_n, Z_k) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z₂) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.     

A Ramsey-type theorem for traceable graphs

A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to K_ω,ω. The versions of these results for finite graphs are discussed.     

Resolving Singularities in a Ramsey-type Growth Model

The aim of this paper is to discuss a mathematical solution procedure to solve a Ramsay-type growth model that explains the fundamentals of consumption and capital accumula-tion in a dynamic equilibrium setting. The problem is formulated as a system of recursive equations and studied through some numerical experiments for the time path of the different variables of the model under some alternative assumption for the steady-state equilibrium of the labour market conditioning the possible singularity of the model.     

A Ramsey-type problem on right-angled triangles in space

It is proved that for any 3-coloring of R³ and for any right-angled triangle T, one can find a congruent copy of T, all of whose vertices are of the same color.     

Ultrafilters and Ramsey-type shadowing phenomena in topological dynamics

The graded exponent is an important invariant of group graded PI-algebras. In this paper we study a specific elementary grading on the algebra of upper triangular matrices UT _n , compute its codimensions, and use this grading to find the asymptotic behaviour of the codimensions of any elementary grading on UT _n , for any group. Moreover, we extend this to the Lie case, and obtain, for any elementary grading on the Lie algebra UT_n^(?), an upper bound and a lower bound for the asymptotic behaviour of its codimensions. Also, we obtain the graded exponent of any grading on UT_n^(?) and for any grading on the Jordan algebra UJ _n .It turns out that the graded exponent for UT _n , considered as an associative, Jordan or Lie algebra, for any grading, coincides with the exponent of the ordinary case. In the associative case, the asymptotic behaviour of the codimensions of any grading on UT _n coincides with the asymptotic behaviour of the ordinary codimensions. But this is not the case for the graded asymptotics of the codimensions of the Lie algebra UT_n^(?).     

Path-path Ramsey-type numbers for the complete bipartite graph

For a fixed pair of integers r, s ≥ 2, all positive integers m and n are determined which have the property that if the edges of K_m,n (a complete bipartite graph with parts n and m) are colored with two colors, then there will always exist a path with r vertices in the first color or a path with s vertices in the second color.     

Some Ramsey-type results for the n-cube

In this note we establish a Ramsey-type result for certain subsets of the n-dimensional cube. This can then be applied to obtain reasonable bounds on various related structures, such as (partial) Hales-Jewett lines for alphabets of sizes 3 and 4, Hilbert cubes in sets of real numbers with small sumsets, “corners” in the integer lattice in the plane, and 3-term integer geometric progressions.