Pith. sign in

REVIEW 43 references

On problems in extremal multigraph theory

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves asymptotic and exact extremal densities for (s,q)-multigraphs in the large- and small-multiplicity regimes.

arxiv 2505.14281 v2 pith:STHQJ63B submitted 2025-05-20 math.CO

Victor Falgas-Ravry , Adva Mond , Rik Sarkar , Victor Souza This is my paper
classification math.CO
keywords problemsmultigraphcountingextremalfalgas-ravrygeneralgraphmultiplicities
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

A multigraph is like a graph where two people can share many handshakes at once. An (s,q)-graph insists that among any s people, the total number of handshakes is at most q. Two old problems ask for the largest total number of handshakes (sum problem) and the largest product of handshake counts (product problem) on n people. This paper studies the asymptotic densities of both quantities.

The authors split the problem by the ambient multiplicity a. When a is large, they prove that the optimal construction is always a blow-up of a generalised Turán pattern, a structured template with a few parts and prescribed edge multiplicities. This gives the geometric density exactly in the base cases, and a step-up lemma extends it to larger detection parameters, settling a conjecture of Day, Falgas-Ravry and Treglown asymptotically. They also prove the flat-intervals conjecture of Falgas-Ravry, showing that the product density stays constant across an interval of q-values.

When a=1 (sum problem) and a=2 (product problem), the extremal constructions are no longer generalised Turán patterns. The paper shows that for certain q-ranges, the product is maximised by blow-ups of a Petersen-like graph, while the sum problem exhibits strong instability, with many far-apart near-extremal examples. These results give the first non-trivial small-a picture and connect to counting theorems for sparse multigraphs.

Extended reading notes

Core claim

The central load-bearing assertion is Theorem 4.8: under condition (4.5) on the ambient multiplicity a, exΠ(s0, Σs0(T)) = e^{πT} and every near-extremal (s0, Σs0(T))-graph is o(n^2)-close to a product-optimal blow-up of T. This yields asymptotic Conjecture 1.9 (Corollary 1.13) and the flat-interval Conjecture 1.11 (Theorem 1.18).

Load-bearing premise

The step-up Proposition 4.7, which extends the base-case equality exΠ(s,Σ_s(T)) = e^{πT} to all larger s, is asserted with the proof 'essentially identical' to [35, Theorem 3.11] and is not proved in the paper (Section 4.2). All results for s > s0 (Corollary 1.13, Theorems 1.15, 1.17) rest on it. If the step-up lemma carries hidden hypotheses beyond 'a sufficiently large', those theorems are not established. This is structurally different from the central claim: it concerns the propagation of the density equality, not the base-case density itself.

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.

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

The paper introduces no new free parameters fitted to data. The constants x⋆ and π_T are explicitly defined via optimisation, not calibrated. Background uses standard extremal combinatorics tools and one conditional number-theoretic conjecture in remarks only.

assumptions (5)
  • standard math Erdős-Stone theorem gives asymptotic ex(n,s,q) for q ≥ floor(s^2/4).
    Used in Propositions 1.21 and 1.24 to handle edges of multiplicity far from the ambient value.
  • standard math Katona-Nemetz-Simonovits averaging yields monotone limits for exΣ and exΠ.
    Lemma 2.2 and the arithmetic averaging inequality (2.3).
  • standard math Colourful Regularity Lemma and Blow-up Lemma reduce arbitrary multigraphs to pattern blow-ups.
    Corollary 2.17, which is the main reduction tool in the small-a proofs.
  • standard math Integer AM-GM inequality bounds products given sums.
    Proposition 2.3, used throughout small-a and large-a proofs.
  • domain assumption Schanuel's conjecture (conditional) for transcendence remarks.
    Used only in remarks on transcendence of π_T and x⋆, not load-bearing for the main theorems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On problems in extremal multigraph theory." pith.science (2026). https://pith.science/paper/STHQJ63B

@misc{pith2026250514281,
  author       = {Pith},
  title        = {Pith review of: On problems in extremal multigraph theory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/STHQJ63B}},
  note         = {Machine review of arXiv:2505.14281}
}
read the original abstract

A multigraph G is said to be an (s,q)-graph if every s-set of vertices in G supports at most q edges (counting multiplicities). In this paper we consider the maximal sum and product of edge multiplicities in an (s,q)-graph on n vertices. These are multigraph analogues of a problem of Erd\H{o}s raised by F\"uredi and K\"undgen and Mubayi and Terry respectively, with applications to counting problems and extremal hypergraph theory. We make major progress, settling conjectures of Day, Falgas-Ravry and Treglown and of Falgas-Ravry, establishing intricate behaviour for both the sum and the product problems, and providing both a general picture and evidence that the problems may prove computationally intractable in general.

Figures

Figures reproduced from arXiv: 2505.14281 by the authors.

Figure 1
Figure 1. Some examples of generalised Turán patterns. The colours of vertices and edges indicates their multiplicity. Remark 1.7. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The family of graphs C5. {12, 13, 14, 25, 26} (the ‘H-graph’), H7 the graph obtained by glueing two copies of C5 along a path on three vertices (i.e. the graph on [7] with edges {12, 23, 34, 45, 15, 16, 67, 74}), and H9 the graph obtained from the hexagon by joining opposite vertices by a copy of P2 (i.e. the graph on [9] with edges {12, 23, 34, 45, 56, 16, 17, 74, 28, 85, 39, 96}). Finally, we let C5 denote the fam… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [1]

    Extremal problems in graph theory

    Paul Erdős. Extremal problems in graph theory. InA Seminar on Graph Theory, pages 54–59. Holt, Rinehart, and Winston, New York, 1967

    work page 1967

  2. [2]

    Extremal problems in graph theory

    Paul Erdős. Extremal problems in graph theory. InTheory of Graphs and Its Applications, pages 29–36. Publ. House. Czechoslovak Acad. Sci., Prague, 1964. Proc. Sympos. Smolenice, 1963

    work page 1964

  3. [3]

    On an extremal problem in graph theory

    Paul Turán. On an extremal problem in graph theory. Matematikai és Fizikai Lapok, 48:436–452, 1941

    work page 1941

  4. [4]

    Extensions of Turán’s theorem on graphs.Acta Mathematica Hungarica, 14(3-4):417–422, 1963

    Gabriel Dirac. Extensions of Turán’s theorem on graphs.Acta Mathematica Hungarica, 14(3-4):417–422, 1963

    work page 1963

  5. [5]

    On the structure of linear graphs.Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946

    Paul Erdős and Arthur Harold Stone. On the structure of linear graphs.Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946. 36

    work page 1946

  6. [6]

    On the maximal number of edges for a graph with n vertices in which a given subgraph with k vertices has no more than l edges

    AI Gol’berg and Vladimir Alexander Gurvich. On the maximal number of edges for a graph with n vertices in which a given subgraph with k vertices has no more than l edges. In Doklady Akademii Nauk, volume 293, pages 27–32. Russian Academy of Sciences, 1987

    work page 1987

  7. [7]

    Griggs, Miklós Simonovits, and George Rubin Thomas

    Jerrold R. Griggs, Miklós Simonovits, and George Rubin Thomas. Extremal graphs with bounded densities of small subgraphs.Journal of Graph Theory, 29(3):185–207, 1998

    work page 1998

  8. [8]

    A weighted generalization of Turán’s theorem.Journal of Graph Theory, 25(4):267–275, 1997

    John Adrian Bondy and Zsolt Tuza. A weighted generalization of Turán’s theorem.Journal of Graph Theory, 25(4):267–275, 1997

    work page 1997

Show all 43 references
  1. [9]

    Extremal Problems On Integer-Weighted Graphs

    John Allen Kuchenbrod. Extremal Problems On Integer-Weighted Graphs. PhD thesis, University of Kentucky, 1999

    1999

  2. [10]

    Turán problems for integer-weighted graphs.Journal of Graph Theory, 40(4):195–225, 2002

    Zoltán Füredi and André Kündgen. Turán problems for integer-weighted graphs.Journal of Graph Theory, 40(4):195–225, 2002

    2002

  3. [11]

    An Extremal Graph Problem with a Transcendental Solution

    Dhruv Mubayi and Caroline Terry. An Extremal Graph Problem with a Transcendental Solution. Combinatorics, Probability and Computing, 28(2):303–324, 2019

    2019

  4. [12]

    Asymptotic enumeration of Kn-free graphs

    Paul Erdős, Daniel J Kleitman, and Bruce Lee Rothschild. Asymptotic enumeration of Kn-free graphs. InTomo II, Atti dei Convegni Lincei, No. 17, pages 19–27, 1976

    1976

  5. [13]

    On the entropy values of hereditary classes of graphs

    Vladimir E Alekseev. On the entropy values of hereditary classes of graphs. Discrete Mathematics and Applications, 3:191–199, 1993

    1993

  6. [14]

    Hereditary and monotone properties of graphs

    Béla Bollobás and Andrew Thomason. Hereditary and monotone properties of graphs. In The Mathematics of Paul Erdős II, pages 70–78. Springer, 1997

    1997

  7. [15]

    Independent sets in hypergraphs

    József Balogh, Robert Morris, and Wojciech Samotij. Independent sets in hypergraphs. Journal of the American Mathematical Society, 28(3):669–709, 2015

    2015

  8. [16]

    Hypergraph containers.Inventiones Mathematicae, 201(3):925–992, 2015

    David Saxton and Andrew Thomason. Hypergraph containers.Inventiones Mathematicae, 201(3):925–992, 2015

    2015

  9. [17]

    Some new applications of probability methods to combinatorial analysis and graph theory

    Paul Erdős. Some new applications of probability methods to combinatorial analysis and graph theory. InProceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 39–51. Boca Raton, 1974

    1974

  10. [18]

    Multicolor containers, extremal entropy, and counting.Random Structures & Algorithms, 54(4):676–720, 2019

    Victor Falgas-Ravry, Kelly O’Connell, and Andrew Uzzell. Multicolor containers, extremal entropy, and counting.Random Structures & Algorithms, 54(4):676–720, 2019

    2019

  11. [19]

    A rainbow Erdős–Rothschild problem

    Carlos Hoppen, Hanno Lefmann, and Knut Odermann. A rainbow Erdős–Rothschild problem. SIAM Journal on Discrete Mathematics, 31(4):2647–2674, 2017

    2017

  12. [20]

    The number of gallai k-colorings of complete graphs.Journal of Combinatorial Theory, Series B, 144:1–13, 2020

    Josefran de Oliveira Bastos, Fabricio Siqueira Benevides, and Jie Han. The number of gallai k-colorings of complete graphs.Journal of Combinatorial Theory, Series B, 144:1–13, 2020

    2020

  13. [21]

    Exact solutions to the erdős-rothschild problem

    Oleg Pikhurko and Katherine Staden. Exact solutions to the erdős-rothschild problem. Forum of Mathematics, Sigma, 12:e8, 2024

    2024

  14. [22]

    A method for solving extremal problems in graph theory, stability problems

    Miklós Simonovits. A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 279–319, 1968

    1966

  15. [23]

    A hypergraph turán problem with no stability.Combinatorica, 42(3):433–462, 2022

    Xizhi Liu and Dhruv Mubayi. A hypergraph turán problem with no stability.Combinatorica, 42(3):433–462, 2022

    2022

  16. [24]

    On the jumping constant conjecture for multigraphs

    Vojtěch Rödl and Alexander Sidorenko. On the jumping constant conjecture for multigraphs. Journal of Combinatorial Theory, Series A, 69(2):347–357, 1995

    1995

  17. [25]

    Hypergraphs do not jump.Combinatorica, 4(2):149–159, 1984

    Peter Frankl and Vojtěch Rödl. Hypergraphs do not jump.Combinatorica, 4(2):149–159, 1984

    1984

  18. [26]

    The maximum size of 3-uniform hypergraphs not containing a fano plane.Journal of Combinatorial Theory, Series B, 78(2):274–276, 2000

    Dominique De Caen and Zoltán Füredi. The maximum size of 3-uniform hypergraphs not containing a fano plane.Journal of Combinatorial Theory, Series B, 78(2):274–276, 2000

    2000

  19. [27]

    Brown, Paul Erdős, and Vera T

    William G. Brown, Paul Erdős, and Vera T. Sós. Some extremal problems on r-graphs. In New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971), pages 53–63. Academic Press New York, 1973

    1971

  20. [28]

    Ruzsa and Endre Szemerédi

    Imre Z. Ruzsa and Endre Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(2):939–945, 1978

    1976

  21. [29]

    The limit in the(k + 2, k)-problem of Brown, Erdős and Sós exists for allk ≥ 2

    Michelle Delcourt and Luke Postle. The limit in the(k + 2, k)-problem of Brown, Erdős and Sós exists for allk ≥ 2. Proceedings of the American Mathematical Society, 152(05):1881–1891, 2024. 37

    2024

  22. [30]

    On the (6, 4)-problem of Brown, Erdős, and Sós.Proceedings of the American Mathematical Society, Series B, 11(17):173–186, 2024

    Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev, and Oleg Pikhurko. On the (6, 4)-problem of Brown, Erdős, and Sós.Proceedings of the American Mathematical Society, Series B, 11(17):173–186, 2024

    2024

  23. [31]

    The Brown–Erdős conjecture for hypergraphs of large uniformity

    Peter Keevash and Jason Long. The Brown–Erdős conjecture for hypergraphs of large uniformity. arXiv preprint arXiv:2007.14824, 2020

    2007 arXiv

  24. [32]

    A new approach for the brown–erdős–sós problem

    Asaf Shapira and Mykhaylo Tyomkyn. A new approach for the brown–erdős–sós problem. Israel Journal of Mathematics, pages 1–12, 2025

    2025

  25. [33]

    Katona, T

    Gyula O.H. Katona, T. Nemetz, and Miklós Simonovits. On a graph-problem of Turán in the theory of graphs.Matematikai Lapok, 15:228–238, 1964. (in Hungarian)

    1964

  26. [34]

    Extremal Theory of Locally Sparse Multigraphs.SIAM Journal on Discrete Mathematics, 34(3):1922–1943, 2020

    Dhruv Mubayi and Caroline Terry. Extremal Theory of Locally Sparse Multigraphs.SIAM Journal on Discrete Mathematics, 34(3):1922–1943, 2020

    1922

  27. [35]

    Nicholas Day, Victor Falgas-Ravry, and Andrew Treglown

    A. Nicholas Day, Victor Falgas-Ravry, and Andrew Treglown. Extremal problems for multigraphs. Journal of Combinatorial Theory, Series B, 154:1–48, 2022

    2022

  28. [36]

    On an extremal problem for locally sparse multigraphs.European Journal of Combinatorics, 118:103887, 2024

    Victor Falgas-Ravry. On an extremal problem for locally sparse multigraphs.European Journal of Combinatorics, 118:103887, 2024

    2024

  29. [37]

    On extremal problems on multigraphs.Graphs and Combi- natorics, 40(6):114, 2024

    Ran Gu and Shuaichao Wang. On extremal problems on multigraphs.Graphs and Combi- natorics, 40(6):114, 2024

    2024

  30. [38]

    Szemerédi’s Regularity Lemma and its applications in graph theory

    János Komlós and Miklós Simonovits. Szemerédi’s Regularity Lemma and its applications in graph theory. InPaul Erdős is eighty, volume II, pages 295–352. Janos Bolyai Mathematical Society, 1996

    1996

  31. [39]

    Blow-up lemma.Combinatorica, 17:109–123, 1997

    János Komlós, Gábor Sárközy, and Endre Szemerédi. Blow-up lemma.Combinatorica, 17:109–123, 1997

    1997

  32. [40]

    The blow-up lemma.Combinatorics, Probability and Computing, 8(1-2):161– 176, 1999

    János Komlós. The blow-up lemma.Combinatorics, Probability and Computing, 8(1-2):161– 176, 1999

    1999

  33. [41]

    Personal communication

    Victor Falgas-Ravry and Eero Räty. Personal communication

  34. [42]

    Extremal Problems for Multigraphs

    Rik Sarkar. Extremal Problems for Multigraphs. Master’s thesis, Indian Institute of Science Education and Research (IISER), Pune, 2025.http://dr.iiserpune.ac.in:8080/jspui/ bitstream/123456789/9859/1/20201122%20_Rik_Sarkar_MS_Thesis.pdf

    2025

  35. [43]

    Large subgraphs of minimal density or degree

    Paul Erdős, Ralph Faudree, Arun Jagota, and Tomasz Łuczak. Large subgraphs of minimal density or degree. Journal of combinatorial mathematics and combinatorial computing, 22:87–96, 1996. Appendix Proof of Proposition 3.7 parts (i)–(iv).Part (i): let x be a product-optimal weig...

    1996

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.