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.     

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.     

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.     

Nonsymmetric 2‐(v,k,λ) designs,with (r,λ) = 1, admitting a solvable flag‐transitive automorphism group of affine type

Nonsymmetric $2‐\left(v,k,\lambda \right)$ designs, with $\left(r,\lambda \right)=1$, admitting a solvable flag‐transitive automorphism group of affine type not contained in $A\mathrm{\Gamma }{L}_1\left(v\right)$ are classified.     

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.     

New lower bounds on the size of (n,r)‐arcs in PG(2,q)

An $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ is a set of $n$ points such that each line contains at most $r$ of the selected points. It is well known that $\left(n,r\right)$‐arcs in $\text{PG}\left(2,q\right)$ correspond to projective linear codes. Let $m_r\left(2,q\right)$ denote the maximal number $n$ of points for which an $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ exists. In this paper we obtain improved lower bounds on $m_r\left(2,q\right)$ by explicitly constructing $\left(n,r\right)$‐arcs. Some of the constructed $\left(n,r\right)$‐arcs correspond to linear codes meeting the Griesmer bound. All results are obtained by integer linear programming.     

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$).     

Deza graphs with parameters (v,k,k−2,a)

A Deza graph with parameters $\left(v,k,b,a\right)$ is a $k$‐regular graph on $v$ vertices in which the number of common neighbors of two distinct vertices takes one of the following values: $b$ or $a$, where $b\ge a$. In the previous papers Deza graphs with $b=k?1$ were characterized. In this paper, we characterize Deza graphs with $b=k?2$.     

Generalized pentagonal geometries

A pentagonal geometry PENT($k,r$) is a partial linear space, where every line is incident with $k$ points, every point is incident with $r$ lines, and for each point $x$, there is a line incident with precisely those points that are not collinear with $x$. Here we generalize the concept by allowing the points not collinear with $x$ to form the point set of a Steiner system $S\left(2,k,w\right)$ whose blocks are lines of the geometry.     

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$).     

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)$.     

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.     

On the structure of small strength‐2 covering arrays

A covering array $\text{CA}\left(N;t,k,v\right)$ of strength $t$ is an $N\times k$ array of symbols from an alphabet of size $v$ such that in every $N\times t$ subarray, every $t$‐tuple occurs in at least one row. A covering array is optimal if it has the smallest possible $N$ for given $t$, $k$, and $v$, and uniform if every symbol occurs $?N∕v?$ or $?N∕v?$ times in every column. Before this paper, the only known optimal covering arrays for $t=2$ were orthogonal arrays, covering arrays with $v=2$ constructed from Sperner's Theorem and the Erd?s‐Ko‐Rado Theorem, and 11 other parameter sets with $v>2$ and $N>v^2$. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength‐2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength‐2 covering array with $v>2$ and $N>v^2$ is now known for 21 parameter sets. Our constructive results continue to support the conjecture.     

A generalization of Heffter arrays

In this paper, we define a new class of partially filled arrays, called relative Heffter arrays, that are a generalization of the Heffter arrays introduced by Archdeacon in 2015. Let $v=2nk+t$ be a positive integer, where $t$ divides $2nk$, and let $J$ be the subgroup of ${\mathbb{Z}}_v$ of order $t$. A ${\mathrm{H}}_t\left(m,n;s,k\right)$ Heffter array over ${\mathbb{Z}}_v$ relative to $J$ is an $m\times n$ partially filled array with elements in ${\mathbb{Z}}_v$ such that (a) each row contains $s$ filled cells and each column contains $k$ filled cells; (b) for every $x\in {\mathbb{Z}}_v\backslash J$, either $x$ or $?x$ appears in the array; and (c) the elements in every row and column sum to $0$. Here we study the existence of square integer (i.e., with entries chosen in $\pm \left\{1,\text{…},?\frac{2nk+t}{2}?\right\}$ and where the sums are zero in $\mathbb{Z}$) relative Heffter arrays for $t=k$, denoted by ${\mathrm{H}}_k\left(n;k\right)$. In particular, we prove that for $3\le k\le n$, with $k\ne 5$, there exists an integer ${\mathrm{H}}_k\left(n;k\right)$ if and only if one of the following holds: (a) $k$ is odd and $n\equiv 0,3\left(\text{mod}4\right)$; (b) $k\equiv 2\left(\text{mod}4\right)$ and $n$ is even; (c) $k\equiv 0\left(\text{mod}4\right)$. Also, we show how these arrays give rise to cyclic cycle decompositions of the complete multipartite graph.     

Pure tetrahedral quadruple systems with index two

An oriented tetrahedron defined on four vertices is a set of four cyclic triples with the property that any ordered pair of vertices is contained in exactly one of the cyclic triples. A tetrahedral quadruple system of order $n$ with index $\lambda$, denoted by ${\text{TQS}}_{\lambda }\left(n\right)$, is a pair $\left(X,\mathrm{?}\right)$, where $X$ is an $n$‐set and $\mathrm{?}$ is a set of oriented tetrahedra (blocks) such that every cyclic triple on $X$ is contained in exactly $\lambda$ members of $\mathrm{?}$. A ${\text{TQS}}_{\lambda }\left(n\right)$ is pure if there do not exist two blocks with the same vertex set. When $\lambda =1$, the spectrum of a pure TQS $\left(n\right)$ has been completely determined by Ji. In this paper, we show that there exists a pure ${\text{TQS}}_2\left(n\right)$ if and only if $n\equiv 1,2\left(\mathrm{mod}3\right)$ and $n\ge 7$. A corollary is that a simple ${\text{QS}}_4\left(n\right)$ also exists if and only if $n\equiv 1,2\left(\mathrm{mod}3\right)$ and $n\ge 7$.     

Lagrangian densities of linear forests and Turán numbers of their extensions

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. However, determining the Lagrangian density of a hypergraph is not an easy task even for a “simple” hypergraph. For example, to determine the Lagrangian density of $K_4^3$ is equivalent to determine the Turán density of $K_4^3$ (a long standing conjecture of Turán). Hefetz and Keevash studied the Lagrangian density of the 3‐uniform matching of size 2. Pikhurko determined the Lagrangian density of a 4‐uniform tight path of length 2 and this led to confirm the conjecture of Frankl and Füredi on the Turán number of the $r$‐uniform generalized triangle for the case $r=4$. It is natural and interesting to consider Lagrangian densities of other “basic” hypergraphs. In this paper, we determine the Lagrangian densities for a class of 3‐uniform linear forests. For positive integers $s$ and $t$, let $P_{s,t}$ be the disjoint union of a 3‐uniform linear path of length $s$ and $t$ pairwise disjoint edges. In this paper, we determine the Lagrangian densities of $P_{s,t}$ for any $t$ and $s=2$ or 3. Applying a modified version of Pikhurko's transference argument used by Brandt, Irwin, and Jiang, we obtain the Turán numbers of their extensions.     

Decomposable super‐simple RBIBDs with block size 4 and index 6

Necessary conditions for the existence of a decomposable super‐simple resolvable $\left(v,4,6\right)$‐BIBD whose two component subdesigns are both resolvable $\left(v,4,3\right)$‐BIBDs are $v\equiv 0$ (mod $4$) and $v\ge 16$. In this paper, it is proved that these necessary conditions are sufficient, except possibly for $v\in \left\{268,284,292,296\right\}$.