Little-o upper-bound conjecture for equal-weight separating hash families

Let C(N,q,{w1,,wt})C(N,q,\{w_1,\ldots,w_t\}) be the maximal size of an SHF(N;n,q,{w1,,wt})SHF(N;n,q,\{w_1,\ldots,w_t\}). Let t3t\ge 3 be a positive integer, set w1==wt=1w_1=\cdots=w_t=1, and assume (t1)N(t-1)\nmid N.

Little-o upper-bound conjecture.

C(N,q,{1,,1})=o(qNt1).C(N,q,\{1,\ldots,1\})=o\left(q^{\left\lceil\frac{N}{t-1}\right\rceil}\right).

The conjecture concerns the nondivisible-length case, where the known general upper bound may or may not be of the correct order. The source notes that the claim is known when N=t3N=t\ge 3, while the general case remains open; attempted use of the hypergraph removal lemma did not resolve it.

Sources & referencesView supporting material

Primary source

Gennian Ge, Chong Shangguan and Xin Wang, “Some intriguing upper bounds for separating hash families”, arXiv:1707.01758 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.