On the size of subsets of Fⁿ_q avoiding solutions to linear systems with repeated columns

Consider a system of m balanced linear equations in k variables with coefficients in F_q. If k ⩾ 2m + 1, then a routine application of the slice rank method shows that there are constants β, γ ⩾ 1 with γ < q such that, for every subset S ⊆ Fⁿq of size at least β · γⁿ, the system has a solution (x₁...

Enumerating all bilocal Clifford distillation protocols through symmetry reduction

Entanglement distillation is an essential building block in quantum communication protocols. Here, we study the class of near-term implementable distillation protocols that use bilocal Clifford operations followed by a single round of communication. We introduce tools to enumerate and optimise over all protocols for up to n = 5 (not...

Achieving Sybil-Proofness in DistributedWork Systems

In a multi-agent system where agents provide quantifiable work for each other on a voluntary basis, reputation mechanisms are incorporated to induce cooperation. Hereby agents assign their peers numerical scores based on their reported transaction histories. In such systems, adversaries can launch an attack by creating fake identities called...

Constructing tree decompositions of graphs with bounded gonality

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related...

Integer packing sets form a well-quasi-ordering

An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y≤x is in the set as well. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a recently...

Computing graph gonality is hard

There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker-Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool....

Constructing tree decompositions of graphs with bounded gonality

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related...

Treewidth is a lower bound on graph gonality

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. Graphs for which equality holds include the grid graphs and the complete multipartite graphs. We prove that the treewidth lower bound also holds for metric graphs (tropical curves) by constructing for any positive rank divisor on a metric...

Het Cap Set-probleem

Mei vorig jaar zorgde de Nederlandse wiskundige Dion Gijswijt van de TU Delft samen met Jordan Ellenberg (University of Wisconsin) voor een doorbraak in het Cap Set-probleem. In dit artikel bespreken Aart Blokhuis en Dion Gijswijt het probleem en de gevonden oplossing aan de hand van het kaartspel SET

On large subsets of Fnq with no three-termarithmetic progression

In this note, we show that the method of Croot, Lev, and Pach can be used to bound the size of a subset of F n q  Fqn with no three terms in arithmetic progression by c n  cn with c&lt;q c&lt;q . For q=3 q=3 , the problem of finding the largest subset of F n 3  F3n with no three terms in arithmetic progression is called the <i>cap set problem</i...

The power of shaking hands