Source author record

Patric R. J. Östergård

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.CO math.IT Data Structures and Algorithms

Catalog footprint

Research overview

16works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Steiner Triple Systems of Order 21 with Subsystems

The smallest open case for classifying Steiner triple systems is order 21. A Steiner triple system of order 21, an STS(21), can have subsystems of orders 7 and 9, and it is known that there are 12,661,527,336 isomorphism classes of STS(21)s with sub-STS(9)s. Here, the classification of STS(21)s with subsystems is completed by settling the case of STS(21)s with sub-STS(7)s. There are 116,635,963,205,551 isomorphism classes of such systems. An estimation of the number of isomorphism classes of STS(21)s is given.

preprint2016arXiv

Constructing error-correcting binary codes using transitive permutation groups

Let $A_2(n,d)$ be the maximum size of a binary code of length $n$ and minimum distance $d$ . In this paper we present the following new lower bounds: $A_2(18,4) \ge 5632$ , $A_2(21,4) \ge 40960$ , $A_2(22,4) \ge 81920$ , $A_2(23,4) \ge 163840$ , $A_2(24,4) \ge 327680$ , $A_2(24,10) \ge 136$ , and $A_2(25,6) \ge 17920$ . The new lower bounds are a result of a systematic computer search over transitive permutation groups.

preprint2016arXiv

The chromatic number of the square of the 8-cube

A cube-like graph is a Cayley graph for the elementary abelian group of order $2^n$ . In studies of the chromatic number of cube-like graphs, the $k$ th power of the $n$ -dimensional hypercube, $Q_n^k$ , is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph $Q_n^k$ can be constructed with one vertex for each binary word of length $n$ and edges between vertices exactly when the Hamming distance between the corresponding words is at most $k$ . Consequently, a proper coloring of $Q_n^k$ corresponds to a partition of the $n$ -dimensional binary Hamming space into codes with minimum distance at least $k+1$ . The smallest open case, the chromatic number of $Q_8^2$ , is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified.

preprint2016arXiv

There is No McLaughlin Geometry

We determine that there is no partial geometry ${\cal G}$ with parameters $(s,t,α)=(4,27,2)$ . The existence of such a geometry has been a challenging open problem of interest to researchers for almost 40 years. The particular interest in ${\cal G}$ is due to the fact that it would have the exceptional McLaughlin graph as its point graph. Our proof makes extensive use of symmetry and high-performance distributed computing, and details of our techniques and checks are provided. One outcome of our work is to show that a pseudogeometric strongly regular graph achieving equality in the Krein bound need not be the point graph of any partial geometry.

preprint2015arXiv

A coloring of the square of the 8-cube with 13 colors

Let $χ_{\bar{k}}(n)$ be the number of colors required to color the $n$ -dimensional hypercube such that no two vertices with the same color are at a distance at most $k$ . In other words, $χ_{\bar{k}}(n)$ is the minimum number of binary codes with minimum distance at least $k+1$ required to partition the $n$ -dimensional Hamming space. By giving an explicit coloring, it is shown that $χ_{\bar{2}}(8)=13$ .

preprint2015arXiv

Further Results on the Classification of MDS Codes

A $q$ -ary maximum distance separable (MDS) code $C$ with length $n$ , dimension $k$ over an alphabet $\mathcal{A}$ of size $q$ is a set of $q^k$ codewords that are elements of $\mathcal{A}^n$ , such that the Hamming distance between two distinct codewords in $C$ is at least $n-k+1$ . Sets of mutually orthogonal Latin squares of orders $q\leq 9$ , corresponding to two-dimensional \mbox{ $q$ -}ary MDS codes, and $q$ -ary one-error-correcting MDS codes for $q\leq 8$ have been classified in earlier studies. These results are used here to complete the classification of all $7$ -ary and $8$ -ary MDS codes with $d\geq 3$ using a computer search.

preprint2015arXiv

New Lower Bounds for the Shannon Capacity of Odd Cycles

The Shannon capacity of a graph $G$ is defined as $c(G)=\sup_{d\geq 1}(α(G^d))^{\frac{1}{d}},$ where $α(G)$ is the independence number of $G$ . The Shannon capacity of the cycle $C_5$ on $5$ vertices was determined by Lovász in 1979, but the Shannon capacity of a cycle $C_p$ for general odd $p$ remains one of the most notorious open problems in information theory. By prescribing stabilizers for the independent sets in $C_p^d$ and using stochastic search methods, we show that $α(C_7^5)\geq 350$ , $α(C_{11}^4)\geq 748$ , $α(C_{13}^4)\geq 1534$ and $α(C_{15}^3)\geq 381$ . This leads to improved lower bounds on the Shannon capacity of $C_7$ and $C_{15}$ : $c(C_7)\geq 350^{\frac{1}{5}}> 3.2271$ and $c(C_{15})\geq 381^{\frac{1}{3}}> 7.2495$ .

preprint2015arXiv

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.

preprint2014arXiv

Non-existence of a ternary constant weight $(16, 5, 15; 2048)$ diameter perfect code

Ternary constant weight codes of length $n=2^m$ , weight $n-1$ , cardinality $2^n$ and distance $5$ are known to exist for every $m$ for which there exists an APN permutation of order $2^m$ , that is, at least for all odd $m \geq 3$ and for $m=6$ . We show the non-existence of such codes for $m=4$ and prove that any codes with the parameters above are diameter perfect.

preprint2014arXiv

On the Classification of MDS Codes

A $q$ -ary code of length $n$ , size $M$ , and minimum distance $d$ is called an $(n,M,d)_q$ code. An $(n,q^{k},n-k+1)_q$ code is called a maximum distance separable (MDS) code. In this work, some MDS codes over small alphabets are classified. It is shown that every $(k+d-1,q^k,d)_q$ code with $k\geq 3$ , $d \geq 3$ , $q \in \{5,7\}$ is equivalent to a linear code with the same parameters. This implies that the $(6,5^4,3)_5$ code and the $(n,7^{n-2},3)_7$ MDS codes for $n\in\{6,7,8\}$ are unique. The classification of one-error-correcting $8$ -ary MDS codes is also finished; there are $14$ , $8$ , $4$ , and $4$ equivalence classes of $(n,8^{n-2},3)_8$ codes for $n=6,7,8,9$ , respectively. One of the equivalence classes of perfect $(9,8^7,3)_8$ codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction.

preprint2012arXiv

The quaternary complex Hadamard matrices of orders 10, 12, and 14

A complete classification of quaternary complex Hadamard matrices of orders 10, 12 and 14 is given, and a new parametrization scheme for obtaining new examples of affine parametric families of complex Hadamard matrices is provided. On the one hand, it is proven that all 10x10 and 12x12 quaternary complex Hadamard matrices belong to some parametric family, but on the other hand, it is shown by exhibiting an isolated 14x14 matrix that there cannot be a general method for introducing parameters into these types of matrices.

preprint2011arXiv

On Optimal Binary One-Error-Correcting Codes of Lengths $2^m-4$ and $2^m-3$

Best and Brouwer [Discrete Math. 17 (1977), 235-245] proved that triply-shortened and doubly-shortened binary Hamming codes (which have length $2^m-4$ and $2^m-3$ , respectively) are optimal. Properties of such codes are here studied, determining among other things parameters of certain subcodes. A utilization of these properties makes a computer-aided classification of the optimal binary one-error-correcting codes of lengths 12 and 13 possible; there are 237610 and 117823 such codes, respectively (with 27375 and 17513 inequivalent extensions). This completes the classification of optimal binary one-error-correcting codes for all lengths up to 15. Some properties of the classified codes are further investigated. Finally, it is proved that for any $m \geq 4$ , there are optimal binary one-error-correcting codes of length $2^m-4$ and $2^m-3$ that cannot be lengthened to perfect codes of length $2^m-1$ .

preprint2011arXiv

Two Optimal One-Error-Correcting Codes of Length 13 That Are Not Doubly Shortened Perfect Codes

The doubly shortened perfect codes of length 13 are classified utilizing the classification of perfect codes in [P.R.J. Östergård and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification, IEEE Trans. Inform. Theory, to appear]; there are 117821 such (13,512,3) codes. By applying a switching operation to those codes, two more (13,512,3) codes are obtained, which are then not doubly shortened perfect codes.

preprint2010arXiv

The number of Latin squares of order 11

Constructive and nonconstructive techniques are employed to enumerate Latin squares and related objects. It is established that there are (i) 2036029552582883134196099 main classes of Latin squares of order 11; (ii) 6108088657705958932053657 isomorphism classes of one-factorizations of $K_{11,11}$ ; (iii) 12216177315369229261482540 isotopy classes of Latin squares of order 11; (iv) 1478157455158044452849321016 isomorphism classes of loops of order 11; and (v) 19464657391668924966791023043937578299025 isomorphism classes of quasigroups of order 11. The enumeration is constructive for the 1151666641 main classes with an autoparatopy group of order at least 3.

preprint2010arXiv

The Perfect Binary One-Error-Correcting Codes of Length 15: Part II--Properties

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 was recently carried out in [P. R. J. Östergård and O. Pottonen, "The perfect binary one-error-correcting codes of length 15: Part I--Classification," IEEE Trans. Inform. Theory vol. 55, pp. 4657--4660, 2009]. In the current accompanying work, the classified codes are studied in great detail, and their main properties are tabulated. The results include the fact that 33 of the 80 Steiner triple systems of order 15 occur in such codes. Further understanding is gained on full-rank codes via switching, as it turns out that all but two full-rank codes can be obtained through a series of such transformations from the Hamming code. Other topics studied include (non)systematic codes, embedded one-error-correcting codes, and defining sets of codes. A classification of certain mixed perfect codes is also obtained.

preprint2009arXiv

The Perfect Binary One-Error-Correcting Codes of Length 15: Part I--Classification

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 is presented. There are 5983 such inequivalent perfect codes and 2165 extended perfect codes. Efficient generation of these codes relies on the recent classification of Steiner quadruple systems of order 16. Utilizing a result of Blackmore, the optimal binary one-error-correcting codes of length 14 and the (15, 1024, 4) codes are also classified; there are 38408 and 5983 such codes, respectively.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Patric R. J. Östergård

Research overview

Is this your work?

16 publications

Steiner Triple Systems of Order 21 with Subsystems

Constructing error-correcting binary codes using transitive permutation groups

The chromatic number of the square of the 8-cube

There is No McLaughlin Geometry

A coloring of the square of the 8-cube with 13 colors

Further Results on the Classification of MDS Codes

New Lower Bounds for the Shannon Capacity of Odd Cycles

Planar Hypohamiltonian Graphs on 40 Vertices

Non-existence of a ternary constant weight $(16, 5, 15; 2048)$ diameter perfect code

On the Classification of MDS Codes

The quaternary complex Hadamard matrices of orders 10, 12, and 14

On Optimal Binary One-Error-Correcting Codes of Lengths $2^m-4$ and $2^m-3$

Two Optimal One-Error-Correcting Codes of Length 13 That Are Not Doubly Shortened Perfect Codes

The number of Latin squares of order 11

The Perfect Binary One-Error-Correcting Codes of Length 15: Part II--Properties

The Perfect Binary One-Error-Correcting Codes of Length 15: Part I--Classification

See the researcher in context

Building this map preview

Patric R. J. Östergård

Research overview

Is this your work?

16 publications

Steiner Triple Systems of Order 21 with Subsystems

Constructing error-correcting binary codes using transitive permutation groups

The chromatic number of the square of the 8-cube

There is No McLaughlin Geometry

A coloring of the square of the 8-cube with 13 colors

Further Results on the Classification of MDS Codes

New Lower Bounds for the Shannon Capacity of Odd Cycles

Planar Hypohamiltonian Graphs on 40 Vertices

Non-existence of a ternary constant weight (16,5,15;2048)(16, 5, 15; 2048)(16,5,15;2048) diameter perfect code

On the Classification of MDS Codes

The quaternary complex Hadamard matrices of orders 10, 12, and 14

On Optimal Binary One-Error-Correcting Codes of Lengths 2m−42^m-42m−4 and 2m−32^m-32m−3

Two Optimal One-Error-Correcting Codes of Length 13 That Are Not Doubly Shortened Perfect Codes

The number of Latin squares of order 11

The Perfect Binary One-Error-Correcting Codes of Length 15: Part II--Properties

The Perfect Binary One-Error-Correcting Codes of Length 15: Part I--Classification

See the researcher in context

Building this map preview

Non-existence of a ternary constant weight $(16, 5, 15; 2048)$ diameter perfect code

On Optimal Binary One-Error-Correcting Codes of Lengths $2^m-4$ and $2^m-3$