Metraipolis › archive › dc_88494fa9aba7

Separating hash families with large universe II — arXiv:2610.41353

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41353
License (as archived)
CC0-1.0
Archived
2026-11-03T05:44:32.005Z
SHA-256 of the archived text
758027a1e3066bb32e69753faa1fdcb313ae7f2cd094d642663e8e79908fe051
Stable URL of this page
https://metraipolis.com/documento/dc_88494fa9aba7

How to cite

Separating hash families with large universe II — arXiv:2610.41353 — arXiv (en), https://arxiv.org/abs/2610.41353 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_88494fa9aba7 (Metraipolis archive dc_88494fa9aba7, sha256 758027a1e3066bb32e69753faa1fdcb313ae7f2cd094d642663e8e79908fe051)
BibTeX
@misc{dc88494fa9aba7,
  title = {Separating hash families with large universe II — arXiv:2610.41353},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41353},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_88494fa9aba7; sha256 758027a1e3066bb32e69753faa1fdcb313ae7f2cd094d642663e8e79908fe051},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41353. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For fixed integers $t,k\ge 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41353 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:32:16.991Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).