PreprintarXiv licencearXiv
Separating hash families with large universe II
Abstract
For fixed integers t,k≥ 2, put N=(t−1)(k−1)+1. We prove that the maximum universe size of a t-perfect hash family of length N over an alphabet of size q satisfies $ p_t(N,q)\ge q^{k-o(1)}$. Together with monotonicity in the length, this gives a positive answer to a question of Blackburn, Etzion, Stinson and Zaverucha for every choice of feasible parameters. Our proof combines the Nash--Williams--Tutte theorem, a graph-theoretic elimination argument, and a solution-free-set theorem established in our previous work.
Related
- Finding large families of rational curves through Bend-and-Break
- Large Maximal Intersecting Families with Covering Number Three
- Structure of large t-intersecting families I: Stability for the Hilton--Milner--Frankl theorem
- Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige
- Moments and Large Geometric Monodromy for Linearly Constrained Kloosterman Families
BibTeX
@misc{wei2026separating,
title = {{Separating hash families with large universe II}},
author = {Xin Wei and Gennian Ge},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41353},
eprint = {2610.41353},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41353},
}
RIS
TY - UNPB
TI - Separating hash families with large universe II
AU - Xin Wei
AU - Gennian Ge
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41353
UR - https://arxiv.org/abs/2610.41353
AB - For fixed integers t,k≥ 2, put N=(t−1)(k−1)+1. We prove that the maximum universe size of a t-perfect hash family of length N over an alphabet of size q satisfies $ p_t(N,q)\ge q^{k-o(1)}$. Together with monotonicity in the length, this gives a positive answer to a question of Blackburn, Etzion, Stinson and Zaverucha for every choice of feasible parameters. Our proof combines the Nash--Williams--Tutte theorem, a graph-theoretic elimination argument, and a solution-free-set theorem established in our previous work.
ER -