Given a finite grid in R², 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.

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.

A graph G is said to be q-Ramsey for a q-tuple of graphs (H₁,..., H_q), denoted by G →q (H₁,..., H_q), if every q-edge-coloring of G contains a monochromatic copy of Hi in color i for some i ε [q]. Let sq(H1,..., Hq) denote the smallest minimum degree of G over all graphs G that are minimal q-Ramsey for (H₁,..., H_q) (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdos, and Lovasz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter sq has been studied by several groups of authors, their main focus being on the symmetric case, where Hi ≅ H for all i ε [q]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine s₂(H₁, H₂) when (H₁, H₂) is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on s_q(Cℓ,..., Cℓ, K_t,..., K_t) in terms of the size of the cliques t, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.