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. A graph [Formula: see text] is said to be [Formula: see text]-Ramsey for a [Formula: see text]-tuple of graphs [Formula: see text], denoted by [Formula: see text], if every [Formula: see text]-edge-coloring of [Formula: see text] contains a monochromatic copy of [Formula: see text] in color [Formula: see text] for some [Formula: see text]. Let [Formula: see text] denote the smallest minimum degree of [Formula: see text] over all graphs [Formula: see text] that are minimal [Formula: see text]-Ramsey for [Formula: see text] (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter [Formula: see text] has been studied by several groups of authors, their main focus being on the symmetric case, where [Formula: see text] for all [Formula: see text]. 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 [Formula: see text] when [Formula: see text] 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 [Formula: see text] in terms of the size of the cliques [Formula: see text], 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.

A famous conjecture of Ryser states that every $r$-partite hypergraph has vertex cover number at most $r - 1$ times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as $r$-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins, and Szabó that all 3-Ryser hypergraphs with matching number $\nu > 1$ are essentially obtained by taking $\nu$ disjoint copies of intersecting 3-Ryser hypergraphs. Abu-Khazneh showed that such a characterization is false for $r = 4$ by giving a computer generated example of a 4-Ryser hypergraph with $\nu = 2$ whose vertex set cannot be partitioned into two sets such that we have an intersecting 4-Ryser hypergraph on each of these parts. Here we construct first infinite families of $r$-Ryser hypergraphs, for any fixed matching number $\nu > 1$, that are truly nonintersecting in the sense that they do not contain two vertex disjoint intersecting $r$-Ryser subhypergraphs.