We study the problem of finding the largest numberT(n,m) of ternary vectors of lengthnsuch that for any three distinct vectors there are at leastmcoordinates where they pairwise differ. This problem is a special case of the perfectk-hashing problem in theoretical computer science, corresponding to thek= 3 case. Form= 1, we get the classical trifference problem which is wide open. We prove upper and lower bounds onT(n,m) for various ranges of the parametermand determine the phase transition threshold onm=m(n) whereT(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.

Abstract In this paper, we study the cardinality of the smallest set of lines of the finite projective spaces $${{\,\textrm{PG}\,}}(n, q)$$ PG ( n , q ) such that every plane is incident with at least one line of the set. This is the first main open problem concerning the minimum size of (s, t)-blocking sets in $${{\,\textrm{PG}\,}}(n,q)$$ PG ( n , q ) , where we set $$s=2$$ s = 2 and $$t=1$$ t = 1 . In $${{\,\textrm{PG}\,}}(n,q)$$ PG ( n , q ) , an (s, t)-blocking set refers to a set of t-spaces such that each s-space is incident with at least one chosen t-space. This is a notoriously difficult problem, as it is equivalent to determining the size of certain q-Turán designs and q-covering designs. We present an improvement on the upper bounds of Etzion and of Metsch via a refined scheme for a recursive construction, which in fact enables improvement in the general case as well.

We prove an asymptotic result on the maximum number of k-vertex subtrees in binary trees of given order. This problem turns out to be equivalent to determine the maximum number of k+2-cycles in n-vertex outerplanar graphs, thus we settle the generalised outerplanar Turán number for all cycles. We also determine the exponential growth of the generalised outerplanar Turán number of paths Pk as a function of k which implies the order of magnitude of the generalised outerplanar Turán number of arbitrary trees. The bounds are strongly related to the sequence of Catalan numbers.

Abstract The long-standing Erdős–Faber–Lovász conjecture states that every n-uniform linear hypergaph with n edges has a proper vertex-coloring using n colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erdős–Faber–Lovász conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.

The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the vertices and edges of $F$ with independent sets of size $r$ and copies of $K_{r,r}$, respectively. For bipartite graphs $F$, very little is known about the order of magnitude of the Turán number of $F[r]$. In this paper we prove that ${ex}(n,C_6[2])=O(n^{5/3})$ and, more generally, for any positive integer $t$, ${ex}(n,\theta_{3,t}[2])=O(n^{5/3})$. This is tight when $t$ is sufficiently large.

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension$k$over the$q$-element Galois field which is linear in both$q$and$k$, hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well.

Let ℱ be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in ℱ we have that |A| = a, |B| = b, and A ∩ B = Ø. Furthermore, ℱ is weakly cross-intersecting if for any (Ai , Bi ), (Aj , Bj ) ∈ ℱ with i ≠ j we have th