Search

Given a finite grid in R2, how many lines are needed to cover all but one point at least k times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball–Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball–Serra and provide an asymptotic answer for almost all grids. For the standard grid {0, …, n − 1} × {0, …, n − 1}, we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments., Discrete Mathematics and Optimization

We study the problem of determining the minimum number of affine subspaces of codimension that are required to cover all points of at least times while covering the origin at most times. The case is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for. The value of also follows from a well-known theorem of Alon and FÜredi about coverings of finite grids in affine spaces over arbitrary fields. Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for we have, while for we have, and obtain asymptotic results between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory., Discrete Mathematics and Optimization

We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given $d$, we ask for the largest value of $n$, denoted $R_f(d)$, for which there exists a fixed-point-free labeling of $\overset{\tiny\leftrightarrow}{K}_n$. Determining $R_f(d)$ for all $d >0$ is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra, who proved that $d \leq R_f(d) \leq d^4+d$ and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound $R_f(d) \leq d^{2 + o(1)}$, yielding an efficient ${{(1-\varepsilon)}}$-EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$; this improves the bound of $O(n^{0.8})$ of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. Additionally, we prove the stronger upper bound $2d-2$, in the case where all edge-labels are permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$, was recently considered by Alon and Krivelevich and by M\'{e}sz\'{a}ros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.