A strong s-blocking set in a projective space is a set of points that intersects each codimension-s subspace in a spanning set of the subspace. We present an explicit construction of such sets in a (k-1)-dimensional projective space over Fq of size Os(qsk), which is optimal up to the constant factor depending on s. This also yields an optimal explicit construction of affine blocking sets in Fqk with respect to codimension-(s+1) affine subspaces, and of s-minimal codes. Our approach is motivated by a recent construction of Alon, Bishnoi, Das, and Neri of strong 1-blocking sets, which uses expander graphs with a carefully chosen set of vectors as their vertex set. The main novelty of our work lies in constructing specific hypergraphs on top of these expander graphs, where tree-like configurations correspond to strong s-blocking sets. We also discuss some connections to size-Ramsey numbers of hypergraphs, which might be of independent interest.

We study the problem of finding the largest number T(n,m) of ternary vectors of length n such that for any three distinct vectors there are at least m coordinates where they pairwise differ. This problem is a special case of the perfect k-hashing problem in theoretical computer science, corresponding to the k = 3 case. For m = 1, we get the classical trifference problem which is wide open. We prove upper and lower bounds on T(n,m) for various ranges of the parameter m and determine the phase transition threshold on m = m(n) where T(n,m) jumps from constant to exponential in n. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. Moreover, we relate the trifference problem to the sunflower conjecture.

In this note, we briefly rectify oversights in the works of several authors on s_r (K_k), the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph G such that any r-colouring of the edges of G contains a monochromatic K_k, whereas no proper subgraph of G has this property. We show that s_r (K_k+1) = O(k³ r³ ln³ k), improving the best known bounds when k ≥ 8 and k² ≤ r ≤ O(k⁴/ ln⁶ k).

We use p-rank bounds on partial ovoids and classical bounds on Ramsey numbers to obtain upper bounds on the size of partial m-ovoids in finite classical polar spaces. These bounds imply the non-existence of m-ovoids for new infinite families of polar spaces. We also give a probabilistic construction of large partial m-ovoids when m grows linearly with the rank of the polar space.

In the special case of symplectic spaces over the binary field, we prove an equivalence between partial m-ovoids and a generalisation of Oddtown families from extremal set theory, studied under the name of m-nearly orthogonal sets. We give a new construction for large partial 2-ovoids in these spaces, and thus for 2-nearly orthogonal sets over the binary field. This construction uses triangle-free graphs associated with certain BCH codes, whose complements have low 2-rank, and it gives an asymptotic improvement over the previous best construction.

We give another construction of triangle-free graphs using a binary projective cap, which has low complementary rank over the reals. This improves the bounds in the recently introduced rank-Ramsey problem and provides better constructions of large partial m-ovoids for m > 2 in the binary symplectic space.

A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the (k−1)-dimensional projective space over Fq that have size at most cqk for some universal constant c. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of Fq-linear minimal codes of length n and dimension k, for every prime power q, for which n ≤ cqk. This solves one of the main open problems on minimal codes.

We prove new upper bounds on the smallest size of affine blocking sets, that is, sets of points in a finite affine space that intersect every affine subspace of a fixed codimension. We show an equivalence between affine blocking sets with respect to codimension-2 subspaces that are generated by taking a union of lines through the origin, and strong blocking sets in the corresponding projective space, which in turn are equivalent to minimal codes. Using this equivalence, we improve the current best upper bounds on the smallest size of a strong blocking set in finite projective spaces over fields of size at least 3. Furthermore, using coding theoretic techniques, we improve the current best lower bounds on a strong blocking set. Our main motivation for these new bounds is their application to trifferent codes, which are sets of ternary codes of length (Formula presented.) with the property that for any three distinct codewords there is a coordinate where they all have distinct values. Over the finite field (Formula presented.), we prove that minimal codes are equivalent to linear trifferent codes. Using this equivalence, we show that any linear trifferent code of length (Formula presented.) has size at most (Formula presented.), improving the recent upper bound of Pohoata and Zakharov. Moreover, we show the existence of linear trifferent codes of length (Formula presented.) and size at least (Formula presented.), thus (asymptotically) matching the best lower bound on trifferent codes. We also give explicit constructions of affine blocking sets with respect to codimension-2 subspaces that are a constant factor bigger than the best known lower bound. By restricting to (Formula presented.), we obtain linear trifferent codes of size at least (Formula presented.), improving the current best explicit construction that has size (Formula presented.).

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.

We prove that (Formula presented.), where (Formula presented.) is the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph (Formula presented.) such that any (Formula presented.) -colouring of the edges of (Formula presented.) contains a monochromatic (Formula presented.), whereas no proper subgraph of (Formula presented.) has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

A well-known conjecture, often attributed to Ryser, states that the cover number of an r-partite r-uniform hypergraph is at most r−1 times larger than its matching number. Despite considerable effort, particularly in the intersecting case, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Bustamante and Stein and, independently, Király and Tóthmérész considered the problem under the assumption that the hypergraph is t-intersecting, conjecturing that the cover number τ(H) of such a hypergraph H is at most r−t. In these papers, it was proven that the conjecture is true for r≤4t−1, but also that it need not be sharp; when r=5 and t=2, one has τ(H)≤2. We extend these results in two directions. First, for all t≥2 and r≤3t−1, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy τ(H)≤⌊(r−t)/2⌋+1. Second, we extend the range of t for which the conjecture is known to be true, showing that it holds for all [Formula presented]. We also introduce several related variations on this theme. As a consequence of our tight bounds, we resolve the problem for k-wise t-intersecting hypergraphs, for all k≥3 and t≥1. We further give bounds on the cover numbers of strictly t-intersecting hypergraphs and the s-cover numbers of t-intersecting hypergraphs.