2020/02/25 by Simone Costa, Costa, Simone, Marco Dalai +1 · 1 citation
Computer Science · Engineering · Mathematics · #68R05 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2002.11025
openalex publication_date 2020/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let C⊆ \1,…,k\n be such that for any k distinct elements of C there exists a coordinate where they all differ simultaneously. Fredman and Komlós studied upper and lower bounds on the largest cardinality of such a set C, in particular proving that as n→∞, |C|≤ exp(n k!/kk-1+o(n)). Improvements over this result where first derived by different authors for k=4. More recently, Guruswami and Riazanov showed that the coefficient k!/kk-1 is certainly not tight for any k>3, although they could only determine explicit improvements for k=5,6. For larger k, their method gives numerical values modulo a conjecture on the maxima of certain polynomials. In this paper, we first prove their conjecture, completing the explicit computation of an improvement over the Fredman-Komlós bound for any k. Then, we develop a different method which gives substantial improvements for k=5,6.