Search

A vector space partition $\mathcal{P}$ of the projective space $\operatorname{PG}(v-1,q)$ is a set of subspaces in $\operatorname{PG}(v-1,q)$ which partitions the set of points. We say that a vector space partition $\mathcal{P}$ has type $(v-1)^{m_{v-1}} \dots 2^{m_2}1^{m_1}$ if precisely $m_i$ of its elements have dimension $i$, where $1\le i\le v-1$. Here we determine all possible types of vector space partitions in $\operatorname{PG}(7,2)$., 27 pages

We determine the minimum possible column multiplicity of even, doubly-, and triply-even codes given their length. This refines a classification result for the possible lengths of $q^r$-divisible codes over $\mathbb{F}_q$. We also give a few computational results for field sizes $q>2$. Non-existence results of divisible codes with restricted column multiplicities for a given length have applications e.g. in Galois geometry and can be used for upper bounds on the maximum cardinality of subspace codes., 26 pages, 7 tables

A \emph{subcube partition} is a partition of the Boolean cube $\{0,1\}^n$ into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are singletons and the entire partition. A subcube partition is tight if it "mentions" all coordinates. We study extremal properties of tight irreducible subcube partitions: minimal size, minimal weight, maximal number of points, maximal size, and maximal minimum dimension. We also consider the existence of homogeneous tight irreducible subcube partitions, in which all subcubes have the same dimensions. We additionally study subcube partitions of $\{0,\dots,q-1\}^n$, and partitions of $\mathbb{F}_2^n$ into affine subspaces, in both cases focusing on the minimal size. Our constructions and computer experiments lead to several conjectures on the extremal values of the aforementioned properties., 38 pages

In this paper, we give a geometric construction of the three strong non-lifted $(3\mod{5})$-arcs in $\operatorname{PG}(3,5)$ of respective sizes 128, 143, and 168, and construct an infinite family of non-lifted, strong $(t\mod{q})$-arcs in $\operatorname{PG}(r,q)$ with $t=(q+1)/2$ for all $r\ge3$ and all odd prime powers $q$., Comment: 11 pages

An affine vector space partition of $\operatorname{AG}(n,q)$ is a set of proper affine subspaces that partitions the set of points. Here we determine minimum sizes and enumerate equivalence classes of affine vector space partitions for small parameters. We also give parametric constructions for arbitrary field sizes., Comment: 24 pages

A linear code over $\mathbb{F}_q$ with the Hamming metric is called $\Delta$-divisible if the weights of all codewords are divisible by $\Delta$. They have been introduced by Harold Ward a few decades ago. Applications include subspace codes, partial spreads, vector space partitions, and distance optimal codes. The determination of the possible lengths of projective divisible codes is an interesting and comprehensive challenge., Comment: 105 pages; typos corrected

Subspace codes are the $q$-analog of binary block codes in the Hamming metric. Here the codewords are vector spaces over a finite field. They have e.g. applications in random linear network coding, distributed storage, and cryptography. In this chapter we survey known constructions and upper bounds for subspace codes., 103 pages

Many real-world voting systems consist of voters that occur in just two different types. Indeed, each voting system with a {\lq\lq}House{\rq\rq} and a {\lq\lq}Senat{\rq\rq} is of that type. Here we present structural characterizations and explicit enumeration formulas for these so-called bipartite simple games., 13 pages

We consider integers whose squares have just three decimal digits. Examples are e.g. given by $2108436491907081488939581538^2 = 4445504440405440505004450045555054500055550554550445444$ and $10100000000010401000000000101^2 = 102010000000210100200000110221001000002101002000000010201$. The aim of this paper is to summarize the current knowledge on squares with three digits, scattered around webpages and newsgroup postings, and to add a few new insights. While we will mostly focus on the base $B=10$, several results are presented for general values of $B$. The used mathematical tools are completely elementary. However, we give complete proofs of all statements or explicitly state them as conjectures., 42 pages, 6 tables; typos corrected

The proof of the non-existence of Griesmer $[104, 4, 82]_5$-codes is just one of many examples where extendability results are used. In a series of papers Landjev and Rousseva have introduced the concept of $(t\operatorname{mod} q)$-arcs as a general framework for extendability results for codes and arcs. Here we complete the known partial classification of $(3 \operatorname{mod} 5)$-arcs in $\operatorname{PG}(3,5)$ and uncover two missing, rather exceptional, examples disproving a conjecture of Landjev and Rousseva. As also the original non-existence proof of Griesmer $[104, 4, 82]_5$-codes is affected, we present an extended proof to fill this gap., 33 pages, 15 tables; typos corrected

A basic problem for constant dimension codes is to determine the maximum possible size $A_q(n,d;k)$ of a set of $k$-dimensional subspaces in $\mathbb{F}_q^n$, called codewords, such that the subspace distance satisfies $d_S(U,W):=2k-2\dim(U\cap W)\ge d$ for all pairs of different codewords $U$, $W$. Constant dimension codes have applications in e.g.\ random linear network coding, cryptography, and distributed storage. Bounds for $A_q(n,d;k)$ are the topic of many recent research papers. Providing a general framework we survey many of the latest constructions and show up the potential for further improvements. As examples we give improved constructions for the cases $A_q(10,4;5)$, $A_q(11,4;4)$, $A_q(12,6;6)$, and $A_q(15,4;4)$. We also derive general upper bounds for subcodes arising in those constructions., Comment: 19 pages; typos corrected

We classify 8-divisible binary linear codes with minimum distance 24 and small length. As an application we consider the codes associated to nodal sextics with 65 ordinary double points., Comment: 53 pages

One of the main problems in random network coding is to compute good lower and upper bounds on the achievable cardinality of the so-called subspace codes in the projective space $\mathcal{P}_q(n)$ for a given minimum distance. The determination of the exact maximum cardinality is a very tough discrete optimization problem involving a huge number of symmetries. Besides some explicit constructions for \textit{good} subspace codes several of the most success full constructions involve the solution of discrete optimization subproblems itself, which mostly have not been not been solved systematically. Here we consider the multilevel a.k.a.\ Echelon--Ferrers construction and given lower and upper bounds for the achievable cardinalities. From a more general point of view, we solve maximum clique problems in weighted graphs, where the weights can be polynomials in the field size $q$., Comment: 95 pages

We present an algorithm for the classification of linear codes over finite fields, based on lattice point enumeration. We validate a correct implementation of our algorithm with known classification results from the literature, which we partially extend to larger ranges of parameters., 12 pages, 5 tables

We construct strongly walk-regular graphs as coset graphs of the duals of codes with three non-zero homogeneous weights over $\mathbb{Z}_{p^m},$ for $p$ a prime, and more generally over chain rings of depth $m$, and with a residue field of size $q$, a prime power. Infinite families of examples are built from Kerdock and generalized Teichm\"uller codes. As a byproduct, we give an alternative proof that the Kerdock code is nonlinear., Comment: 28 pages, 6 tables

The minimum distance of all binary linear codes with dimension at most eight is known. The smallest open case for dimension nine is length $n=46$ with known bounds $19\le d\le 20$. Here we present a $[46,9,20]_2$ code and show its uniqueness. Interestingly enough, this unique optimal code is asymmetric, i.e., it has a trivial automorphism group. Additionally, we show the non-existence of $[47,10,20]_2$ and $[85,9,40]_2$ codes., 7 pages, 3 tables, typos corrected

Constant dimension codes are used for error control in random linear network coding, so that constructions for these codes with large cardinality have achieved wide attention in the last decade. Here, we improve the so-called linkage construction. Known upper bounds for constant dimension codes containing lifted MRD codes are generalized., Comment: 13 pages; earlier versions contain a serious flaw in the statement that is now named Conjecture 4.6; typos corrected

A projective linear code over $\mathbb{F}_q$ is called $\Delta$-divisible if all weights of its codewords are divisible by $\Delta$. Especially, $q^r$-divisible projective linear codes, where $r$ is some integer, arise in many applications of collections of subspaces in $\mathbb{F}_q^v$. One example are upper bounds on the cardinality of partial spreads. Here we survey the known results on the possible lengths of projective $q^r$-divisible linear codes., Comment: 38 pages

A well known class of objects in combinatorial design theory are {group divisible designs}. Here, we introduce the $q$-analogs of group divisible designs. It turns out that there are interesting connections to scattered subspaces, $q$-Steiner systems, design packings and $q^r$-divisible projective sets. We give necessary conditions for the existence of $q$-analogs of group divsible designs, construct an infinite series of examples, and provide further existence results with the help of a computer search. One example is a $(6,3,2,2)_2$ group divisible design over $\operatorname{GF}(2)$ which is a design packing consisting of $180$ blocks that such every $2$-dimensional subspace in $\operatorname{GF}(2)^6$ is covered at most twice., 18 pages, 3 tables, typos corrected

A vector space partition $\mathcal{P}$ in $\mathbb{F}_q^v$ is a set of subspaces such that every $1$-dimensional subspace of $\mathbb{F}_q^v$ is contained in exactly one element of $\mathcal{P}$. Replacing "every point" by "every $t$-dimensional subspace", we generalize this notion to vector space $t$-partitions and study their properties. There is a close connection to subspace codes and some problems are even interesting and unsolved for the set case $q=1$., 12 pages, typos corrected

We show that there is a binary subspace code of constant dimension 3 in ambient dimension 7, having minimum distance 4 and cardinality 333, i.e., $333 \le A_2(7,4;3)$, which improves the previous best known lower bound of 329. Moreover, if a code with these parameters has at least 333 elements, its automorphism group is in one of $31$ conjugacy classes. This is achieved by a more general technique for an exhaustive search in a finite group that does not depend on the enumeration of all subgroups., 18 pages; typos corrected

For which positive integers $n,k,r$ does there exist a linear $[n,k]$ code $C$ over $\mathbb{F}_q$ with all codeword weights divisible by $q^r$ and such that the columns of a generating matrix of $C$ are projectively distinct? The motivation for studying this problem comes from the theory of partial spreads, or subspace codes with the highest possible minimum distance, since the set of holes of a partial spread of $r$-flats in $\operatorname{PG}(v-1,\mathbb{F}_q)$ corresponds to a $q^r$-divisible code with $k\leq v$. In this paper we provide an introduction to this problem and report on new results for $q=2$., 10 pages, 3 tables

We study asymptotic lower and upper bounds for the sizes of constant dimension codes with respect to the subspace or injection distance, which is used in random linear network coding. In this context we review known upper bounds and show relations between them. A slightly improved version of the so-called linkage construction is presented which is e.g. used to construct constant dimension codes with subspace distance $d=4$, dimension $k=3$ of the codewords for all field sizes $q$, and sufficiently large dimensions $v$ of the ambient space, that exceed the MRD bound, for codes containing a lifted MRD code, by Etzion and Silberstein., Comment: 30 pages, 3 tables

It is shown that the maximum size $A_2(8,6;4)$ of a binary subspace code of packet length $v=8$, minimum subspace distance $d=4$, and constant dimension $k=4$ is at most $272$. In Finite Geometry terms, the maximum number of solids in $\operatorname{PG}(7,2)$, mutually intersecting in at most a point, is at most $272$. Previously, the best known upper bound $A_2(8,6;4)\le 289$ was implied by the Johnson bound and the maximum size $A_2(7,6;3)=17$ of partial plane spreads in $\operatorname{PG}(6,2)$. The result was obtained by combining the classification of subspace codes with parameters $(7,17,6;3)_2$ and $(7,34,5;\{3,4\})_2$ with integer linear programming techniques. The classification of $(7,33,5;\{3,4\})_2$ subspace codes is obtained as a byproduct., Comment: 9 pages

In this article, the partial plane spreads in $PG(6,2)$ of maximum possible size $17$ and of size $16$ are classified. Based on this result, we obtain the classification of the following closely related combinatorial objects: Vector space partitions of $PG(6,2)$ of type $(3^{16} 4^1)$, binary $3\times 4$ MRD codes of minimum rank distance $3$, and subspace codes with parameters $(7,17,6)_2$ and $(7,34,5)_2$., 31 pages, 9 tables

It is shown that the automorphism group of a binary $q$-analog of the Fano plane is either trivial or of order $2$., 10 pages

One of the main problems of subspace coding asks for the maximum possible cardinality of a subspace code with minimum distance at least $d$ over $\mathbb{F}_q^n$, where the dimensions of the codewords, which are vector spaces, are contained in $K\subseteq\{0,1,\dots,n\}$. In the special case of $K=\{k\}$ one speaks of constant dimension codes. Since this (still) emerging field is very prosperous on the one hand side and there are a lot of connections to classical objects from Galois geometry it is a bit difficult to keep or to obtain an overview about the current state of knowledge. To this end we have implemented an on-line database of the (at least to us) known results at \url{subspacecodes.uni-bayreuth.de}. The aim of this recurrently updated technical report is to provide a user guide how this technical tool can be used in research projects and to describe the so far implemented theoretic and algorithmic knowledge., 44 pages, 6 tables, 7 screenshots

A partial $t$-spread in $\mathbb{F}_q^n$ is a collection of $t$-dimensional subspaces with trivial intersection such that each non-zero vector is covered at most once. We present some improved upper bounds on the maximum sizes., Comment: 4 pages

Constant-dimension codes with the maximum possible minimum distance have been studied under the name of partial spreads in Finite Geometry for several decades. Not surprisingly, for this subclass typically the sharpest bounds on the maximal code size are known. The seminal works of Beutelspacher and Drake \& Freeman on partial spreads date back to 1975, and 1979, respectively. From then until recently, there was almost no progress besides some computer-based constructions and classifications. It turns out that vector space partitions provide the appropriate theoretical framework and can be used to improve the long-standing bounds in quite a few cases. Here, we provide a historic account on partial spreads and an interpretation of the classical results from a modern perspective. To this end, we introduce all required methods from the theory of vector space partitions and Finite Geometry in a tutorial style. We guide the reader to the current frontiers of research in that field, including a detailed description of the recent improvements., 30 pages, 1 table

A set of $n$-lattice points in the plane, no three on a line and no four on a circle, such that all pairwise distances and all coordinates are integral is called an $n$-cluster (in $\mathbb{R}^2$). We determine the smallest existent $7$-cluster with respect to its diameter. Additionally we provide a toolbox of algorithms which allowed us to computationally locate over 1000 different $7$-clusters, some of them having huge integer edge lengths. On the way, we exhaustively determined all Heronian triangles with largest edge length up to $6\cdot 10^6$., 18 pages, 2 figures, 2 tables

It is shown that the maximal size of a $2$-arc in the projective Hjelmslev plane over $\mathbb{Z}_{25}$ is $21$, and the $(21,2)$-arc is unique up to isomorphism. Furthermore, all maximal $(20,2)$-arcs in the affine Hjelmslev plane over $\mathbb{Z}_{25}$ are classified up to isomorphism., 20 pages, 3 tables

We perform an exhaustive search for the minimum 4-regular unit distance graph resulting in a lower bound of 34 vertices., 11 pages, 5 figures

We study criteria attesting that a given graph can not be embedded in the plane so that neighboring vertices are at unit distance apart and the straight line edges do not cross., 9 pages, 1 table, 5 figures

We consider point sets in $\mathbb{Z}_n^2$ where no three points are on a line - also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small $n$., 13 pages, 7 tables, 3 figures

A graph $G=(V,E)$ is called a unit-distance graph in the plane if there is an injective embedding of $V$ in the plane such that every pair of adjacent vertices are at unit distance apart. If additionally the corresponding edges are non-crossing and all vertices have the same degree $r$ we talk of a regular matchstick graph. Due to Euler's polyhedron formula we have $r\le 5$. The smallest known $4$-regular matchstick graph is the so called Harborth graph consisting of $52$ vertices. In this article we prove that no finite $5$-regular matchstick graph exists., Comment: 15 pages, 12 figures, 2 tables

We consider 3-regular planar matchstick graphs, i.e. those which have a planar embedding such that all edge lengths are equal, with given girth g. For girth 3 it is known that such graphs exist if and only if the number of vertices n is an even integer larger or equal to 8. Here we prove that such graphs exist for girth g=4 if and only if n is even and at least 20. We provide an example for girth g=5 consisting of 180 vertices., Comment: 18 pages, 1 table, 8 figures

Gvozdeva, Hemaspaandra, and Slinko (2011) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class $\mathcal{C}_��$ consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least 1 and each losing coalition a weight of at most $��$. For a given game the minimal possible value of $��$ is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation beween this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered., 26 pages, 4 tables

We combine the parametric Barvinok algorithm with a generation algorithm for a finite list of suitably chosen discrete sub-cases on the enumeration of complete simple games, i.e. a special subclass of monotone Boolean functions. Recently, Freixas et al. have proven an enumeration formula for complete simple games with two types of voters. We will provide a shorter proof and an enumeration formula for complete simple games with two shift-minimal winning coalitions., Comment: 13 pages, 1 figure, 6 tables, submitted to ISSAC 2010

We consider point sets in the affine plane $\mathbb{F}_q^2$ where each Euclidean distance of two points is an element of $\mathbb{F}_q$. These sets are called integral point sets and were originally defined in $m$-dimensional Euclidean spaces $\mathbb{E}^m$. We determine their maximal cardinality $\mathcal{I}(\mathbb{F}_q,2)$. For arbitrary commutative rings $\mathcal{R}$ instead of $\mathbb{F}_q$ or for further restrictions as no three points on a line or no four points on a circle we give partial results. Additionally we study the geometric structure of the examples with maximum cardinality., 22 pages, 4 figures

Geometrical objects with integral side lengths have fascinated mathematicians through the ages. We call a set $P=\{p_1,...,p_n\}\subset\mathbb{Z}^2$ a maximal integral point set over $\mathbb{Z}^2$ if all pairwise distances are integral and every additional point $p_{n+1}$ destroys this property. Here we consider such sets for a given cardinality and with minimum possible diameter. We determine some exact values via exhaustive search and give several constructions for arbitrary cardinalities. Since we cannot guarantee the maximality in these cases we describe an algorithm to prove or disprove the maximality of a given integral point set. We additionally consider restrictions as no three points on a line and no four points on a circle., 23 pages, 10 figures, 4 tables

There are many papers studying properties of point sets in the Euclidean space $\mathbb{E}^m$ or on integer grids $\mathbb{Z}^m$, with pairwise integral or rational distances. In this article we consider the distances or coordinates of the point sets which instead of being integers are elements of $\mathbb{Z} / \mathbb{Z}n$, and study the properties of the resulting combinatorial structures., 20 pages, 3 figures

In this paper we construct constant dimension space codes with prescribed minimum distance. There is an increased interest in space codes since a paper by Koetter and Kschischang were they gave an application in network coding. There is also a connection to the theory of designs over finite fields. We will modify a method of Braun, Kerber and Laue which they used for the construction of designs over finite fields to do the construction of space codes. Using this approach we found many new constant dimension spaces codes with a larger number of codewords than previously known codes. We will finally give a table of the best found constant dimension space codes., Comment: 13 pages, 1 figure, 1 table, submitted

We determine the numbers of integral tetrahedra with diameter $d$ up to isomorphism for all $d\le 1000$ via computer enumeration. Therefore we give an algorithm that enumerates the integral tetrahedra with diameter at most $d$ in $O(d^5)$ time and an algorithm that can check the canonicity of a given integral tetrahedron with at most 6 integer comparisons. For the number of isomorphism classes of integral $4\times 4$ matrices with diameter $d$ fulfilling the triangle inequalities we derive an exact formula., Comment: 10 pages, 1 figure

Geometrical objects with integral sides have attracted mathematicians for ages. For example, the problem to prove or to disprove the existence of a perfect box, that is, a rectangular parallelepiped with all edges, face diagonals and space diagonals of integer lengths, remains open. More generally an integral point set $\mathcal{P}$ is a set of $n$ points in the $m$-dimensional Euclidean space $\mathbb{E}^m$ with pairwise integral distances where the largest occurring distance is called its diameter. From the combinatorial point of view there is a natural interest in the determination of the smallest possible diameter $d(m,n)$ for given parameters $m$ and $n$. We give some new upper bounds for the minimum diameter $d(m,n)$ and some exact values., Comment: 8 pages, 7 figures; typos corrected

Since ancient times mathematicians consider geometrical objects with integral side lengths. We consider plane integral point sets $\mathcal{P}$, which are sets of $n$ points in the plane with pairwise integral distances where not all the points are collinear. The largest occurring distance is called its diameter. Naturally the question about the minimum possible diameter $d(2,n)$ of a plane integral point set consisting of $n$ points arises. We give some new exact values and describe state-of-the-art algorithms to obtain them. It turns out that plane integral point sets with minimum diameter consist very likely of subsets with many collinear points. For this special kind of point sets we prove a lower bound for $d(2,n)$ achieving the known upper bound $n^{c_2\log\log n}$ up to a constant in the exponent. A famous question of Erd\H{o}s asks for plane integral point sets with no 3 points on a line and no 4 points on a circle. Here, we talk of point sets in general position and denote the corresponding minimum diameter by $\dot{d}(2,n)$. Recently $\dot{d}(2,7)=22 270$ could be determined via an exhaustive search., Comment: 12 pages, 5 figures

In this article we prove a conjecture of Bezdek, Brass, and Harborth concerning the maximum volume of the convex hull of any facet-to-facet connected system of n unit hypercubes in the d-dimensional Euclidean space. For d=2 we enumerate the extremal polyominoes and determine the set of possible areas of the convex hull for each n., 13 pages, 10 figures

As a generalization of polyominoes we consider edge-to-edge connected nonoverlapping unions of regular $k$-gons. For $n\le 4$ we determine formulas for the number $a_k(n)$ of generalized polyominoes consisting of $n$ regular $k$-gons. Additionally we give a table of the numbers $a_k(n)$ for small $k$ and $n$ obtained by computer enumeration. We finish with some open problems for $k$-polyominoes., 10 pages, 6 figures, 3 tables

We generalise the definition of the characteristic of an integral triangle to integral simplices and prove that each simplex in an integral point set has the same characteristic. This theorem is used for an efficient construction algorithm for integral point sets. Using this algorithm we are able to provide new exact values for the minimum diameter of integral point sets., 9 pages, 1 figure

The number of essentially different square polyominoes of order n and minimum perimeter p(n) is enumerated., 9 pages, slightly corrected version

A Diophantine figure is a set of points on the integer grid $\mathbb{Z}^{2}$ where all mutual Euclidean distances are integers. We also speak of Diophantine graphs. In this language a Diophantine figure is a complete Diophantine graph. Due to a famous theorem of Erd��s and Anning there are complete Diophantine graphs which are not contained in larger ones. We call them Erd��s-Diophantine graphs. A special class of Diophantine graphs are Diophantine carpets. These are planar triangulations of a subset of the integer grid. We give an effective construction for Erd��s-Diophantine graphs and characterize the chromatic number of Diophantine carpets., 4 pages, 1 figure