Restrictions on parameters of partial difference sets in nonabelian groups

A partial difference set $S$ in a finite group $G$ satisfying $1?S$ and $S=S^{?1}$ corresponds to an undirected strongly regular Cayley graph $\text{Cay}\left(G,S\right)$. While the case when $G$ is abelian has been thoroughly studied, there are comparatively few results when $G$ is nonabelian. In this paper, we provide restrictions on the parameters of a partial difference set that apply to both abelian and nonabelian groups and are especially effective in groups with a nontrivial center. In particular, these results apply to $p$‐groups, and we are able to rule out the existence of partial difference sets in many instances.     

Paley type partial difference sets in abelian groups

Partial difference sets with parameters $\left(v,k,\lambda ,\mu \right)=\left(v,\left(v?1\right)/2,\left(v?5\right)/4,\left(v?1\right)/4\right)$ are called Paley type partial difference sets. In this note, we prove that if there exists a Paley type partial difference set in an abelian group of order v, where v is not a prime power, then $v=n^4$ or $9n^4$, $n>1$ an odd integer. In 2010, Polhill constructed Paley type partial difference sets in abelian groups with those orders. Thus, combining with the constructions of Polhill and the classical Paley construction using nonzero squares of a finite field, we completely answer the following question: “For which odd positive integers $v>1$, can we find a Paley type partial difference set in an abelian group of order $v$?”     

New necessary conditions on Paley‐type partial difference sets in abelian groups

Let be an abelian group of order , where are distinct odd prime numbers. In this paper, we prove that if contains a regular Paley‐type partial difference set (PDS), then for any is congruent to 3 modulo 4 whenever is odd. These new necessary conditions further limit the specific order of an abelian group in which there can exist a Paley‐type PDS. Our result is similar to a result on abelian Hadamard (Menon) difference sets proved by Ray‐Chaudhuri and Xiang in 1997.     

Sequencing partial Steiner triple systems

A partial Steiner triple system of order $n$ is sequenceable if there is a sequence of length $n$ of its distinct points such that no proper segment of the sequence is a union of point‐disjoint blocks. We prove that if a partial Steiner triple system has at most three point‐disjoint blocks, then it is sequenceable.     

There are 3155 nonisomorphic perfect one‐factorizations of K16

We enumerate all nonisomorphic perfect one‐factorizations of $K_{16}$.     

On a question of Thas on partial 3‐(qn + 1, q + 1, 1) designs

In this note, we answer a question of JA Thas about partial $3$‐ $\left(q^n+1,q+1,1\right)$ designs. We then extend this answer to a result about the embedding of certain partial $3$‐ $\left(q^2+1,q+1,1\right)$ designs into Möbius planes.     

A reduction of the spectrum problem for odd sun systems and the prime case

A k‐cycle with a pendant edge attached to each vertex is called a k‐sun. The existence problem for k‐sun decompositions of K_v, with k odd, has been solved only when k = 3 or 5. By adapting a method used by Hoffmann, Lindner, and Rodger to reduce the spectrum problem for odd cycle systems of the complete graph, we show that if there is a $k$‐sun system of $K_v$ ( $k$ odd) whenever $v$ lies in the range $2k<v<6k$ and satisfies the obvious necessary conditions, then such a system exists for every admissible $v\ge 6k$. Furthermore, we give a complete solution whenever k is an odd prime.     

New lower bounds for partial k‐parallelisms

Due to the applications in network coding, subspace codes and designs have received many attentions. Suppose that $k\mid n$ and $V\left(n,q\right)$ is an $n$‐dimensional space over the finite field ${\mathbb{F}}_q$. A $k$‐spread is a $(q^n?1)/(q^k?1)$‐set of $k$‐dimensional subspaces of $V\left(n,q\right)$ such that each nonzero vector is contained in exactly one element of it. A partial $k$‐parallelism in $V\left(n,q\right)$ is a set of pairwise disjoint $k$‐spreads. As the number of $k$‐dimensional subspaces in $V\left(n,q\right)$ is ${\left[\genfrac{}{}{0ex}{}{n}{k}\right]}_q$, there are at most ${\left[\genfrac{}{}{0ex}{}{n?1}{k?1}\right]}_q$ spreads in a partial $k$‐parallelism. By studying the independence numbers of Cayley graphs associated to a special type of partial $k$‐parallelisms in $V\left(n,q\right)$, we obtain new lower bounds for partial $k$‐parallelisms. In particular, we show that there exist at least $\frac{q^k?1}{q^n?1}{\left[\genfrac{}{}{0ex}{}{n?1}{k?1}\right]}_q$ pairwise disjoint $k$‐spreads in $V\left(n,q\right)$.     

Exceptions and characterization results for type‐1 λ‐designs

Let $X$ be a finite set with $v$ elements, called points and $\beta$ be a family of subsets of $X$, called blocks. A pair $\left(X,\beta \right)$ is called $\lambda$‐design whenever $\mid \beta \mid =\mid X\mid$ and

• 1. for all $B_i,B_j\in \beta ,i\ne j,\mid B_i\cap B_j\mid =\lambda$;
• 2. for all $B_j\in \beta ,\mid B_j\mid =k_j>\lambda$, and not all $k_j$ are equal.

The only known examples of $\lambda$‐designs are so‐called type‐1 designs, which are obtained from symmetric designs by a certain complementation procedure. Ryser and Woodall had independently conjectured that all $\lambda$‐designs are type‐1. Let $r,r^{*}?(r>r^{*})$ be replication numbers of a $\lambda$‐design $D=\left(X,\beta \right)$ and $g=\text{gcd}\left(r?1,r^{*}?1\right),m=\text{gcd}\left(\left(r?r^{*}\right)∕g,\lambda \right)$, and $m\prime =m$, if $m$ is odd and $m\prime =m∕2$, otherwise. For distinct points $x$ and $y$ of $D$, let $\lambda \left(x,y\right)$ denote the number of blocks of $X$ containing $x$ and $y$. We strengthen a lemma of S.S. Shrikhande and N.M. Singhi and use it to prove that if $\frac{r\left(r?1\right)}{\left(v?1\right)}?\frac{k\left(r?r^{*}\right)}{m\prime \left(v?1\right)}$ are not integers for $k=1,2,\text{…},m\prime ?1$, then $D$ is type‐1. As an application of these results, we show that for fixed positive integer $\theta$ there are finitely many nontype‐1 $\lambda$‐designs with $r=r^{*}+\theta$. If $r?r^{*}=27$ or $r?r^{*}=4p$ and $r^{*}\ne {\left(p?1\right)}^2$, or $v=7p+1$ such that $p?1,13\left(\mathrm{mod}21\right)$ and $p?4,9,19,24\left(\mathrm{mod}35\right)$, where $p$ is a positive prime, then $D$ is type‐1. We further obtain several inequalities involving $\lambda (x,y)$, where equality holds if and only if D is type‐1.     

The number of the non‐full‐rank Steiner triple systems

The $p$‐rank of a Steiner triple system (STS) $B$ is the dimension of the linear span of the set of characteristic vectors of blocks of $B$, over GF $\left(p\right)$. We derive a formula for the number of different STSs of order $v$ and given $2$‐rank $r_2$, $r_2<v$, and a formula for the number of STSs of order $v$ and given $3$‐rank $r_3$, $r_3<v?1$. Also, we prove that there are no STSs of $2$‐rank smaller than $v$ and, at the same time, $3$‐rank smaller than $v?1$. Our results extend previous study on enumerating STSs according to the rank of their codes, mainly by Tonchev, V.A. Zinoviev, and D.V. Zinoviev for the binary case and by Jungnickel and Tonchev for the ternary case.     

Design theory and some forbidden configurations

In this paper we relate $t$‐designs to a forbidden configuration problem in extremal set theory. Let ${\mathbf{1}}_t{\mathbf{0}}_{?}$ denote a column of $t$ 1's on top of $?$ 0's. Let $q?{\mathbf{1}}_t{\mathbf{0}}_{?}$ denote the $\left(t+?\right)\times q$ matrix consisting of $t$ rows of $q$ 1's and $?$ rows of $q$ 0's. We consider extremal problems for matrices avoiding certain submatrices. Let $A$ be a (0, 1)‐matrix forbidding any $\left(t+?\right)\times \left(\lambda +2\right)$ submatrix $\left(\lambda +2\right)?{\mathbf{1}}_t{\mathbf{0}}_{?}$. Assume $A$ is $m$‐rowed and only columns of sum $t+1,t+2,\text{…},m??$ are allowed to be repeated. Assume that $A$ has the maximum number of columns subject to the given restrictions. Assume $m$ is sufficiently large. Then $A$ has each column of sum $0,1,\text{…},t$ and $m??+1,m??+2,\text{…},m$ exactly once and, given the appropriate divisibility condition, the columns of sum $t+1$ correspond to a $t$‐design with block size $t+1$ and parameter $\lambda$. The proof derives a basic upper bound on the number of columns of $A$ by a pigeonhole argument and then a careful argument, for large m, reduces the bound by a substantial amount down to the value given by design‐based constructions. We extend in a few directions.     

Large monochromatic components in 3‐edge‐colored Steiner triple systems

It is known that in any r‐coloring of the edges of a complete r‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that $\left(2n+3\right)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $\left(1?o\left(1\right)\right)n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐partite hole (ie, disjoint sets $X_1,X_2,X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1,X_2,X_3$) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.     

Legendre G‐array pairs and the theoretical unification of several G‐array families

We investigate how Legendre $G$‐array pairs are related to several different perfect binary $G$‐array families. In particular we study the relations between Legendre $G$‐array pairs, Sidelnikov‐Lempel‐Cohn‐Eastman ${\mathbb{Z}}_{q?1}$‐arrays, Yamada‐Pott $G$‐array pairs, Ding‐Helleseth‐Martinsen ${\mathbb{Z}}_2\times {\mathbb{Z}}_p^m$‐arrays, Yamada ${\mathbb{Z}}_{\left(q?1\right)∕2}$‐arrays, Szekeres ${\mathbb{Z}}_p^m$‐array pairs, Paley ${\mathbb{Z}}_p^m$‐array pairs, and Baumert ${\mathbb{Z}}_{p_1}^{m_1}\times {\mathbb{Z}}_{p_2}^{m_2}$‐array pairs. Our work also solves one of the two open problems posed by Ding. Moreover, we provide several computer search‐based existence and nonexistence results regarding Legendre ${\mathbb{Z}}_n$‐array pairs. Finally, by using cyclotomic cosets, we provide a previously unknown Legendre ${\mathbb{Z}}_{57}$‐array pair.     

Cyclically near‐resolvable 4‐cycle systems of 2Kv

Fu and Mishima [J. Combin. Des. 10 (2002), pp. 116–125] have utilized the extended Skolem sequence to prove that there exists a 1‐rotationally resolvable $4$‐cycle system of $2K_v$ if and only if $v\equiv 0$ (mod $4$). In this paper, the existence of a cyclically near‐resolvable $4$‐cycle system is discussed, and it is shown that there exists a cyclically near‐resolvable $4$‐cycle system of $2K_v$ if and only if $v\equiv 1$ (mod $4$).     

Combinatorial designs for deep learning

Deep learning is a machine learning methodology using a multilayer neural network. Let $V_1,V_2,\text{…},V_L$ be mutually disjoint node sets (layers). A multilayer neural network can be regarded as a union of the complete bipartite graphs $K_{\mid V_i\mid ,\mid V_{i+1}\mid }$ on consecutive two node sets $V_i$ and $V_{i+1}$ for $i=1,2,\text{…},L?1$. The edges of a bipartite graph function as weights which are represented as a matrix. The values of $i$th layer are basically computed by multiplication of the weight matrix and values of $\left(i?1\right)$th layer. Using mass training and teacher data, the weight parameters are estimated little by little. Overfitting (or overlearning) refers to a model that models the “training data” too well. It then becomes difficult for the model to generalize to new data which were not in the training set. The most popular method to avoid overfitting is called dropout. Dropout zeros out a random sample of activations (nodes) during the training process. A random sampling of nodes causes more irregular frequency of dropout edges. There is a similar sampling concept in the area of design of experiments. We propose a combinatorial design that drops out nodes from each layer. This design balances the edge frequencies. We analyze and construct such designs in this paper.     

Short k‐radius sequences, k‐difference sequences and universal cycles

An $n$‐ary $k$‐radius sequence is a finite sequence of elements taken from an alphabet of size $n$ in which any two distinct elements occur within distance $k$ of each other somewhere in the sequence. The study of constructing short $k$‐radius sequences was motivated by some problems occurring in large data transfer. Let $f_k\left(n\right)$ be the shortest length of any $n$‐ary $k$‐radius sequence. We show that the conjecture $f_k\left(n\right)=\frac{n^2}{2k}+O\left(n\right)$ by Bondy et al is true for $k\le 4$, and determine the exact values of $f_2\left(n\right)$ for new infinitely many $n$. Further, we investigate new sequences which we call $k$‐difference, as they are related to $k$‐radius sequences and seem to be interesting in themselves. Finally, we answer a question about the optimal length of packing and covering analogs of universal cycles proposed by D?bski et al.     

Colourings of star systems

An $e$‐star is a complete bipartite graph $K_{1,e}$. An $e$‐star system of order $n>1,S_e\left(n\right)$, is a partition of the edges of the complete graph $K_n$ into $e$‐stars. An $e$‐star system is said to be $k$‐colourable if its vertex set can be partitioned into $k$ sets (called colour classes) such that no $e$‐star is monochromatic. The system $S_e\left(n\right)$ is $k$‐chromatic if $S_e\left(n\right)$ is $k$‐colourable but is not $\left(k?1\right)$‐colourable. If every $k$‐colouring of an $e$‐star system can be obtained from some $k$‐colouring $?$ by a permutation of the colours, we say that the system is uniquely $k$‐colourable. In this paper, we first show that for any integer $k?2$, there exists a $k$‐chromatic 3‐star system of order $n$ for all sufficiently large admissible $n$. Next, we generalize this result for $e$‐star systems for any $e?3$. We show that for all $k?2$ and $e?3$, there exists a $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$). Finally, we prove that for all $k?2$ and $e?3$, there exists a uniquely $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$).