Ramsey-goodness—and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r _Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r _Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r _Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r _Δ > 2 ^cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r _Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P _n ^k , the kth power of a path P _n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K ₃) > cn. We show that, given Δ and H, there are β>0 and n ₀ such that, if G is a connected graph on n≥n ₀ vertices with maximum degree at most Δ and bandwidth at most β _n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn.     

Two remarks on the Burr–Erdős conjecture

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 K_N 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 c_d such that r(H)≤c_dn 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.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

Decomposition of the completer-graph into completer-partiter-graphs

Forn ≥ r ≥ 1, letf _r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf ₂(n) =n ? 1. Here we observe thatf ₃(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc ₁(r) andc ₂(r) such thatc ₁(r) ≤f _r (n)?n ^?[r/2] ≤n ₂(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

Elliptic equation with a singular potential in a domain with a conic point

This paper deals with the behavior of the nonnegative solutions of the problem $$- \Delta u = V(x)u, \left. u \right|\partial \Omega = \varphi (x)$$ in a conical domain Ω ? ? ⁿ , n ≥ 3, where 0 ≤ V (x) ∈ L₁(Ω), 0 ≤ ?(x) ∈ L₁(?Ω) and ?(x) is continuous on the boundary ?Ω. It is proved that there exists a constant C _*(n) = (n ? 2)²/4 such that if V ₀(x) = (c + λ ₁)|x|^?2, then, for 0 ≤ c ≤ C _*(n) and V(x) ≤ V ₀(x) in the domain Ω, this problem has a nonnegative solution for any nonnegative boundary function ?(x) ∈ L ₁(?Ω); for c > C _*(n) and V(x) ≥ V ₀(x) in Ω, this problem has no nonnegative solutions if ?(x) > 0.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

The smallestn-uniform hypergraph with positive discrepancy

A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd?s and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc ₁ andc ₂ such that $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ where snd(x) is the least positive integer that does not dividex.     

On conjugate characteristic polynomial of a graph

Let $c=a+b\sqrt{m}$ and $\overline{c}=a-b\sqrt{m}$ , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A ^c =[c _ij ] is the conjugate adjacency matrix of a graph G if c _ij =c for any two adjacent vertices i and j, $c_{ij}=\overline{c}$ for any two nonadjacent vertices i and j, and c _ij =0 if i=j. Let P _G ^c (λ)=|λ I?A ^c | denote the conjugate characteristic polynomial of G. Further, let e=e(G) and Δ=Δ(G) be the number of edges and number of triangles of G, respectively. Let G and H be two graphs of order n and let e(G)=e(H). In this work we prove that c ₃(G)=c ₃(H) if and only if Δ(G)=Δ(H) and $\Delta(\overline{G})=\Delta(\overline{H})$ , where $\overline{G}$ denotes the complement of G and c _k is the coefficient which corresponds to λ ^n?k with respect to P _G ^c (λ). Besides, we here give the conjugate spectrum and conjugate characteristic polynomial of all connected graphs of order n=2,3,4,5, with respect to the constant $c=1+\sqrt{2}$ .     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

Graphs with certain families of spanning trees

Sufficient conditions are given in terms of δ(G) and Δ(T), for a graph G with n vertices to contain a tree T with n vertices. One of these sufficient conditions is used to calculate some of the Ramsey numbers for the pair tree-star. Also necessary conditions are given, in terms of δ(G), for a graph G with n vertices to contain all trees with n vertices.     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

The connected Ramsey number

A graph G is totally connected if both G and ? (its complement) are connected. The connected Ramsey number r_c(F, H) is the smallest integer k ? 4 so that if G is a totally connected graph of order k then either F ? G or H ? ?. We show that if neither of F nor H contains a bridge, then r_c = r(F, H), the usual generalized Ramsey number of F and H. We compute r_c (P_mP_m), the connected Ramsey number for paths.     

A note on constructive methods for ramsey numbers

Let r(k) denote the least integer n-such that for any graph G on n vertices either G or its complement G contains a complete graph K_k on k vertices. in this paper, we prove the following lower bound for the Ramsey number r(k) by explicit construction: r(k) ≥ exp (c(Log k)^4/3[(log log k)^1/3] for some constant c> 0.     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.