Fredman–Komlós bounds and information theory
From MaRDI portal
Publication:3739153
DOI10.1137/0607062zbMath0603.05034OpenAlexW2029773437MaRDI QIDQ3739153
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
graph entropygraph coveringperfect hashingentropies of graphsFredman-Komlós lemmaseparating partition systems
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
\(\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, 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
