共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
Let X be an infinite internal set in an ω1-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 相似文献
3.
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. 相似文献
4.
5.
6.
《Journal of Combinatorial Theory, Series A》1987,44(1):120-128
The induced restricted versions of the vector space Ramsey theorem and of the Graham-Rothschild parameter set theorem are proved. 相似文献
7.
8.
9.
10.
Jan Kyn?l 《European Journal of Combinatorics》2012,33(3):336-339
Improving a result of Károlyi, Pach and Tóth, we construct an arrangement of n segments in the plane with at most nlog8/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. 相似文献
11.
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)n on n vertices. We show that there is a graph on O(n4 log n) vertices and O(n6(log n)2) edges such that G → Tn for every n-vertex oriented tree (RIGHT ARROW ABOVE T)n. We also prove that there exists a graph G with O(n2 log n) vertices and O(n3(log n)2) edges such that G → (RIGHT ARROW ABOVE T)n for any such tree (RIGHT ARROW ABOVE T)n. 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)n, where (RIGHT ARROW ABOVE P)n is the directed path of order n, has more than n2/2 vertices and more than [n/3]3 edges if n ≥ 3. © 1996, John Wiley & Sons, Inc. 相似文献
12.
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. 相似文献
13.
For a graph G whose number of edges is divisible by k, let R(G,Zk) denote the minimum integer r such that for every function f: E(Kr) ? Zk there is a copy G1 of G in Kr so that Σe∈E(G1) f(e) = 0 (in Zk). We prove that for every integer k1 R(Kn, Zk) ≤ n + O(k3 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(Kn, Zk) ≤ 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,Z2) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc. 相似文献
14.
15.
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. 相似文献
16.
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. 相似文献
17.
It is proved that for any 3-coloring of R3 and for any right-angled triangle T, one can find a congruent copy of T, all of whose vertices are of the same color. 相似文献
18.
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 UTn(?), an upper bound and a lower bound for the asymptotic behaviour of its codimensions. Also, we obtain the graded exponent of any grading on UTn(?) 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 UTn(?). 相似文献
19.
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 Km,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. 相似文献
20.
Ron Graham 《Journal of Combinatorial Theory, Series A》2010,117(2):189-195
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. 相似文献