×

Distance Ramsey numbers. (English. Russian original) Zbl 1270.05066

Dokl. Math. 87, No. 2, 171-174 (2013); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk, Vol. 449, No. 3, 267-270 (2013).
A graph is a distance graph in \(R^d,\) the \(d\)-dimension Euclidean space, if its vertices can be associated with different points of \(R^d\) such that any pair of adjacent vertices of such a graph corresponds to a pair of points a unit distance apart.
This paper studies the distance Ramsey number, \(R_{\text{NEH}}(s, t, d),\) i.e., the minimum positive number \(R\) such that, for any graph \(G\) on \(R\) vertices, either the graph itself contains an induced \(s\)-vertex subgraph isomorphic to a distance graph in \(R^d\) or the complement of the graph contains an induced \(t\)-vertex subgraph isomorphic to a distance graph in \(R^d.\)
The central result as reported in this paper is a tighter lower bound of the distance Ramsey number for a fixed \(d\) as follows: for \(d\geq 4\) and \(\gamma>0,\) there exists \(s_0=s_0(d, \gamma)\) such that for all \(s \geq s_0,\) \[ R_{\text{NEH}}(s, s, d) \geq 2^{\left (\frac{1}{2 [d/2]}-\gamma \right )s}. \]
Clearly, the gist of showing \(R_{\text{NEH}}(s, s, d)>n\) is to demonstrate the existence of an \(n\)-vertex graph \(G\) such that no \(s\)-vertex induced subgraph of \(G\) and its complement is isomorphic to a distance graph in \(R^d.\) This task is accomplished in this paper by showing that, for all sufficiently large \(s,\) there is an \(n\)-vertex graph \(G\) such that the number of \(k\)-cliques, where \(k=\left [ \frac{d}{2} \right ]+1,\) in any of the \(s\)-vertex induced subgraphs of both \(G\) and its complement exceeds \(s^{k-\epsilon},\) where \(\epsilon\) depends only on \(d.\) This is naturally done following a probabilistic approach, making use of the classical Erdős-Rényi model \(G(n, \frac{1}{2}).\)

MSC:

05C55 Generalized Ramsey theory
05C12 Distance in graphs
05D10 Ramsey theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ramsey, F. P., No article title, Proc. London Math. Soc. Ser. 2, 30, 264-286 (1930) · JFM 55.0032.04 · doi:10.1112/plms/s2-30.1.264
[2] R. L. Graham, B. K. Rothschild, and J. H. Spencer, Ramsey Theory (Wiley, New York, 1990). · Zbl 0705.05061
[3] ErdΩ, P., No article title, Am. Math. Monthly, 53, 248-250 (1946) · Zbl 0060.34805 · doi:10.2307/2305092
[4] Raigorodskii, A. M., No article title, Russ. Math. Surv., 56, 103-139 (2001) · Zbl 1008.54018 · doi:10.1070/RM2001v056n01ABEH000358
[5] F. Harary, Graph Theory (Addison-Wesley, Reading, Mass., 1969; Mir, Moscow, 1973). · Zbl 0182.57702
[6] Bruijn, N. G.; ErdΩ, P., No article title, Proc. Koninkl. Nederl. Acad. Wet. Ser. A, 54, 371-373 (1951)
[7] P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry (Springer, Berlin, 2005). · Zbl 1086.52001
[8] N. Alon and J. Spencer, The Probabilistic Method (Wiley, New York, 2002). · Zbl 1333.05001
[9] Conlon, D., No article title, Ann. Math., 170, 941-960 (2009) · Zbl 1188.05087 · doi:10.4007/annals.2009.170.941
[10] Raigorodskii, A. M., No article title, Dokl. Math., 75, 221-223 (2007) · Zbl 1175.05139 · doi:10.1134/S1064562407020123
[11] Raigorodskii, A. M.; Titova, M. V., No article title, Sovrem. Mat. Ee Prim., 20, 75-83 (2011)
[12] Kupavskii, A. B.; Raigorodskii, A. M.; Titova, M. V., No article title, Tr. Mosk. Fiz. Tekh. Inst., 4, 111-121 (2012)
[13] ErdΩ, P., No article title, Isr. J. Math., 2, 183-190 (1964) · Zbl 0129.39905 · doi:10.1007/BF02759942
[14] Räul, V., No article title, Eur. J. Combin., 6, 69-78 (1985)
[15] ErdΩ, P.; Kleitman, D. J.; Rothschild, B. L., Asymptotic Enumeration of Kn-Free Graphs, 19-27 (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.