×

zbMATH — the first resource for mathematics

Kneser graphs are like Swiss cheese. (English) Zbl 1404.05088
Summary: We prove that for a large family of product graphs, and for Kneser graphs \(K(n,\alpha n)\) with fixed \(\alpha<1/2\), the following holds. Any set of vertices that spans a small proportion of the edges in the graph can be made independent by removing a small proportion of the vertices of the graph. This allows us to strengthen the results of I. Dinur et al. [Geom. Funct. Anal. 18, No. 1, 77–97 (2008; Zbl 1147.05058)] and I. Dinur and the first author [Comb. Probab. Comput. 18, No. 1–2, 107–122 (2009; Zbl 1243.05235)], and show that any independent set in these graphs is almost contained in an independent set which depends on few coordinates. Our proof is inspired by, and follows some of the main ideas of, J. Fox’s proof of the graph removal lemma [Ann. Math. (2) 174, No. 1, 561–579 (2011; Zbl 1231.05133)].

MSC:
05C35 Extremal problems in graph theory
05D05 Extremal set theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Shagnik Das and Tuan Tran, Removal and stability for Erdős-Ko-Rado, SIAM J. Discrete Math. 30 (2016), no. 2, 1102-1114. MR 3504983 3 · Zbl 1336.05141
[2] Irit Dinur and Ehud Friedgut, Intersecting families are almost contained in juntas, Combinatorics Probability and Computing 18 (2009), no. 1-2, 107-122. 1, 2 · Zbl 1243.05235
[3] Irit Dinur, Ehud Friedgut, and Oded Regev, Independent sets in graph powers are almost contained in juntas, GAFA 18 (2008), no. 1, 77-97. 1, 2, 3, 4, 5, 14, 15, 16
[4] Irit Dinur, Elchanan Mossel, and Oded Regev, Conditional hardness for approximate coloring, SIAM J. Comput. 39 (2009), no. 3, 843-873. MR 2538841 3, 5, 14, 15 · Zbl 1192.68317
[5] Irit Dinur and Igor Shinkar, On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 6302, Springer, Berlin, 2010, pp. 138-151. MR 2755832 14, 15 · Zbl 1304.68060
[6] Jacob Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011), no. 1, 561-579. MR 2811609 (2012j:05224) 1, 2, 5 · Zbl 1231.05133
[7] Pooya Hatami, Sushant Sachdeva, and Madhur Tulsiani, An arithmetic analogue of Fox’s triangle removal argument, Online J. Anal. Comb. (2016), no. 11, Art. 1, 17. MR 3460727 3, 17 · Zbl 1331.05113
[8] Daniel Král’, Oriol Serra, and Lluís Vena, A removal lemma for systems of linear equations over finite fields, Israel J. Math. 187 (2012), 193-207. MR 2891704 3 · Zbl 1306.11012
[9] , On the removal lemma for linear systems over abelian groups, European J. Combin. 34 (2013), no. 2, 248-259. MR 2994398 3
[10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295-341. MR 2630040 3, 5 · Zbl 1201.60031
[11] I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combina-torics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939-945
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.