共查询到20条相似文献,搜索用时 31 毫秒
1.
Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers
2 ≤ s < t let f
s,t
(n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K
s
}}, where the minimum is taken over all K
t
-free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds
is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n
1/2+o(1)) ≤ f
s,s+1(n) ≤ O(n
1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f
s,s+1(n) ≤ O(n
2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n
1/2−ɛ
) ≤ f
s,s+k
(n) ≤ O(n
1/2+ɛ
. In addition, we also discuss some connections between the function f
s,t
and vertex Folkman numbers. 相似文献
2.
Noga Alon Omer Angel Itai Benjamini Eyal Lubetzky 《Israel Journal of Mathematics》2012,188(1):353-384
In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n
1+ɛ
distinct sums of pairs or that many distinct products, and conjectured a lower bound of n
2−o(1). They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given
graph G on n labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least n
1+ɛ
edges. 相似文献
3.
Izolda Gorgol 《Graphs and Combinatorics》2008,24(4):327-331
A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K
n
with no rainbow copy of H. The rainbow number
rb(n, H) is the minimum number of colors such that any edge-coloring of K
n
with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers.
We show that for n ≥ k + 1, where C
k
+ denotes a cycle C
k
with a pendant edge. 相似文献
4.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n). 相似文献
5.
Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK
m
so that everyK
s
⊆K
m
has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
6.
Bruce R 《Combinatorica》1999,19(2):267-296
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 相似文献
7.
The multicolor Ramsey number Rr(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph Kn must result in a monochromatic subgraph of Kn isomorphic to H. It is well known that 2rm<Rr(C2m+1)<2(r+2)!m and Rr(C2m)≥(r−1)(m−1)+1. In this paper, we prove that Rr(C2m)≥2(r−1)(m−1)+2.
This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003) 相似文献
8.
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 相似文献
9.
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. 相似文献
10.
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)−1 for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths. 相似文献
11.
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. 相似文献
12.
Raphael Yuster 《Graphs and Combinatorics》2001,17(3):579-587
We prove that for every ε>0 and positive integer r, there exists Δ0=Δ0(ε) such that if Δ>Δ0 and n>n(Δ,ε,r) then there exists a packing of K
n
with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn
2 edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let αΔ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥αΔ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K
n
).
Received: March 15, 1999?Final version received: October 22, 1999 相似文献
13.
Given graphs H1,…, Hk, let f(H1,…, Hk) be the minimum order of a graph G such that for each i, the induced copies of Hi in G cover V(G). We prove constructively that f(H1, H2) ≤ 2(n(H1) + n(H2) − 2); equality holds when H1 = H 2 = Kn. We prove that f(H1, K n) = n + 2√δ(H1)n + O(1) as n → ∞. We also determine f(K1, m −1, K n) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000 相似文献
14.
The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph KN on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant cd such that r(H)≤cdn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds. 相似文献
15.
V. A. Ustimenko 《Journal of Mathematical Sciences》2007,140(3):461-471
The paper is devoted to the study of a linguistic dynamical system of dimension n ≥ 2 over an arbitrary commutative ring K,
i.e., a family F of nonlinear polynomial maps f
α : K
n
→ K
n
depending on “time” α ∈ {K − 0} such that f
α
−1 = f
−αM, the relation f
α1 (x) = f
α2 (x) for some x ∈ Kn implies α1 = α2, and each map f
α has no invariant points. The neighborhood {f
α (υ)∣α ∈ K − {0}} of an element v determines the graph Γ(F) of the dynamical system on the vertex set Kn. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α1, υ, α2), s ≤ d, where αi + αi+1 is a nonzero divisor for i = 1, υ, d − 1, the vertices υ
a = f
α1 × ⋯ × f
αs
(υ) in the graph are connected by a unique path. For each commutative ring K and each even integer n ≠= 0 mod 3, there is a family of linguistic dynamical systems Ln(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system Ln(q). If K = Fq, the graphs L(n, Fq) form a new family of graphs of large girth. The projective limit L(K) of L(n, K), n → ∞, is well defined for each commutative
ring K; in the case of an integral domain K, the graph L(K) is a forest. If K has zero divisors, then the girth of K drops
to 4. We introduce some other families of graphs of large girth related to the dynamical systems Ln(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric
cryptographic algorithms. These graphs allow us to establish the best known upper bounds on the minimal order of regular graphs
without cycles of length 4n, with odd n ≥ 3. Bibliography: 42 titles.
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 214–234. 相似文献
16.
Guy Wolfovitz 《Combinatorica》2013,33(5):623-631
Let f 3,4(n), for a natural number n, be the largest integer m such that every K 4-free graph of order n contains an induced triangle-free subgraph of order m. We prove that for every suffciently large n, f 3,4(n)≤n 1/2(lnn)120. By known results, this bound is tight up to a polylogarithmic factor. 相似文献
17.
Jeremy Lyle 《Graphs and Combinatorics》2011,27(5):741-754
The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K
r
-free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs Hr{\mathcal{H}_r}, such that if H ? Hr{H \in \mathcal{H}_r}, there exists a constant C < (r − 2)/(r − 1) such that any H-free graph G on n vertices with δ(G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < (r − 2)/(r − 1) is given for every H ? Hr{H \in \mathcal{H}_r}, with particular attention to the case when χ(H) = 3. 相似文献
18.
刘新和 《高校应用数学学报(英文版)》2003,18(2):129-137
§ 1 IntroductionThe Feigenbaum functional equation plays an importantrole in the theory concerninguniversal properties of one-parameter families of maps of the interval that has the formf2 (λx) +λf(x) =0 ,0 <λ=-f(1 ) <1 ,f(0 ) =1 ,(1 .1 )where f is a map ofthe interval[-1 ,1 ] into itself.Lanford[1 ] exhibited a computer-assist-ed proof for the existence of an even analytic solution to Eq.(1 .1 ) .It was shown in[2 ]that Eq.(1 .1 ) does not have an entire solution.Si[3] discussed the it… 相似文献
19.
Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate
the study of the topological properties of this class of complexes.
We prove that Hom(K
m, Kn) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for
some graphG, and integersm≥2 andk≥−1, we have ϖ
1
k
(Hom(K
m, G))≠0, thenχ(G)≥k+m; here ℤ2-action is induced by the swapping of two vertices inK
m, and ϖ1 is the first Stiefel-Whitney class corresponding to this action.
Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K
n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K
n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement.
The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant
PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm. 相似文献
20.
We investigate the growth and the distribution of zeros of rational uniform approximations with numerator degree ≤n and denominator degree ≤m
n
for meromorphic functions f on a compact set E of ℂ where m
n
=o(n/log n) as n→∞. We obtain a Jentzsch–Szegő type result, i.e., the zero distribution converges weakly to the equilibrium distribution of
the maximal Green domain E
ρ(f) of meromorphy of f if f has a singularity of multivalued character on the boundary of E
ρ(f). The paper extends results for polynomial approximation and rational approximation with fixed degree of the denominator.
As applications, Padé approximation and real rational best approximants are considered. 相似文献