On finite simple groups and Kneser graphs
Andrea Lucchini
and Attila Maróti
DOI: 10.1007/s10801-009-0177-0
Abstract
For a finite group G let Γ ( G) be the (simple) graph defined on the elements of G with an edge between two (distinct) vertices if and only if they generate G. The chromatic number of Γ ( G) is considered for various non-solvable groups G.
Pages: 549–566
Keywords: keywords Kneser graph; chromatic number; finite simple group; special linear group; symmetric group
Full Text: PDF
References
1. Blackburn, S.: Sets of permutations that generate the symmetric group pairwise. J. Combin. Theory Ser. A 113(7), 1572-1581 (2006)
2. Bollobás, B.: Erd\Acute\Acute os, P. On the structure of edge graphs. Bull. London Math. Soc. 5, 317-321 (1973)
3. Britnell, J.R., Evseev, A., Guralnick, R.M., Holmes, P.E., Maróti, A.: Sets of elements that pairwise generate a linear group. J. Combin. Theory Ser. A 115(3), 442-465 (2008)
4. Bryce, R.A., Fedri, V., Serena, L.: Subgroup coverings of some linear groups. Bull. Austral Math. Soc. 60(2), 227-238 (1999)
5. Chowdhury, A., Godsil, C., Royle, G.: Colouring lines in projective spaces. J. Combin. Theory Ser. A 113(1), 39-52 (2006)
6. Chvátal, V., Szemerédi, E.: On the Erd\Acute\Acute os-Stone theorem. J. London Math. Soc. 23(2), 207-214 (1981)
7. Damian, E., Lucchini, A.: On the Dirichlet polynomial of finite groups of Lie type. Rend. Sem. Mat. Univ. Padova, vol. 115 (2006)
8. Dickson, L.E.: Linear Groups: With an Exposition of the Galois Field Theory. Dover Publication Inc., New York (1958)
9. Erd\Acute\Acute os, P., Stone, A.: On the structure of linear graphs. Bull. American Math. Soc. 52, 1087-1091 (1946)
10. Frankl, P., Wilson, R.M.: The Erd\Acute\Acute os-Ko-Rado theorem for vector spaces. J. Comb. Theory, Ser. A 43(2), 228-236 (1986)
11. Haxell, P.E.: A condition for matchability in hypergraphs. Graphs and Combinatorics 11, 245-248 (1995)
12. Haxell, P.E.: A note on vertex list colouring. Combin. Probab. Comput. 10(4), 345-347 (2001)
13. Huppert, B., Blackburn, N.: Finite Groups III. Springer, Berlin (1982)
14. Kleidman, P.B.: The maximal subgroups of the Chevalley groups G2(q), with q odd, the Ree groups G2(q2) and their automorphism groups. J. Algebra 117, 30-71 (1988) 2
15. Liebeck, M.W., Shalev, A.: Maximal subgroups of symmetric groups. J. Combin. Theory Ser. A 75, 341-352 (1996)
16. Liebeck, M.W., Shalev, A.: Simple groups, probabilistic methods, and a conjecture of Kantor and Lubotzky. J. Algebra 184(1), 31-57 (1996)
17. Lovász, L.: Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory, Ser. A 25, 319-324 (1978)
18. Lucido, M.S.: On the covers of finite groups. In: Groups St Andrews 2001 in Oxford, Vol. II. London Math. Soc. Lecture Note Ser., vol. 305, pp. 395-399. Cambridge Univ. Press, Cambridge (2003)
19. Lucido, M.S.: On the n-covers of exceptional groups of Lie type. In: Groups St Andrews 2005, Vol. II.
2. Bollobás, B.: Erd\Acute\Acute os, P. On the structure of edge graphs. Bull. London Math. Soc. 5, 317-321 (1973)
3. Britnell, J.R., Evseev, A., Guralnick, R.M., Holmes, P.E., Maróti, A.: Sets of elements that pairwise generate a linear group. J. Combin. Theory Ser. A 115(3), 442-465 (2008)
4. Bryce, R.A., Fedri, V., Serena, L.: Subgroup coverings of some linear groups. Bull. Austral Math. Soc. 60(2), 227-238 (1999)
5. Chowdhury, A., Godsil, C., Royle, G.: Colouring lines in projective spaces. J. Combin. Theory Ser. A 113(1), 39-52 (2006)
6. Chvátal, V., Szemerédi, E.: On the Erd\Acute\Acute os-Stone theorem. J. London Math. Soc. 23(2), 207-214 (1981)
7. Damian, E., Lucchini, A.: On the Dirichlet polynomial of finite groups of Lie type. Rend. Sem. Mat. Univ. Padova, vol. 115 (2006)
8. Dickson, L.E.: Linear Groups: With an Exposition of the Galois Field Theory. Dover Publication Inc., New York (1958)
9. Erd\Acute\Acute os, P., Stone, A.: On the structure of linear graphs. Bull. American Math. Soc. 52, 1087-1091 (1946)
10. Frankl, P., Wilson, R.M.: The Erd\Acute\Acute os-Ko-Rado theorem for vector spaces. J. Comb. Theory, Ser. A 43(2), 228-236 (1986)
11. Haxell, P.E.: A condition for matchability in hypergraphs. Graphs and Combinatorics 11, 245-248 (1995)
12. Haxell, P.E.: A note on vertex list colouring. Combin. Probab. Comput. 10(4), 345-347 (2001)
13. Huppert, B., Blackburn, N.: Finite Groups III. Springer, Berlin (1982)
14. Kleidman, P.B.: The maximal subgroups of the Chevalley groups G2(q), with q odd, the Ree groups G2(q2) and their automorphism groups. J. Algebra 117, 30-71 (1988) 2
15. Liebeck, M.W., Shalev, A.: Maximal subgroups of symmetric groups. J. Combin. Theory Ser. A 75, 341-352 (1996)
16. Liebeck, M.W., Shalev, A.: Simple groups, probabilistic methods, and a conjecture of Kantor and Lubotzky. J. Algebra 184(1), 31-57 (1996)
17. Lovász, L.: Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory, Ser. A 25, 319-324 (1978)
18. Lucido, M.S.: On the covers of finite groups. In: Groups St Andrews 2001 in Oxford, Vol. II. London Math. Soc. Lecture Note Ser., vol. 305, pp. 395-399. Cambridge Univ. Press, Cambridge (2003)
19. Lucido, M.S.: On the n-covers of exceptional groups of Lie type. In: Groups St Andrews 2005, Vol. II.