Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDesigns, permutations, and transitive groups
244
0
0.0
(
0
)
Added by
Patrick Sol\\'e
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A notion of $t$-designs in the symmetric group on $n$ letters was introduced by Godsil in 1988. In particular $t$-transitive sets of permutations form a $t$-design. We derive special lower bounds for $t=1$ and $t=2$ by a power moment method. For general $n,t$ we give a %linear programming lower bound . For $nge 4$ and $t=2,$ this bound is strong enough to show a lower bound on the size of such $t$-designs of $n(n-1)dots (n-t+1),$ which is best possible when sharply $t$-transitive sets of permutations exist. This shows, in particular, that tight $2$-designs do not exist.
rate research
Read More
We give two combinatorial proofs of Goulden and Jacksons formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type $B$.
Let $q$ be a prime power and $Vcong{mathbb F}_q^n$. A $t$-$(n,k,lambda)_q$ design, or simply a subspace design, is a pair ${mathcal D}=(V,{mathcal B})$, where ${mathcal B}$ is a subset of the set of all $k$-dimensional subspaces of $V$, with the property that each $t$-dimensional subspace of $V$ is contained in precisely $lambda$ elements of ${mathcal B}$. Subspace designs are the $q$-analogues of balanced incomplete block designs. Such a design is called block-transitive if its automorphism group ${rm Aut}({mathcal D})$ acts transitively on ${mathcal B}$. It is shown here that if $tgeq 2$ and ${mathcal D}=(V,{mathcal B})$ is a block-transitive $t$-$(n,k,lambda)_q$ design then ${mathcal D}$ is trivial, that is, ${mathcal B}$ is the set of all $k$-dimensional subspaces of $V$.
We introduce the random graph $mathcal{P}(n,q)$ which results from taking the union of two paths of length $ngeq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0<q(n)leq 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.
Recently, Bagno, Garber and Mansour studied a kind of excedance number on the complex reflection groups and computed its multidistribution with the number of fixed points on the set of involutions in these groups. In this note, we consider the similar problems in more general cases and make a correction of one result obtained by them.
A detailed description of the structure of two-ended arc-transitive digraphs is given. It is also shown that several sets of conditions, involving such concepts as Property Z, local quasi-primitivity and prime out-valency, imply that an arc-transitive digraph must be highly-arc-transitive. These are then applied to give a complete classification of two-ended highly-arc-transitive digraphs with prime in- and out-valencies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
