Source author record

Ákos Seress

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.GR math.CO math.PR

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Element order versus minimal degree in permutation groups: an old lemma with new applications

In this note we present a simplified and slightly generalized version of a lemma the authors published in 1987. The lemma as stated here asserts that if the order of a permutation of $n$ elements is greater than $n^α$ then some non-identity power of the permutation has support size less than $n/α$ . The original version made an unnecessary additional assumption on the cycle structure of the permutation; the proof of the present cleaner version follows the original proof verbatim. Application areas include parallel and sequential algorithms for permutation groups, the diameter of Cayley graphs of permutation groups, and the automorphisms of structures with regularity constraints such as Latin squares, Steiner 2-designs, and strongly regular graphs. This note also serves as a modest tribute to the junior author whose untimely passing is deeply mourned.

preprint2014arXiv

Generation of finite classical groups by pairs of elements with large fixed point spaces

We study `good elements' in finite $2n$ -dimensional classical groups $G$ : namely $t$ is a `good element' if $o(t)$ is divisible by a primitive prime divisor of $q^n-1$ for the relevant field order $q$ , and $t$ fixes pointwise an $n$ -space. The group ${\rm{SL}}_{2n}(q)$ contains such elements, and they are present in ${\rm{Su}}_{2n}(q), {\rm{Sp}}_{2n}(q), {\rm{So}}^ε_{2n}(q)$ , only if $n$ is odd, even, even, respectively. We prove that there is an absolute positive constant $c$ such that two random conjugates of $t$ generate $G$ with probability at least $c$ , if $G\ne {\rm{Sp}}_{2n}(q)$ with $q$ even. In the exceptional case $G={\rm{Sp}}_{2n}(q)$ with $q$ even, two conjugates of $t$ never generate $G$ : in this case we prove that two random conjugates of $t$ generate a subgroup ${\rm{SO}}^ε_{2n}(q)$ with probability at least $c$ . The results (proved for all field orders at least $4$ ) underpin analysis of new constructive recognition algorithms for classical groups in even characteristic, which succeed where methods utilising involution centralisers are not available.

preprint2014arXiv

Random generators of the symmetric group: diameter, mixing time and spectral gap

Let $g$ , $h$ be a random pair of generators of $G=Sym(n)$ or $G=Alt(n)$ . We show that, with probability tending to $1$ as $n\to \infty$ , (a) the diameter of $G$ with respect to $S = \{g,h,g^{-1},h^{-1}\}$ is at most $O(n^2 (\log n)^c)$ , and (b) the mixing time of $G$ with respect to $S$ is at most $O(n^3 (\log n)^c)$ . (Both $c$ and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott--Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai--Beals--Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on $\ell$ -tuples, where $\ell$ is an arbitrary constant (Friedman et al., 1998).

preprint2013arXiv

On Pyber's base size conjecture

Let $G$ be a permutation group on a finite set $Ω$ . A subset $B \subseteq Ω$ is a base for $G$ if the pointwise stabilizer of $B$ in $G$ is trivial. The base size of $G$ , denoted $b(G)$ , is the smallest size of a base. A well known conjecture of Pyber from the early 1990s asserts that there exists an absolute constant $c$ such that $b(G) \le c\log |G| / \log n$ for any primitive permutation group $G$ of degree $n$ . Some special cases have been verified in recent years, including the almost simple and diagonal cases. In this paper, we prove Pyber's conjecture for all non-affine primitive groups.

preprint2012arXiv

Bounds on the diameter of Cayley graphs of the symmetric group

In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group of degree n, the word length in terms of S of every permutation is bounded above by a polynomial of n. We prove this conjecture for sets of generators containing a permutation fixing at least 37% of the points.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ákos Seress

Research overview

Is this your work?

5 publications

Element order versus minimal degree in permutation groups: an old lemma with new applications

Generation of finite classical groups by pairs of elements with large fixed point spaces

Random generators of the symmetric group: diameter, mixing time and spectral gap

On Pyber's base size conjecture

Bounds on the diameter of Cayley graphs of the symmetric group

See the researcher in context

Building this map preview