Bussey systems and Steiner's tactical problem Colbourn, Charles J; Kreher, Donald L; Ostergård, Patric R. J
Glasnik matematički,
12/2023, Volume:
58, Issue:
2
Journal Article, Paper
Peer reviewed
Open access
In 1853, Steiner posed a number of combinatorial (tactical) problems, which eventually led to a large body of research on Steiner systems.
However, solutions to Steiner's questions coincide with ...Steiner systems only for strengths two and three.
For larger strengths, essentially only one class of solutions to Steiner's tactical problems is known, found by Bussey more than a century ago.
In this paper, the relationships among Steiner systems, perfect binary one-error-correcting codes, and solutions to Steiner's tactical problem (Bussey systems) are discussed.
For the latter, computational results are provided for at most 15 points.
On q-Steiner systems from rank metric codes Arias, Francisco; de la Cruz, Javier; Rosenthal, Joachim ...
Discrete mathematics,
October 2018, 2018-10-00, Volume:
341, Issue:
10
Journal Article
Peer reviewed
Open access
In this paper we prove that rank metric codes with special properties imply the existence of q-analogs of suitable designs. More precisely, we show that the minimum weight vectors of a 2d,d,d dually ...almost MRD code C≤Fqm2d(2d≤m) which has no code words of rank weight d+1 form a q-Steiner system S(d−1,d,2d)q. This is the q-analog of a result in classical coding theory and it may be seen as a first step to prove a q-analog of the famous Assmus–Mattson Theorem.
The research on orthogonal Steiner systems S(t,k,v) was initiated in 1968. For (t,k)∈{(2,3),(3,4)}, this corresponds to orthogonal Steiner triple systems (STSs) and Steiner quadruple systems (SQSs), ...respectively. The existence problem of a pair of orthogonal STSs or SQSs was settled completely thirty years ago. However, for Steiner systems with t≥3 and k≥5, only two small examples of orthogonal pairs were known to exist before this work. An infinite family of orthogonal Steiner systems S(3,5,v) is constructed in this paper. In particular, the existence of a pair of orthogonal Steiner systems S(3,5,4m+1) is established for any even m≥2; additionally a pair of orthogonal G-designs G(4m+15,5,5,3) is displayed for any odd m≥3. The construction is based on the Steiner systems admitting 3-transitive automorphism groups supported by elementary symmetric polynomials. Moreover, 50 mutually orthogonal Steiner systems S(5,8,24) are shown to exist.
Interplay between coding theory and combinatorial t -designs has been a hot topic for many years for combinatorialists and coding theorists. Some infinite families of cyclic codes supporting infinite ...families of 3-designs have been constructed in the past 50 years. However, no infinite family of negacyclic codes supporting an infinite family of 3-designs has been reported in the literature. This is the main motivation of this paper. Let q = p m , where p is an odd prime and m ≥ 2 is an integer. The objective of this paper is to present an infinite family of cyclic codes over GF( q ) supporting an infinite family of 3-designs and two infinite families of negacyclic codes over GF( q 2 ) supporting two infinite families of 3-designs. The parameters and the weight distributions of these codes are determined. The subfield subcodes of these negacyclic codes over GF( q ) are studied. Three infinite families of almost MDS codes are also presented. A constacyclic code over GF(4) supporting a 4-design and seven open problems are also presented in this paper.
In the paper a problem of assignment of tasks to machines is formulated and solved, where a criterion of data replication is used and a large size of data imposes additional constraints. This problem ...is met in practice when dealing with large genomic files or other types of vast data. The necessity of comparing all pairs of files within a big set of DNA sequencing results, which we collected, maintained, and analyzed within a national genomic project, brought us to the proposed results. This problem resembles that of generating a particular Steiner system, and a mechanism observed there is employed in one of our algorithms. Based on the problem complexity, we propose two heuristic algorithms, which work very well even for instances with tight constraints and a heterogeneous environment defined. In addition, we propose a simplified method, nevertheless capable of finding very good solutions and surpassing the algorithms in some special cases. The methods are validated in tests on a wide set of instances, where values of parameters reflect our real-world application and where their usefulness is proven.
We prove asymptotic upper bounds on the number of $d$-partitions (paving matroids of fixed rank) and partial Steiner systems (sparse paving matroids of fixed rank), using a mixture of entropy ...counting, sparse encoding, and the probabilistic method.
Given a subgroup H of a group (G,+), a (G,H,k,1) difference family (DF) is a set F of k-subsets of G such that {f−f′:f,f′∈F,f≠f′,F∈F}=G∖H. Let gZgh be the subgroup of order h in Zgh generated by g. A ...(Zgh,gZgh,k,1)-DF is called cyclic and written as a (gh,h,k,1)-CDF. This paper shows that for h∈{2,3,6}, there exists a (gh,h,4,1)-CDF if and only if gh≡h(mod12), g⩾4 and (g,h)∉{(9,3),(5,6)}. As a corollary, it is shown that a 1-rotational Steiner system S(2,4,v) exists if and only if v≡4(mod12) and v≠28. This solves the long-standing open problem on the existence of a 1-rotational S(2,4,v). As another corollary, we establish the existence of an optimal (v,4,1)-optical orthogonal code with ⌊(v−1)/12⌋ codewords for any positive integer v≡1,2,3,4,6(mod12) and v≠25. We also give applications of our results to cyclic group divisible designs with block size four and optimal cyclic 3-ary constant-weight codes with weight four and minimum distance six.
A line coloring of PG
(
n
,
q
) $\text{PG}(n,q)$, the n $n$‐dimensional projective space over GF(
q
) $(q)$, is an assignment of colors to all lines of PG
(
n
,
q
) $\text{PG}(n,q)$ so that any two ...lines with the same color do not intersect. The chromatic index of PG
(
n
,
q
) $\text{PG}(n,q)$, denoted by χ
′
(
PG
(
n
,
q
)
) $\chi ^{\prime} (\text{PG}(n,q))$, is the least number of colors for which a coloring of PG
(
n
,
q
) $\text{PG}(n,q)$ exists. This paper translates the problem of determining the chromatic index of PG
(
n
,
q
) $\text{PG}(n,q)$ to the problem of examining the existences of PG
(
3
,
q
) $\text{PG}(3,q)$ and PG
(
4
,
q
) $\text{PG}(4,q)$ with certain properties. In particular, it is shown that for any odd integer n $n$ and q
∈
{
3
,
4
,
8
,
16
}
,
χ
′
(
PG
(
n
,
q
)
)
=
(
q
n
−
1
)
∕
(
q
−
1
) $q\in \{3,4,8,16\},\chi ^{\prime} (\text{PG}(n,q))=({q}^{n}-1)\unicode{x02215}(q-1)$, which implies the existence of a parallelism of PG
(
n
,
q
) $\text{PG}(n,q)$ for any odd integer n $n$ and q
∈
{
3
,
4
,
8
,
16
} $q\in \{3,4,8,16\}$.
Tremain equiangular tight frames Fickus, Matthew; Jasper, John; Mixon, Dustin G. ...
Journal of combinatorial theory. Series A,
January 2018, 2018-01-00, Volume:
153
Journal Article
Peer reviewed
Open access
Equiangular tight frames provide optimal packings of lines through the origin. We combine Steiner triple systems with Hadamard matrices to produce a new infinite family of equiangular tight frames. ...This in turn leads to new constructions of strongly regular graphs and distance-regular antipodal covers of the complete graph.