English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Separating hash families are useful combinatorial structures which aregeneralizations of many well-studied objects in combinatorics, cryptography andcoding theory. In this paper, using tools from graph theory and additive numbertheory, we solve several open problems and conjectures concerning bounds andconstructions for separating hash families. Firstly, we discover that thecardinality of a separating hash family satisfies a Johnson-type inequality. Asa result, we obtain a new upper bound, which is superior to all previous ones.Secondly, we present a construction for an infinite class of perfect hashfamilies. It is based on the Hamming graphs in coding theory and generalizesmany constructions that appeared before. It provides an affirmative answer toboth Bazrafshan-Trung's open problem on separating hash families andAlon-Stav's conjecture on parent-identifying codes. Thirdly, let $p_t(N,q)$denote the maximal cardinality of a $t$-perfect hash family of length $N$ overan alphabet of size $q$. Walker II and Colbourn conjectured that$p_3(3,q)=o(q^2)$. We verify this conjecture by proving$q^{2-o(1)}<p_3(3,q)=o(q^2)$. Our proof can be viewed as an application ofRuzsa-Szemer{\'e}di's (6,3)-theorem. We also prove$q^{2-o(1)}<p_4(4,q)=o(q^2)$. Two new notions in graph theory and additivenumber theory, namely rainbow cycles and $R$-sum-free sets, are introduced toprove this result. These two bounds support a question of Blackburn, Etzion,Stinson and Zaverucha. Finally, we establish a bridge between perfect hashfamilies and hypergraph Tur{\'a}n problems. This connection has not beennoticed before. As a consequence, many new results and problems arise.

Separating hash families: A Johnson-type bound and new constructions