On finite simple groups and Kneser graphs.
type: Item
instance of: scholarly article
title: On finite simple groups and Kneser graphs.
zbMATH Open document ID: 1206.20024
author: Andrea Lucchini
author: Attila Maróti
published in: Journal of Algebraic Combinatorics
publication date: 2010-05-05T00:00:00Z
review text: Let \(G\) be a finite group. Let \(m(G)\) denote the minimal index of a proper subgroup of \(G\). If \(G\) is non-cyclic then \(\sigma(G)\) denotes the least number of proper subgroups of \(G\) whose union is \(G\). If \(G\) is generated by two elements then \(\omega(G)\) denotes the maximal size of subsets \(S\) of \(G\) such that every two distinct elements of \(S\) generate \(G\). Clearly, \(\omega(G)\leq\sigma(G)\) if both invariants are defined. The question arises: does there exist a universal constant \(c\geq 1\) such that if \(G\) is a non-Abelian finite simple group, then \((1-c/m(G)\leq\omega(G))\)? In Theorem 1.1 of the paper, the affirmative answer to this question for projective special linear groups, Suzuki groups and Ree groups is given. Let \(\Gamma(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 (least number of colors needed to color the vertices of the graph in such way that the endpoints of every edge receive different colors) of the graph \(\Gamma(G)\) is denoted by \(\chi(G)\). Clearly, \(\omega(G)\leq\chi(G)\leq\sigma(G)\) if all three invariants are defined. In Theorem 1.2, if \(G\) is any of the groups \(\text{GL}(n,q)\), \(\text{PGL}(n,q)\), \(\text{SL}(n,q)\), \(\text{PSL}(n,q)\) and \(n\geq 12\), a new lower bound for \(\chi(G)\) is given. In the proofs of Theorems 1.1 and 1.2 certain variants of Kneser graphs appear. In Theorem 1.3, some conditions for the embedding a Kneser graph as induced subgraph to \(\Gamma(S_n)\) or \(\Gamma(A_n)\) are given.
reviewed by: Anatoli Kondrat'ev
Mathematics Subject Classification ID: 20D60
Mathematics Subject Classification ID: 20D06
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20G40
zbMATH DE Number: 5703807
zbMATH Keywords: Kneser graphs
zbMATH Keywords: chromatic numbers
zbMATH Keywords: finite simple groups
zbMATH Keywords: special linear groups
zbMATH Keywords: symmetric groups
MaRDI profile type: Publication
full work available at URL: s10801-009-0177-0
OpenAlex ID: W1976712133
cites work: Sets of permutations that generate the symmetric group pairwise.
cites work: On the Structure of Edge Graphs
cites work: Sets of elements that pairwise generate a linear group
cites work: Subgroup coverings of some linear groups
cites work: Colouring lines in projective space
cites work: On the Erdös-Stone Theorem
cites work: On the Dirichlet polynomial of finite groups of Lie type.
cites work: Q3251484
cites work: On the structure of linear graphs
cites work: The Erdős-Ko-Rado theorem for vector spaces
cites work: A condition for matchability in hypergraphs
cites work: A note on vertex list colouring
cites work: Q3659962
cites work: The maximal subgroups of the Chevalley groups \(G_ 2(q)\) with q odd, the Ree groups \(2G_ 2(q)\), and their automorphism groups
cites work: Maximal subgroups of symmetric groups
cites work: Simple groups, probabilistic methods, and a conjecture of Kantor and Lubotzky
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: Q3371017
cites work: Q3440019
cites work: On the orders of primitive groups
cites work: Covering the symmetric groups with proper subgroups.
cites work: The clique complex and hypergraph matching
cites work: On a class of doubly transitive groups
cites work: Groups as the union of proper subgroups.
cites work: Q5781249
DOI: 10.1007/S10801-009-0177-0
description: scientific article; zbMATH DE number 5703807