Fredman–Komlós bounds and information theory

DOI10.1137/0607062zbMath0603.05034OpenAlexW2029773437MaRDI QIDQ3739153

János Körner

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607062

zbMATH Keywords

graph entropygraph coveringperfect hashingentropies of graphsFredman-Komlós lemmaseparating partition systems

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)

Related Items (36)

\(\Sigma\Pi\Sigma\) threshold formulas ⋮ On the extremal combinatorics of the Hamming space ⋮ Information compression and Varshamov-Gilbert bound ⋮ Information theoretic parameters of noncommutative graphs and convex corners ⋮ On colorful edge triples in edge-colored complete graphs ⋮ Separation and Witnesses ⋮ New bounds for perfect hashing via information theory ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Emergence of geometry in a combinatorial universe ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Perfect Hashing and Probability ⋮ On measuring the complexity of networks: Kolmogorov complexity versus entropy ⋮ Entropy of symmetric graphs ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Generalized hashing and parent-identifying codes. ⋮ Sorting under partial information (without the ellipsoid algorithm). ⋮ Applications of coding theory to communication combinatorial problems ⋮ New bounds for perfect \(k\)-hashing ⋮ Data mining of social networks represented as graphs ⋮ Orientations making \(k\)-cycles cyclic ⋮ Improved bounds for covering complete uniform hypergraphs ⋮ Symmetric graphs with respect to graph entropy ⋮ Perfect couples of graphs ⋮ Recursive bounds for perfect hashing ⋮ A better bound for locally thin set families ⋮ Bounds for \(c\)-ideal hashing ⋮ Unnamed Item ⋮ On the capacity of Boolean graph formulæ ⋮ Optimal linear perfect hash families ⋮ Beating Fredman-Komlós for Perfect k-Hashing. ⋮ Probabilistic refinement of the asymptotic spectrum of graphs ⋮ Beating Fredman-Komlós for perfect \(k\)-hashing ⋮ The hat guessing number of graphs ⋮ Min-wise independent permutations ⋮ Entropy splitting for antiblocking corners and perfect graphs ⋮ On two continuum armed bandit problems in high dimensions

Cites Work

• On the Size of Separating Systems and Families of Perfect Hash Functions
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Two-step encoding for finite sources
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fredman–Komlós bounds and information theory