期刊
DISCRETE MATHEMATICS
卷 345, 期 4, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.disc.2021.112776
关键词
Symmetric group; Lovasz local lemma; Group generation; Covering
类别
资金
- Fundacao de Apoio a Pesquisa do Distrito Federal (FAPDF)
- Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq) [302134/2018-2, 422202/2018-5]
- European Research Council (ERC) under the European Union [741420]
- National Research, Development and Innovation Office (NKFIH) [K132951, K115799, K138828]
This article studies two functions sigma(G) and omega(G) of the symmetric group G and proves that they both asymptotically tend to 1/2(n/n/2) when n is even. Furthermore, a lower bound of n/5 for omega(G) is provided. The clique number of the graph is also calculated.
Let G be the symmetric group of degree n. Let omega(G) be the maximal size of a subset S of G such that (x, y) = G whenever x, y E S and x not equal y and let sigma(G) be the minimal size of a family of proper subgroups of G whose union is G. We prove that both functions sigma(G) and omega(G) are asymptotically equal to 1/2(n/n/2) when n is even. This, together with a 2 n/2 result of S. Blackburn, implies that sigma(G)/omega(G) tends to 1 as n ->infinity. Moreover, we give a lower bound of n/5 on omega(G) which is independent of the classification of finite simple groups. We also calculate, for large enough n, the clique number of the graph defined as follows: the vertices are the elements of G and two vertices x, y are connected by an edge if (x, y) >= A(n). (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据