×

Stable sets of maximal size in Kneser-type graphs. (English) Zbl 1048.05078

Summary: We introduce a family of vertex-transitive graphs with specified subgroups of automorphisms which generalise Kneser graphs, powers of complete graphs and Cayley graphs of permutations. We compute the stability ratio for a wide class of these. Under certain conditions we characterise their stable sets of maximal size.

MSC:

05D05 Extremal set theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Dinur, I.; Friedgut, E.; Sudakov, B., Graph Products, Fourier Analysis and Spectral Techniques (2003), p. 22 (preprint) · Zbl 1056.05104
[2] Albertson, M. O.; Collins, K. L., Homomorphisms of 3-chromatic graphs, Discrete Math., 54, 127-132 (1985) · Zbl 0572.05024
[3] Bollobás, B., Combinatorics, Set Systems, Hypergraphs, Hamilies of Vectors and Combinatorial Probability (1986), Cambridge University Press
[4] Cameron, P. J.; Ku, C. Y., Intersecting families of permutations, European J. Combin., 24, 881-890 (2003) · Zbl 1026.05001
[5] Deza, M.; Frankl, P., On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A, 22, 352-360 (1977) · Zbl 0352.05003
[6] M. Deza, P. Frankl, Problem, in: Combinatorics, Coll. Math. Soc. János. Bolyai, North-Holland, Amsterdam, 18 (1978) p. 1193; M. Deza, P. Frankl, Problem, in: Combinatorics, Coll. Math. Soc. János. Bolyai, North-Holland, Amsterdam, 18 (1978) p. 1193
[7] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), 12, 313-318 (1961) · Zbl 0100.01902
[8] Godsil, C.; Royle, G., Algebraic Graph Theory, Graduate Texts in Mathematics (2001), Springer: Springer New York, Berlin, Heidelberg · Zbl 0968.05002
[9] Greenwell, D.; Lovász, L., Applications of product colouring, Acta Math. Acad. Sci. Hungar., 25, 335-340 (1974) · Zbl 0294.05108
[10] Hilton, A. J.W.; Milner, E. C., Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), 18, 369-384 (1967) · Zbl 0168.26205
[11] M. Kneser, Aufgabe 360, Jahresbes Deutsch. Math.—Verein 58(2 Abt.) p. 27 (1955); M. Kneser, Aufgabe 360, Jahresbes Deutsch. Math.—Verein 58(2 Abt.) p. 27 (1955)
[12] B. Larose, Some results on stable sets of maximal size in vertex-transitive graphs (in preparation); B. Larose, Some results on stable sets of maximal size in vertex-transitive graphs (in preparation) · JFM 27.0320.04
[13] Larose, B.; Tardif, C., Projectivity and independent sets in powers of graphs, J. Graph Theory, 40, 3, 162-171 (2002) · Zbl 1003.05077
[14] Lovász, L., Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. (A), 25, 319-324 (1978) · Zbl 0418.05028
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.