ترغب بنشر مسار تعليمي؟ اضغط هنا

Designs, permutations, and transitive groups

244   0   0.0 ( 0 )
 نشر من قبل Patrick Sol\\'e
 تاريخ النشر 2021
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

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 prop erty 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$. Thi s 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$.
228 - Toufik Mansour , Yidong Sun 2007
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 simila r 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-transitiv e 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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا