• ### A subspace code of size $333$ in the setting of a binary $q$-analog of the Fano plane(1708.06224)

March 22, 2019 math.CO, cs.IT, math.IT
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.
• ### Constructions and Bounds for Mixed-Dimension Subspace Codes(1512.06660)

Aug. 29, 2018 math.CO, cs.IT, math.IT
Codes in finite projective spaces equipped with the subspace distance have been proposed for error control in random linear network coding. The resulting so-called \emph{Main Problem of Subspace Coding} is to determine the maximum size $A_q(v,d)$ of a code in $\operatorname{PG}(v-1,\mathbb{F}_q)$ with minimum subspace distance $d$. Here we completely resolve this problem for $d\ge v-1$. For $d=v-2$ we present some improved bounds and determine $A_q(5,3)=2q^3+2$ (all $q$), $A_2(7,5)=34$. We also provide an exposition of the known determination of $A_q(v,2)$, and a table with exact results and bounds for the numbers $A_2(v,d)$, $v\leq 7$.
• ### Generalized roll-call model for the Shapley-Shubik index(1602.04331)

Aug. 8, 2018 math.CO, cs.GT
In 1996 Dan Felsenthal and Mosh\'e Machover considered the following model. An assembly consisting of $n$ voters exercises roll-call. All $n!$ possible orders in which the voters may be called are assumed to be equiprobable. The votes of each voter are independent with expectation $0<p<1$ for an individual vote {\lq\lq}yea{\rq\rq}. For a given decision rule $v$ the \emph{pivotal} voter in a roll-call is the one whose vote finally decides the aggregated outcome. It turned out that the probability to be pivotal is equivalent to the Shapley-Shubik index. Here we give an easy combinatorial proof of this coincidence, further weaken the assumptions of the underlying model, and study generalizations to the case of more than two alternatives.
• ### Heden's bound on the tail of a vector space partition(1708.01113)

May 9, 2018 math.CO
A vector space partition of $\mathbb{F}_q^v$ is a collection of subspaces such that every non-zero vector is contained in a unique element. We improve a lower bound of Heden, in a subcase, on the number of elements of the smallest occurring dimension in a vector space partition. To this end, we introduce the notion of $q^r$-divisible sets of $k$-subspaces in $\mathbb{F}_q^v$. By geometric arguments we obtain non-existence results for these objects, which then imply the improved result of Heden.
• ### Simple Games versus Weighted Voting Games(1805.02192)

May 6, 2018 cs.GT
A simple game $(N,v)$ is given by a set $N$ of $n$ players and a partition of $2^N$ into a set $\mathcal{L}$ of losing coalitions $L$ with value $v(L)=0$ that is closed under taking subsets and a set $\mathcal{W}$ of winning coalitions $W$ with $v(W)=1$. Simple games with $\alpha= \min_{p\geq 0}\max_{W\in {\cal W},L\in {\cal L}} \frac{p(L)}{p(W)}<1$ are known as weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that $\alpha\leq \frac{1}{4}n$ for every simple game $(N,v)$. We confirm this conjecture for two complementary cases, namely when all minimal winning coalitions have size $3$ and when no minimal winning coalition has size $3$. As a general bound we prove that $\alpha\leq \frac{2}{7}n$ for every simple game $(N,v)$. For complete simple games, Freixas and Kurz conjectured that $\alpha=O(\sqrt{n})$. We prove this conjecture up to a $\ln n$ factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing $\alpha$ is \NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if $\alpha<a$ is polynomial-time solvable for every fixed $a>0$.
• ### Classification of large partial plane spreads in $PG(6,2)$ and related combinatorial objects(1606.07655)

May 2, 2018 math.CO
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$.
• ### On minimum sum representations for weighted voting games(1103.1445)

May 2, 2018 math.CO
A proposal in a weighted voting game is accepted if the sum of the (non-negative) weights of the "yea" voters is at least as large as a given quota. Several authors have considered representations of weighted voting games with minimum sum, where the weights and the quota are restricted to be integers. Freixas and Molinero have classified all weighted voting games without a unique minimum sum representation for up to 8 voters. Here we exhaustively classify all weighted voting games consisting of 9 voters which do not admit a unique minimum sum integer weight representation.
• ### $q$-analogs of group divisible designs(1804.11172)

April 30, 2018 math.CO
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.
• ### On the lengths of divisible codes(1707.00650)

April 2, 2019 math.CO, cs.IT, math.IT
In this article, the effective lengths of all $q^r$-divisible linear codes over $\mathbb{F}_q$ with a non-negative integer $r$ are determined. For that purpose, the $S_q(r)$-adic expansion of an integer $n$ is introduced. It is shown that there exists a $q^r$-divisible $\mathbb{F}_q$-linear code of effective length $n$ if and only if the leading coefficient of the $S_q(r)$-adic expansion of $n$ is non-negative. Furthermore, the maximum weight of a $q^r$-divisible code of effective length $n$ is at most $\sigma q^r$, where $\sigma$ denotes the cross-sum of the $S_q(r)$-adic expansion of $n$. This result has applications in Galois geometries. A recent theorem of N{\u{a}}stase and Sissokho on the maximum sizes of partial spreads follows as a corollary. Furthermore, we get an improvement of the Johnson bound for constant dimension subspace codes.
• ### The power of the largest player(1803.04625)

April 26, 2018 cs.GT
Decisions in a shareholder meeting or a legislative committee are often modeled as a weighted game. Influence of a member is then measured by a power index. A large variety of different indices has been introduced in the literature. This paper analyzes how power indices differ with respect to the largest possible power of a non-dictatorial player. It turns out that the considered set of power indices can be partitioned into two classes. This may serve as another indication which index to use in a given application.
• ### Binary Subspace Codes in Small Ambient Spaces(1804.02219)

April 18, 2018 math.CO, cs.IT, math.IT
Codes in finite projective spaces equipped with the subspace distance have been proposed for error control in random linear network coding. Here we collect the present knowledge on lower and upper bounds for binary subspace codes for projective dimensions of at most $7$. We obtain several improvements of the bounds and perform two classifications of optimal subspace codes, which are unknown so far in the literature.
• ### Generalized vector space partitions(1803.10180)

March 27, 2018 math.CO
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$.
• ### Bounds for the Nakamura number(1711.06611)

March 16, 2018 math.CO
The Nakamura number is an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles. For symmetric quota games its number can be obtained by an easy formula. For some subclasses of simple games the corresponding Nakamura number has also been characterized. However, in general, not much is known about lower and upper bounds depending of invariants on simple, complete or weighted games. Here, we survey such results and highlight connections with other game theoretic concepts.
• ### Influence in systems with convex decisions(1803.04138)

March 12, 2018 cs.GT
Given a system where the real-valued states of the agents are aggregated by a function to a real-valued state of the entire system, we are interested in the influence of the different agents on that function. This generalizes the notion of power indices for binary voting systems to decisions over convex one-dimensional policy spaces and has applications in economics, engineering, security analysis, and other disciplines. Here, we provide a solid theoretical framework to study the question of influence in systems with convex decisions. Based on the classical Shapley-Shubik and Penrose-Banzhaf index, from binary voting, we develop two influence measures, whose properties then are analyzed. We present some results for parametric classes of aggregation functions.
• ### Approximating power by weights(1802.00497)

Feb. 1, 2018 cs.GT
Determining the power distribution of the members of a shareholder meeting or a legislative committee is a well-known problem for many applications. In some cases it turns out that power is nearly proportional to relative voting weights, which is very beneficial for both theoretical considerations and practical computations with many members. We present quantitative approximation results with precise error bounds for several power indices as well as impossibility results for such approximations between power and weights.
• ### Coset Construction for Subspace Codes(1512.07634)

Sept. 26, 2017 math.CO, cs.IT, math.IT
One of the main problems of the research area of network coding is to compute good lower and upper bounds of the achievable cardinality of so-called subspace codes in $\operatorname{PG}(n,q)$, i.e., the set of subspaces of $\mathbb{F}_q^n$, for a given minimal distance. Here we generalize a construction of Etzion and Silberstein to a wide range of parameters. This construction, named coset construction, improves or attains several of the previously best-known subspace code sizes and attains the MRD bound for an infinite family of parameters.
• ### Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound(1705.03835)

May 10, 2017 math.CO, cs.IT, math.IT
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.
• ### Upper bounds for partial spreads(1606.08581)

April 4, 2017 math.CO
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.
• ### A new upper bound for subspace codes(1703.08712)

March 25, 2017 math.CO
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.
• ### Projective divisible binary codes(1703.08291)

March 24, 2017 math.CO
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$.
• ### The nucleolus of large majority games(1310.0004)

March 24, 2017 math.OC
Members of a shareholder meeting or legislative committee have greater or smaller voting power than meets the eye if the nucleolus of the induced majority game differs from the voting weight distribution. We establish a new sufficient condition for the weight and power distributions to be equal; and we characterize the limit behavior of the nucleolus in case all relative weights become small.
• ### Partial spreads and vector space partitions(1611.06328)

March 17, 2017 math.CO
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.
• ### Characterization of threshold functions: state of the art, some new contributions and open problems(1603.00329)

March 17, 2017 cs.GT
This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the last two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions.
• ### Fair Representation and a Linear Shapley Rule(1610.05436)

Oct. 18, 2016 cs.GT
When delegations to an assembly or council represent differently sized constituencies, they are often allocated voting weights which increase in population numbers (EU Council, US Electoral College, etc.). The Penrose square root rule (PSRR) is the main benchmark for fair representation of all bottom-tier voters in the top-tier decision making body, but rests on the restrictive assumption of independent binary decisions. We consider intervals of alternatives with single-peaked preferences instead, and presume positive correlation of local voters. This calls for a replacement of the PSRR by a linear Shapley rule: representation is fair if the Shapley value of the delegates is proportional to their constituency sizes.
• ### On the Construction of High Dimensional Simple Games(1602.01581)

July 14, 2016 math.CO, cs.IT, math.IT, cs.GT
Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., "yes" and "no", every voting system can be described by a (monotone) Boolean function $\chi\colon\{0,1\}^n\rightarrow \{0,1\}$. However, its naive encoding needs $2^n$ bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using $n$ weights and one threshold. For heterogeneous agents, one can represent $\chi$ as an intersection of $k$ threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring $k\ge 2^{\frac{n}{2}-1}$ and provided a construction guaranteeing $k\le {n\choose {\lfloor n/2\rfloor}}\in 2^{n-o(n)}$. The magnitude of the worst-case situation was thought to be determined by Elkind et al.~in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number $k$ for a subclass of voting systems. As an application, we give a construction for $k\ge 2^{n-o(n)}$, i.e., there is no gain from a representation complexity point of view.