Pith. sign in

REVIEW 7 minor 102 references

Entropy methods in combinatorics

T0 review · 0 major / 7 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Entropy turns counting problems into inequality problems, and combinatorics has learned how to exploit that at scale.

desk verdict Clean, usable survey of entropy techniques in extremal/probabilistic combinatorics; no new theorems, but the organization and worked proofs make it worth having. read the letter →

arxiv 2607.24414 v1 pith:57Q2IY6X submitted 2026-07-27 math.CO

Wojciech Samotij This is my paper · ORCID
classification math.CO MSC 05C3505C6505D0594A17
keywords entropyShearer'sinequalitychainrulegraphhomomorphismsSidorenkoconjectureunion-closedsetsTurándensityPinsker
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This survey argues that Shannon entropy has become a standard, high-leverage tool in extremal and probabilistic combinatorics. The reason is simple: the entropy of a uniform random element of a finite set is the log of its size, so counting reduces to estimating entropy, and entropy obeys inequalities (chain rule, subadditivity, Shearer, Pinsker, relative entropy) that have no direct counting analogues. The paper organises the recent explosion of applications around a few reusable ideas: the randomised chain rule for permanents, matchings and designs; Shearer’s inequality for shadows, homomorphisms and isoperimetry; deliberately constructed high-entropy random homomorphisms for Sidorenko-type lower bounds; Pinsker-type control of near-independence for stability theorems; Gilmer’s entropy argument for the union-closed sets conjecture; and an entropy characterisation of Turán densities. A sympathetic reader cares because these templates repeatedly turn hard enumeration or extremal questions into short, transferable calculations.

What carries the argument

The chain rule for entropy (with optional random order of conditioning) together with subadditivity, Shearer’s inequality, non-negativity of relative entropy, and Pinsker’s inequality. These let one bound log|X| by averaging conditional entropies that are easier to estimate than the original counting problem.

What would settle it

Exhibit a major recent combinatorial breakthrough that is widely regarded as entropy-driven yet cannot be placed inside any of the six organisational themes of the survey, or show that one of the highlighted ‘book’ proofs (Bregman–Minc via randomised chain rule, Kahn–Galvin–Tetali homomorphism bound, Gilmer’s union-closed argument) does not actually rely on the entropy identities claimed.

Watch

Extended reading notes

Core claim

Entropy methods supply a small toolkit of identities and inequalities that systematically convert combinatorial counting and extremal problems into entropy estimates; the survey shows that a handful of templates—the randomised chain rule, Shearer’s lemma, large-entropy homomorphisms, Pinsker stability, and entropy formulations of Turán density—already underwrite tens to hundreds of recent results and continue to generate new ones.

Load-bearing premise

The claim that these particular themes and proofs are the most influential ones rests on the author’s selective judgment rather than an exhaustive or objective ranking.

Editorial extensions

If this is right

  • Upper bounds on perfect matchings, Steiner systems and high-dimensional permutations continue to follow from a single randomised-chain-rule lemma.
  • Shearer-type projections remain the default route to homomorphism and independent-set counts in regular bipartite graphs and to isoperimetric inequalities on product graphs.
  • Sidorenko-type inequalities and commonality questions will keep being attacked by constructing non-uniform homomorphisms whose entropy is still large and factorisable.
  • Stability versions of classical theorems (Kruskal–Katona, Loomis–Whitney, subgraph tails) can be read off from small relative entropy via Pinsker.
  • Turán densities of hypergraph families admit an equivalent entropy-supremum description that has already produced new density bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same randomised-order and high-entropy-homomorphism templates are likely to migrate next into sparse random hypergraphs and into flag-algebra-free proofs of common-graph inequalities.
  • Once an extremal problem is rewritten as an entropy optimisation, computer-assisted calculus or convex programming can systematically improve the numerical constants that still appear by hand (as happened with the union-closed constant).
  • Relative-entropy stability arguments may give a uniform language for ‘almost tight’ cases across shadow theorems, homomorphism counts and lower-tail large deviations.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 7 minor

Summary. This is a survey article on the use of entropy methods in extremal and probabilistic combinatorics. After a compact introduction to entropy, conditional entropy, binary entropy, and relative entropy (with standard proofs), the author organises the field around six conceptual threads: the randomised chain rule (Radhakrishnan's proof of Brégman's theorem; Linial–Luria-type bounds on perfect matchings in linear hypergraphs), Shearer's inequality (Friedgut–Kahn/Kruskal–Katona, the Kahn/Galvin–Tetali homomorphism bound, edge-isoperimetry in Cartesian products of complete graphs), the Kopparty–Rossman method of constructing high-entropy random homomorphisms (with a proof of Sidorenko's conjecture for graphs with a dominating vertex), Pinsker's inequality and entropic stability (with an entropy proof of Keevash's stability version of Kruskal–Katona), Gilmer's breakthrough on the union-closed sets conjecture (sketched), and the recent Chao–Yu entropy characterisation of Turán densities (with an entropy proof of Turán's theorem). The paper is explicitly a selective overview; it contains no new theorems, so the central claim is expository: that the chosen proofs faithfully convey the key ideas.

Significance. Entropy methods are now central to extremal and probabilistic combinatorics, and a well-organised map of the terrain is genuinely useful, particularly one that includes complete proofs of representative results rather than only citations. Particular strengths: (i) several proofs are given in full detail and some are presented in cleaned-up or slightly generalised form relative to the literature (e.g., Theorem 2.3 under the linearity assumption to avoid a technical step in Luria's argument; Proposition 3.5 generalising the Boucheron–Lugosi–Massart argument to K_m^n); (ii) the selection is current, covering the Gilmer union-closed breakthrough and the very recent Chao–Yu entropy approach to Turán densities; (iii) the survey contains no new claims requiring verification beyond faithful reproduction, and the reproduced arguments I checked are correct, with only local presentational slips. The choice of 'most influential' threads is of course an authorial judgment, but the organisation by technique rather than by problem is well suited to the survey's didactic aim.

minor comments (7)
  1. [§2, proof of Theorem 2.3] §2, proof of Theorem 2.3: the displayed line P(v ≺ ∪_{w∈f} x_w | τ_v, x) = τ_v^{k²−1} is inconsistent with the next display, which uses τ_v^{k(k−1)}. The downstream bound is correct: the relevant estimate must be conditioned also on Z_v^{≺,x} (the event v ≼ x_v), under which the k−1 vertices of x_v\{v} carry no constraint, leaving k(k−1) free witness vertices. As written, the line conditions only on (τ_v, x) and should either include Z in the conditioning or state the k(k−1) exponent directly.
  2. [§5, proof of Theorem 5.3] §5, proof of Theorem 5.3: the inference from (q_U − kε)²/(2q_U) ≤ 2ε to 'q_U ≤ 3kε' does not follow as printed. Solving the quadratic gives q_U ≤ (k + 2 + 2√(k+1))ε, which exceeds 3kε for k = 2 (and marginally for small k generally). Since the theorem permits a k-dependent constant C_k, the statement is unaffected, but the constant in the proof should be corrected.
  3. [§3, after Theorem 3.4] §3, text following the statement of Theorem 3.4: 'there is a well-known bijection between independent sets of G and the set Hom(G, )' — the target graph is missing from the displayed expression (presumably the two-vertex graph with one edge and one loop).
  4. [§1.5 (Organisation)] Coverage (suggestion, not a defect): the survey is explicitly selective, but a brief mention of two further threads would help readers place the map: entropy-compression arguments (algorithmic Lovász local lemma, Moser–Tardos) and the Ruzsa–Tao/Madiman–Tetali sumset inequalities in additive combinatorics. One or two sentences with references would suffice.
  5. [§2, proof of Theorem 2.3] §2, proof of Theorem 2.3: the notation 'v ≼ W' for a set W is used before being defined; the display P(v ≼ W | τ_v) = τ_v^{|W\{v}|} effectively serves as the definition, which could be flagged explicitly. Also, in equation (8) the inner conditioning includes Z_v^{≺,x}, but the probability displays immediately after condition only on (τ_v, x); aligning the conditioning throughout would prevent the confusion underlying the k²−1 vs. k(k−1) slip noted above.
  6. [§7, proof of Turán's theorem] §7, Claim 7.3(ii): the identity H(T_i) = N·H(X_1) + (i−1)·log q uses H(X_2|X_1) − H(X_1) = log q, which in turn needs H(X_1) = H(X_2) (the uniform ordering of a random edge has symmetric marginals). This holds here, but since the proof is given only in sketch, one phrase justifying the bookkeeping would help the reader.
  7. [§1.3, Proposition 1.9] Typographical: Proposition 1.9's proof begins 'Fix integers k and n satisfying 0 ≤ k ≤ n' while the statement assumes k ≤ n/2 (used later for monotonicity of h); harmless but could be aligned. Footnote 1 (natural log convention) is important for the constants in Pinsker's inequality (Proposition 5.1) and might be cross-referenced there.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: selective survey of classical entropy identities and independently published combinatorial applications; no fitted parameters, no self-definitional claims, no load-bearing self-citation chain.

full rationale

The paper is an expository survey. Its central claim is that entropy methods have proliferated in combinatorics and that a handful of techniques (randomised chain rule, Shearer's inequality, large-entropy homomorphisms, Pinsker stability, Gilmer's union-closed argument, Chao–Yu Turán entropy) organise the literature; that claim is supported by citing original external sources (Shannon, Shearer/Chung–Graham–Frankl–Shearer, Radhakrishnan, Kahn, Galvin–Tetali, Kopparty–Rossman, Pinsker, Gilmer, Chao–Yu, etc.) and by reproducing standard proofs. Entropy definitions (H, conditional H, DKL, binary entropy) and the classical identities (chain rule, subadditivity, non-negativity of relative entropy, data-processing) are taken as given from information theory, not derived from the combinatorial conclusions. The few self-citations ([20], [32], [64], [65]) appear only as further illustrations of the same toolkit, not as uniqueness theorems or premises that force the survey's organisation. There are no fitted parameters, no 'predictions' that reduce to inputs by construction, and no renaming of empirical patterns as first-principles results. Minor presentational slips noted by the reader (exponent inconsistency in the Theorem 2.3 write-up; loose constant in Theorem 5.3) do not create circularity. Score 0 is the honest finding.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

As a survey, the paper rests on standard information-theoretic identities and on the correctness of the cited combinatorial theorems it re-proves or sketches. No free parameters or new physical/combinatorial entities are introduced.

assumptions (4)
  • standard math Shannon entropy H(X) = -∑ p log p and the chain rule, subadditivity, and non-negativity of relative entropy (Facts 1.2–1.11)
    Classical information theory; used throughout as the basic calculus.
  • standard math Shearer's inequality (Lemma 3.1) and its combinatorial corollary
    Attributed to Shearer (via Chung–Graham–Frankl–Shearer); proved in the text from the chain rule.
  • standard math Pinsker's inequality relating total variation to relative entropy (Proposition 5.1)
    Classical; used for stability versions.
  • domain assumption Correctness of the original combinatorial statements being surveyed (Bregman, Sidorenko-type results, Gilmer's theorem, Turán densities, etc.)
    Survey relies on the literature it cites; proofs are reproduced or sketched but ultimate authority is the cited sources.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Entropy methods in combinatorics." pith.science (2026). https://pith.science/paper/57Q2IY6X

@misc{pith2026260724414,
  author       = {Pith},
  title        = {Pith review of: Entropy methods in combinatorics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/57Q2IY6X}},
  note         = {Machine review of arXiv:2607.24414}
}
read the original abstract

Even though entropy methods have been used in combinatorics for at least five decades, only in recent years has their use really proliferated. There are now tens, if not hundreds, of combinatorial papers that crucially rely on the notion of entropy and exploit the various powerful identities and inequalities relating entropies. In this short survey article, we give a selective overview of these works and discuss several of them in more detail, outlining some of the key ideas.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

102 extracted references · 19 linked inside Pith

  1. [1]

    Aigner and G

    M. Aigner and G. M. Ziegler.Proofs from The Book. Springer, Berlin, sixth edition, 2018. See corrected reprint of the 1998 original [ MR1723092], Including illustrations by Karl H. Hofmann

    2018

  2. [2]

    N. Alon. On the number of subgraphs of prescribed type of graphs with a given number of edges.Israel J. Math., 38(1-2):116–130, 1981. ENTROPY METHODS IN COMBINATORICS 17

    1981

  3. [3]

    Alon and J

    N. Alon and J. H. Spencer.The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016

    2016

  4. [4]

    Alweiss, B

    R. Alweiss, B. Huang, and M. Sellke. Improved lower bound for Frankl’s union-closed sets conjecture.Electron. J. Combin., 31(3):Paper No. 3.35, 11, 2024

    2024

  5. [5]

    Balogh, B

    J. Balogh, B. Bollob´ as, and B. Narayanan. Counting independent sets in regular hypergraphs.J. Combin. Theory Ser. A, 180:Paper No. 105405, 5, 2021

    2021

  6. [6]

    Behague, G

    N. Behague, G. Crudele, J. A. Noel, and L. M. Simbaqueba. Sidorenko-type inequalities for pairs of trees. Random Structures Algorithms, 67(1):Paper No. e70026, 51, 2025

    2025

  7. [7]

    Behague, N

    N. Behague, N. Morrison, and J. A. Noel. Off-diagonal commonality of graphs via entropy.SIAM J. Discrete Math., 38(3):2335–2360, 2024

    2024

  8. [8]

    Blekherman and A

    G. Blekherman and A. Raymond. A new proof of the Erd˝ os-Simonovits conjecture on walks.Graphs Combin., 39(3):Paper No. 53, 8, 2023

    2023

Show all 102 references
  1. [9]

    R. B. Boppana. A Useful Inequality for the Binary Entropy Function. arXiv:2301.09664

    arXiv

  2. [10]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart.Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux

    2013

  3. [11]

    Boyadzhiyska, S

    S. Boyadzhiyska, S. Das, and T. Szab´ o. Enumerating extensions of mutually orthogonal Latin squares.Des. Codes Cryptogr., 88(10):2187–2206, 2020

    2020

  4. [12]

    L. M. Br` egman. Certain properties of nonnegative matrices and their permanents.Dokl. Akad. Nauk SSSR, 211:27–30, 1973

    1973

  5. [13]

    S. Cambie. Better bounds for the union-closed sets conjecture using the entropy approach. arXiv:2212.12500

    arXiv

  6. [14]

    Chao and H.-H

    T.-W. Chao and H.-H. H. Yu. A Purely Entropic Approach to the Rainbow Triangle Problem. arXiv:2407.14084

    arXiv

  7. [15]

    Chao and H.-H

    T.-W. Chao and H.-H. H. Yu. Kruskal-Katona-type problems via the entropy method.J. Combin. Theory Ser. B, 169:480–506, 2024

    2024

  8. [16]

    Chao and H.-H

    T.-W. Chao and H.-H. H. Yu. When entropy meets Tur´ an: new proofs and hypergraph Tur´ an results.J. Lond. Math. Soc. (2), 113(3):Paper No. e70473, 40, 2026

    2026

  9. [17]

    Chase and S

    Z. Chase and S. Lovett. Approximate union closed conjecture. arXiv:2211.11689

    arXiv

  10. [18]

    Christoph, N

    M. Christoph, N. Dragani´ c, A. Gir˜ ao, E. Hurley, L. Michel, and A. M¨ uyesser. Cycle-factors of regular graphs via entropy. arXiv:2507.19417

    arXiv

  11. [19]

    F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. Some intersection theorems for ordered sets and graphs.J. Combin. Theory Ser. A, 43(1):23–37, 1986

    1986

  12. [20]

    Cohen Antonir, M

    A. Cohen Antonir, M. Harel, F. Mousset, and W. Samotij. Upper tails for irregular graphs beyond the mean- field regime. arXiv:2606.14564

  13. [21]

    Coja-Oghlan and M

    A. Coja-Oghlan and M. Hahn-Klimroth. The cut metric for probability distributions.SIAM J. Discrete Math., 35(2):1096–1135, 2021

    2021

  14. [22]

    Coja-Oghlan, F

    A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborov´ a. Information-theoretic thresholds from the cavity method.Adv. Math., 333:694–795, 2018

    2018

  15. [23]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. An approximate version of Sidorenko’s conjecture.Geom. Funct. Anal., 20(6):1354–1366, 2010

    2010

  16. [24]

    Conlon, J

    D. Conlon, J. H. Kim, C. Lee, and J. Lee. Some advances on Sidorenko’s conjecture.J. Lond. Math. Soc. (2), 98(3):593–608, 2018

    2018

  17. [25]

    Conlon and J

    D. Conlon and J. Lee. Finite reflection groups and graph norms.Adv. Math., 315:130–165, 2017

    2017

  18. [26]

    Csisz´ ar

    I. Csisz´ ar. A note on Jensen’s inequality.Studia Sci. Math. Hungar., 1:185–188, 1966

    1966

  19. [27]

    Csisz´ ar and J

    I. Csisz´ ar and J. K¨ orner.Information theory. Cambridge University Press, Cambridge, second edition, 2011. Coding theorems for discrete memoryless systems

    2011

  20. [28]

    Cuckler and J

    B. Cuckler and J. Kahn. Entropy bounds for perfect matchings and Hamiltonian cycles.Combinatorica, 29(3):327–335, 2009

    2009

  21. [29]

    Cuckler and J

    B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs.Combinatorica, 29(3):299–326, 2009

    2009

  22. [30]

    Cutler and A

    J. Cutler and A. J. Radcliffe. An entropy proof of the Kahn-Lov´ asz theorem.Electron. J. Combin., 18(1):Paper 10, 9, 2011

    2011

  23. [31]

    T. Dai, A. Divoux, and T. Kelly. Entropy bounds for perfect matchings in bipartite hypergraphs.Electron. J. Combin., 33(2):Paper No. 2.20, 13, 2026

    2026

  24. [32]

    Diskin and W

    S. Diskin and W. Samotij. Isoperimetry in Product Graphs.Electron. J. Combin., 32(3):P3.12, 2025

    2025

  25. [33]

    Ellis, E

    D. Ellis, E. Friedgut, G. Kindler, and A. Yehudayoff. Geometric stability via information theory.Discrete Anal., pages Paper No. 10, 29, 2016

    2016

  26. [34]

    Engbers and D

    J. Engbers and D. Galvin.H-coloring tori.J. Combin. Theory Ser. B, 102(5):1110–1133, 2012

    2012

  27. [35]

    Engbers and D

    J. Engbers and D. Galvin.H-colouring bipartite graphs.J. Combin. Theory Ser. B, 102(3):726–742, 2012

    2012

  28. [36]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits. Cube-supersaturated graphs and related problems. InProgress in graph theory (Waterloo, Ont., 1982), pages 203–218. Academic Press, Toronto, ON, 1984

    1982

  29. [37]

    Fox and B

    J. Fox and B. Sudakov. Dependent random choice.Random Structures Algorithms, 38(1-2):68–99, 2011

    2011

  30. [38]

    Friedgut

    E. Friedgut. Hypergraphs, entropy, and inequalities.Amer. Math. Monthly, 111(9):749–760, 2004

    2004

  31. [39]

    Friedgut and J

    E. Friedgut and J. Kahn. On the number of copies of one hypergraph in another.Israel J. Math., 105:251–256, 1998. ENTROPY METHODS IN COMBINATORICS 18

    1998

  32. [40]

    D. Galvin. Three tutorial lectures on entropy and counting. arXiv:1406.7872

    arXiv

  33. [41]

    D. Galvin. On homomorphisms from the Hamming cube toZ.Israel J. Math., 138:189–213, 2003

    2003

  34. [42]

    Galvin and P

    D. Galvin and P. Tetali. On weighted graph homomorphisms. InGraphs, morphisms and statistical physics, volume 63 ofDIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 97–104. Amer. Math. Soc., Provi- dence, RI, 2004

    2004

  35. [43]

    J. Gilmer. A constant lower bound for the union-closed sets conjecture. arXiv:2211.09055

    arXiv

  36. [44]

    Grzesik, J

    A. Grzesik, J. Lee, B. Lidick´ y, and J. Volec. On tripartite common graphs.Combin. Probab. Comput., 31(5):907–923, 2022

    2022

  37. [45]

    T. S. Han. Nonnegative entropy measures of multivariate symmetric correlations.Information and Control, 36(2):133–156, 1978

    1978

  38. [46]

    Harel, F

    M. Harel, F. Mousset, and W. Samotij. Upper tails via high moments and entropic stability.Duke Math. J., 171(10):2089–2192, 2022

  39. [47]

    I ˇlkoviˇ c and J

    D. I ˇlkoviˇ c and J. Yan. An improved hypergraph Mantel’s Theorem. arXiv:2503.14474

    arXiv

  40. [48]

    V. Jain, F. Koehler, and A. Risteski. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. InSTOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1226–1236. ACM, New York, 2019

    2019

  41. [49]

    Janson, K

    S. Janson, K. Oleszkiewicz, and A. Ruci´ nski. Upper tails for subgraph counts in random graphs.Israel J. Math., 142:61–92, 2004

    2004

  42. [50]

    Jenssen and P

    M. Jenssen and P. Keevash. Homomorphisms from the torus.Adv. Math., 430:Paper No. 109212, 89, 2023

    2023

  43. [51]

    J. Kahn. An entropy approach to the hard-core model on bipartite graphs.Combin. Probab. Comput., 10(3):219–237, 2001

    2001

  44. [52]

    J. Kahn. Range of cube-indexed random walk.Israel J. Math., 124:189–201, 2001

    2001

  45. [53]

    J. Kahn. Entropy, independent sets and antichains: a new approach to Dedekind’s problem.Proc. Amer. Math. Soc., 130(2):371–378, 2002

    2002

  46. [54]

    J. Kahn. Asymptotics for Shamir’s problem.Adv. Math., 422:Paper No. 109019, 39, 2023

    2023

  47. [55]

    Kahn and A

    J. Kahn and A. Lawrenz. Generalized rank functions and an entropy argument.J. Combin. Theory Ser. A, 87(2):398–403, 1999

    1999

  48. [56]

    Kahn and J

    J. Kahn and J. Park. The number of 4-colorings of the Hamming cube.Israel J. Math., 236(2):629–649, 2020

    2020

  49. [57]

    Kamˇ cev, A

    N. Kamˇ cev, A. Liebenau, and N. Morrison. Towards a characterization of Sidorenko systems.Q. J. Math., 74(3):957–974, 2023

    2023

  50. [58]

    P. Keevash. The existence of designs. arXiv:1401.3665

    arXiv

  51. [59]

    P. Keevash. Shadows and intersections: stability and new proofs.Adv. Math., 218(5):1685–1703, 2008

    2008

  52. [60]

    P. Keevash. Counting designs.J. Eur. Math. Soc. (JEMS), 20(4):903–927, 2018

    2018

  53. [61]

    J. H. B. Kemperman. On the optimum rate of transmitting information.Ann. Math. Statist., 40:2156–2177, 1969

    1969

  54. [62]

    J. H. Kim, C. Lee, and J. Lee. Two approaches to Sidorenko’s conjecture.Trans. Amer. Math. Soc., 368(7):5057–5074, 2016

    2016

  55. [63]

    Kopparty and B

    S. Kopparty and B. Rossman. The homomorphism domination exponent.European J. Combin., 32(7):1097– 1114, 2011

    2011

  56. [64]

    Kozma, T

    G. Kozma, T. Meyerovitch, R. Peled, and W. Samotij. What does a typical metric space look like?Ann. Inst. Henri Poincar´ e Probab. Stat., 60(1):11–53, 2024

    2024

  57. [65]

    Kozma and W

    G. Kozma and W. Samotij. Lower tails via relative entropy.Ann. Probab., 51(2):665–698, 2023

    2023

  58. [66]

    Kr´ a˘l, J

    D. Kr´ a˘l, J. Volec, and F. Wei. Common graphs with arbitrary chromatic number.Compos. Math., 161(3):594– 634, 2025

    2025

  59. [67]

    R. A. Krueger, L. Li, and J. Park. Lipschitz functions on weak expanders. arXiv:2408.14702

    arXiv

  60. [68]

    Kullback

    S. Kullback. A lower bound for discrimination information in terms of variation.IEEE Transactions on Information Theory, 13:126–127, 1967

    1967

  61. [69]

    Kullback and R

    S. Kullback and R. A. Leibler. On information and sufficiency.Ann. Math. Statistics, 22:79–86, 1951

    1951

  62. [70]

    M. Kwan. Almost all Steiner triple systems have perfect matchings.Proc. Lond. Math. Soc. (3), 121(6):1468– 1495, 2020

    2020

  63. [71]

    M. Kwan, R. Safavi, and Y. Wang. Counting perfect matchings in Dirac hypergraphs.Combinatorica, 46(1):Pa- per No. 5, 32, 2026

    2026

  64. [72]

    J. Lee. On some graph densities in locally dense graphs.Random Structures Algorithms, 58(2):322–344, 2021

    2021

  65. [73]

    J. L. X. Li and B. Szegedy. On the logarithmic calculus and Sidorenko’s conjecture. arXiv:1107.1153

    arXiv

  66. [74]

    L. Li, G. McKinley, and J. Park. The number of colorings of the middle layers of the Hamming cube.Combi- natorica, 45(1):Paper No. 7, 47, 2025

    2025

  67. [75]

    Linial and Z

    N. Linial and Z. Luria. An upper bound on the number of Steiner triple systems.Random Structures Algo- rithms, 43(4):399–406, 2013

    2013

  68. [76]

    Linial and Z

    N. Linial and Z. Luria. An upper bound on the number of high-dimensional permutations.Combinatorica, 34(4):471–486, 2014

    2014

  69. [77]

    X. Liu. On a hypergraph Mantel theorem. arXiv:2501.19229

    arXiv

  70. [78]

    X. Liu. Spectral generalized Tur´ an problems. arXiv:2507.21689. ENTROPY METHODS IN COMBINATORICS 19

    arXiv

  71. [79]

    L. H. Loomis and H. Whitney. An inequality related to the isoperimetric inequality.Bull. Amer. Math. Soc., 55:961–962, 1949

    1949

  72. [80]

    Z. Luria. New bounds on the number of n-queens configurations. arXiv:1705.05225

    arXiv

  73. [81]

    Ma and T

    J. Ma and T. Zhu. A note on hypergraph extensions of Mantel’s theorem. arXiv:2505.11373

    arXiv

  74. [82]

    Manurangsi and P

    P. Manurangsi and P. Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. In44th International Colloquium on Automata, Languages, and Programming, volume 80 ofLIPIcs. Leibniz Int. Proc. Inform., pages 78:1–78:15. Schloss Dagstuhl. Leibniz-Zent...

    2017

  75. [83]

    H. Minc. Upper bounds for permanents of (0,1)-matrices.Bull. Amer. Math. Soc., 69:789–791, 1963

    1963

  76. [84]

    Montanari

    A. Montanari. Estimating random variables from random sparse observations.European Transactions on Telecommunications, 19(4):385–403, 2008

    2008

  77. [85]

    Palmer and D

    C. Palmer and D. P´ alv¨ olgyi. At most 3.55n stable matchings. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, pages 217–227. IEEE Computer Soc., Los Alamitos, CA, 2022

    2021

  78. [86]

    L. Pebody. Extension of a Method of Gilmer. arXiv:2211.13139

    arXiv

  79. [87]

    Peled and Y

    R. Peled and Y. Spinka. Long-range order in discrete spin systems. arXiv:2010.03177

    2010 arXiv

  80. [88]

    Peled and Y

    R. Peled and Y. Spinka. Rigidity of proper colorings ofZ d.Invent. Math., 232(1):79–162, 2023

    2023

  81. [89]

    M. S. Pinsker.Information and information stability of random variables and processes. Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1964. Translated and edited by Amiel Feinstein

    1964

  82. [90]

    Radhakrishnan

    J. Radhakrishnan. An entropy proof of Bregman’s theorem.J. Combin. Theory Ser. A, 77(1):161–164, 1997

    1997

  83. [91]

    Raghavendra and N

    P. Raghavendra and N. Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. InProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 373–387. ACM, New York, 2012

    2012

  84. [92]

    A. R´ enyi. On the foundations of information theory.Rev. Inst. Internat. Statist., 33:1–14, 1965

    1965

  85. [93]

    Sa˘ glam

    M. Sa˘ glam. Near log-convexity of measured heat in (discrete) time and consequences. In59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, pages 967–978. IEEE Computer Soc., Los Alamitos, CA, 2018

    2018

  86. [94]

    W. Sawin. An improved lower bound for the union-closed set conjecture. arXiv:2211.11504

    arXiv

  87. [95]

    Schrijver

    A. Schrijver. A short proof of Minc’s conjecture.J. Combinatorial Theory Ser. A, 25(1):80–83, 1978

    1978

  88. [96]

    C. E. Shannon. A mathematical theory of communication.Bell System Tech. J., 27:379–423, 623–656, 1948

    1948

  89. [97]

    Sidorenko

    A. Sidorenko. A correlation inequality for bipartite graphs.Graphs Combin., 9(2):201–204, 1993

    1993

  90. [98]

    A. F. Sidorenko. Inequalities for functionals generated by bipartite graphs.Diskret. Mat., 3(3):50–65, 1991

    1991

  91. [99]

    M. Simkin. The number ofn-queens configurations.Adv. Math., 427:Paper No. 109127, 83, 2023

    2023

  92. [100]

    B. Szegedy. An information theoretic approach to Sidorenko’s conjecture. arXiv:1406.6738

    arXiv

  93. [101]

    van der Hofstad, R

    R. van der Hofstad, R. Pendavingh, and J. van der Pol. The number of partial Steiner systems andd-partitions. Adv. Comb., pages Paper No. 2, 23, 2022

    2022

  94. [102]

    L. Yu. Dimension-free bounds for the union-closed sets conjecture.Entropy, 25(5):Paper No. 767, 10, 2023. School of Mathematical Sciences, Tel A viv University, Tel A viv, Israel Email address:samotij@tauex.tau.ac.il

    2023

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.