×

On random subgraphs of Kneser and Schrijver graphs. (English) Zbl 1334.05158

Summary: A Kneser graph \({\mathrm{KG}}_{n,k}\) is a graph whose vertices are in one-to-one correspondence with \(k\)-element subsets of \([n]\), with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to L. Lovász [ibid. 25, 319–324 (1978; Zbl 0418.05028)] states that the chromatic number of a Kneser graph \({{\mathrm{KG}}}_{n,k}\) is equal to \(n-2k+2\). In this paper we study the chromatic number of a random subgraph of a Kneser graph \({\mathrm{KG}}_{n,k}\) as \(n\) grows. A random subgraph \({{\mathrm{KG}}}_{n, k}(p)\) is obtained by including each edge of \({{\mathrm{KG}}}_{n, k}\) with probability \(p\). For a wide range of parameters \(k = k(n)\), \(p = p(n)\) we show that \(\chi({\mathrm{KG}}_{n,k}(p))\) is very close to \(\chi({{\mathrm{KG}}}_{n, k})\), w.h.p. differing by at most 4 in many cases. Moreover, we obtain the same bounds on the chromatic numbers for the so-called Schrijver graphs, which are known to be vertex-critical induced subgraphs of Kneser graphs.

MSC:

05C80 Random graphs (graph-theoretic aspects)

Citations:

Zbl 0418.05028
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Frankl, P.; Lovász, L., The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc., 298, 1, 359-370 (1986) · Zbl 0605.05033
[2] Alon, N.; Spencer, J., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization (2000)
[4] Bárány, I., A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A, 25, 3, 325-326 (1978) · Zbl 0404.05028
[5] Bogolyubskiy, L. I.; Gusev, A. S.; Pyaderkin, M. M.; Raigorodskii, A. M., Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs, Dokl. Math., 457, 383-387 (2014)
[6] Bogolyubskiy, L. I.; Gusev, A. S.; Pyaderkin, M. M.; Raigorodskii, A. M., Independence numbers and chromatic numbers of the random subgraphs of some distance graphs, Sbornik: Mathematics, 206, 10, 1340 (2015) · Zbl 1331.05191
[7] Bollobás, B., Random Graphs (2001), Cambridge University Press · Zbl 0979.05003
[8] Bollobás, B.; Narayanan, B. P.; Raigorodskii, A. M., On the stability of the Erdős-Ko-Rado theorem · Zbl 1325.05145
[9] Dol’nikov, V. L., Transversals of families of sets, (Studies in the Theory of Functions of Several Real Variables (1981), Yaroslav. Gos. Univ.: Yaroslav. Gos. Univ. Yaroslavl’), 30-36, (in Russian) · Zbl 0488.52004
[10] Greene, J. E., A new short proof of Kneser’s conjecture, Amer. Math. Monthly, 109, 10, 918-920 (2002) · Zbl 1023.05014
[11] Kneser, M., Aufgabe 360, Jahresber. Dtsch. Math.-Ver., 2, 27 (1955)
[12] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028
[13] Matoušek, J., Using the Borsuk-Ulam Theorem (2003), Springer
[14] Rödl, V.; Schacht, M., Extremal results in random graphs, (Erdős Centennial (2013), Springer) · Zbl 1304.05125
[15] Schrijver, A., Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wiskd., III. Ser., 26, 454-461 (1978) · Zbl 0432.05026
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.