Pith. sign in

REVIEW 5 minor 50 references

Graphs of VC-dimension d contain a clique or independent set of size n to the power 1 over (C d)^d.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-13 00:42 UTC pith:I3L2IIPS

load-bearing objection Clean single-exponential EH bound for bounded VC-dimension by smarter induction on external dimension classes; solid and worth citing.

arxiv 2607.09049 v1 pith:I3L2IIPS submitted 2026-07-10 math.CO

A Single-Exponential ErdH{o}s--Hajnal Bound for Graphs of Bounded VC-Dimension

Shuang Sun , Yan Wang , Jiasheng Zeng This is my paper
classification math.CO MSC 05C3505C6905D1068Q32
keywords Erdős–Hajnal conjectureVC-dimensionhomogeneous setsiterative sparsificationpure blockadesexternal VC-dimensionpolynomial Rödl propertyhypergraph Ramsey
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper improves the quantitative form of the Erdős–Hajnal property for graphs of bounded VC-dimension. Earlier work already showed that every n-vertex graph of VC-dimension at most d has a clique or independent set of size at least n to a positive power that depends only on d, but the power was only double-exponentially small in d. The new bound replaces that double-exponential loss by a single-exponential one: the power is at least 1 over (C d)^d for an absolute constant C. The argument works by refining an iterative sparsification procedure. Instead of inducting on the size of a large forbidden bipartite pattern, it inducts directly on the external VC-dimension, using a dimension-drop lemma that forces the pattern graph of a pure blockade to live in a lower class whenever a vertex is mixed on many blocks. The same improved exponent immediately yields sharper polynomial Rödl statements, multicolour hypergraph Ramsey bounds under bounded VC-dimension, and explicit Erdős–Hajnal-type estimates for tournaments, semi-algebraic graphs, NIP structures, bounded-rank and bounded-sign-rank graphs, and Boolean combinations of low-complexity relations.

Core claim

There exists an absolute constant h such that every graph G of VC-dimension at most d satisfies max{\omega(G),\alpha(G)} \ge |G|^{(h d)^{-d}}. Equivalently the Erdős–Hajnal exponent η_d is at least (h d)^{-d}, improving the previous lower bound 2^{-2^{O(d)}}.

What carries the argument

Dimension-drop on pure blockades: if a vertex is mixed on every block of an ε-pure blockade whose pattern graph contains a bi-induced copy of the universal shattering bigraph U_r, then the original graph contains a bi-induced copy of U_{r+1}; consequently the pattern graph itself belongs to the class C_{r-1} of graphs of external VC-dimension at most r-1, allowing a clean inductive step that multiplies the reciprocal exponent by only a linear factor in r.

Load-bearing premise

The whole construction rests on a quantitative ultra-strong regularity lemma that partitions a VC-dimension-d graph into at most ε to the power -K d nearly pure pairs; if that polynomial length bound fails, the size of the extracted blockades collapses.

What would settle it

Either exhibit, for infinitely many d, an n-vertex graph of VC-dimension d whose largest clique or independent set has size smaller than n to the power (C d)^{-d} for every fixed C, or show that every such graph already contains a homogeneous set larger than n to a power better than 1/d, matching the random-graph upper bound of order 1/d given in the paper.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves a quantitative Erdős–Hajnal theorem for graphs of VC-dimension at most d: there is an absolute constant h such that every such n-vertex graph G satisfies max{ω(G), α(G)} ≥ |G|^{(h d)^{-d}} (Theorem 1.2). This improves the double-exponential lower bound η_d ≥ 2^{-2^{O(d)}} of Nguyen–Scott–Seymour to a single-exponential form. The argument works with the nested classes C_r of graphs free of a bi-induced copy of the universal shattering bigraph U_{r+1}, obtains pure blockades via the quantitative ultra-strong regularity lemma, proves a dimension-drop lemma for mixed vertices on the pattern graph, and runs an iterative sparsification that yields either a highly restricted induced subgraph or a complete/anticomplete blockade; a standard cograph conversion then produces the recurrence s_r ≤ C r s_{r-1} with s_0 = 1. Quantitative consequences are derived for polynomial Rödl subgraphs, multicolour hypergraph Ramsey numbers under bounded VC-dimension, tournaments, NIP/semi-algebraic graphs, Boolean combinations, bounded-rank and bounded-sign-rank graphs, and dot-product threshold graphs.

Significance. The result is a clean and substantial quantitative improvement on a theorem that settled a conjecture of Fox–Pach–Suk. By inducting directly on external VC-dimension rather than on the exponential size of U_{d+1} and by fixing the restrictedness power in the sparsification step, the authors replace a double-exponential dependence by a single-exponential one of the form (C d)^{-d}. The proof is fully explicit, self-contained once the published regularity lemma is granted, and immediately yields concrete exponents for a long list of geometric, algebraic and model-theoretic graph classes. The matching probabilistic upper bound of order 1/d (Remark 5.2) shows that the new lower bound is not tight, yet the single-exponential guarantee is already the best general bound available and will be useful for further quantitative work in induced Ramsey theory.

minor comments (5)
  1. In the statement of Lemma 2.4 the constant b is chosen as 34K; a short parenthetical remark that any sufficiently large multiple of K works would make the dependence on the regularity constant completely transparent.
  2. Lemma 2.10 (the fixed-power iteration) is used with p=4 throughout; it would help the reader if the authors briefly noted that any fixed p≥2 works and that the concrete choice only affects the absolute constant h.
  3. In the proof of Theorem 3.1 the authors enlarge s_{r-1} if necessary so that s_{r-1}≥ r. While correct, a one-line remark that this only weakens the inductive hypothesis would remove any momentary doubt.
  4. Section 4.3 lists many applications by citing the reductions of Nguyen–Scott–Seymour; adding a single sentence that the only change is the substitution of the new exponent (hd)^{-d} would make the section self-contained for readers who do not have [36] open.
  5. Typographical: in the abstract the displayed inequality uses |G| (Cd)^{-d} without the exponentiation symbol rendered as a superscript in some PDF viewers; a small LaTeX adjustment would improve readability.

Circularity Check

0 steps flagged

No significant circularity: the single-exponential EH bound is obtained by a self-contained inductive sparsification on external VC-dimension classes C_r, solving an explicit recurrence from regularity and dimension-drop lemmas.

full rationale

The derivation of Theorem 1.2 / Theorem 3.1 is a closed inductive argument. It begins from the definition of the nested classes C_r (graphs with no bi-induced U_{r+1}, i.e., external VC-dimension ≤ r) and the quantitative ultra-strong regularity lemma (Theorem 2.3, taken from Nguyen–Scott–Seymour with the polynomial dependence of Fox–Pach–Suk). Lemma 2.4 produces an ε-pure blockade; Lemma 2.6 shows that a vertex mixed on many blocks forces the pattern graph into C_{r-1}; Lemmas 2.7–2.11 convert this into a global alternative (large restricted induced subgraph or complete/anticomplete blockade of controlled width); Lemma 2.12 converts the alternative into a homogeneous set via cograph induction. The resulting recurrence is s_r ≤ C r s_{r-1} with s_0 = 1, which solves to s_r ≤ (h r)^r and yields the claimed exponent (h d)^{-d}. No parameter is fitted to data; no uniqueness theorem is imported from the authors; the only external inputs are standard regularity and Sauer–Shelah/Warren-type counting lemmas used for applications. The probabilistic obstruction of Remark 5.2 is an independent upper-bound construction and does not feed back into the lower-bound proof. The argument is therefore free of self-definitional, fitted-input, or self-citation circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 1 invented entities

The paper is pure mathematics. It relies on standard combinatorial lemmas (Sauer–Shelah, Turán, Ramsey numbers, cograph structure) and one previously published quantitative regularity lemma. No free parameters are fitted to data; absolute constants are existential. The only invented entities are the auxiliary classes C_r and the universal bigraphs U_r, which are definitional packaging of external VC-dimension.

axioms (3)
  • domain assumption Quantitative ultra-strong regularity lemma: every graph of VC-dimension ≤ d admits an equipartition of length ≤ ε^{-K d} in which all but an ε-fraction of pairs are weakly ε-pure (Theorem 2.3).
    Taken verbatim from Nguyen–Scott–Seymour; supplies the pure blockades that start every sparsification step.
  • standard math Sauer–Shelah lemma: a set system of VC-dimension ≤ d shatters at most O(|S|^d) subsets of any S.
    Used in applications (Boolean combinations, sign-rank) to convert algebraic or rank bounds into VC-dimension bounds.
  • standard math Every cograph on n vertices has a homogeneous set of size ≥ √n.
    Invoked in the final conversion Lemma 2.12 to turn restricted subgraphs or pure blockades into cliques or stable sets.
invented entities (1)
  • Classes C_r of graphs with no bi-induced copy of the universal bigraph U_{r+1} no independent evidence
    purpose: Allow induction on external VC-dimension rather than on the exponential size of U_{d+1}.
    Definitional packaging; equivalent to external VC-dimension ≤ r. No independent physical or empirical content.

pith-pipeline@v1.1.0-grok45 · 27105 in / 2355 out tokens · 28602 ms · 2026-07-13T00:42:13.065858+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of A Single-Exponential Erd\H{o}s--Hajnal Bound for Graphs of Bounded VC-Dimension." pith.science (2026). https://pith.science/paper/I3L2IIPS

@misc{pith2026260709049,
  author       = {Pith},
  title        = {Pith review of: A Single-Exponential Erd\Hos--Hajnal Bound for Graphs of Bounded VC-Dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I3L2IIPS}},
  note         = {Machine review of arXiv:2607.09049}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

A homogeneous set in a graph is a clique or a stable set. The Erd\H{o}s--Hajnal conjecture states that, for every graph $H$, there exists $c>0$ such that every $H$-free graph on $n$ vertices has a homogeneous set of size at least $n^c$. Nguyen, Scott and Seymour proved that for every $d>0$, graphs of VC-dimension at most $d$ have the Erd\H{o}s--Hajnal property, confirming a conjecture of Fox, Pach and Suk. In particular, they showed that every such $n$-vertex graph contains a homogeneous set of size at least $n^{\eta_d}$ for some $\eta_d\ge 2^{-2^{O(d)}}$. In this paper, we give a sharper quantitative bound on the homogeneous sets in graphs of VC-dimension at most $d$, showing that one may take $ \eta_d\ge (Cd)^{-d}, $ where $C$ is an absolute constant. Equivalently, every graph $G$ of VC-dimension at most $d$ satisfies \[ \max\{\omega(G),\alpha(G)\}\ge |G|^{(Cd)^{-d}}. \] Our proof refines the iterative sparsification method of Nguyen, Scott and Seymour. The main enhancement is to apply the VC-dimension assumption directly, which gives a more efficient induction and thus improves the dependence on $d$. We also derive quantitative consequences for polynomial R\"odl subgraphs, hypergraph Ramsey bounds under bounded VC-dimension, induced-free and viral formulations, tournaments, NIP and semi-algebraic graphs, Boolean combinations of relations of bounded VC-dimension, graphs whose adjacency matrices have bounded rank, graphs of bounded sign-rank, and graphs defined by dot-product threshold representations.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 29 canonical work pages · 1 internal anchor

  1. [1]

    N. Alon, J. Pach, and J. Solymosi. Ramsey-type theorems with forbidden subgraphs.Combinatorica, 21 (2):155–170, 2001. doi: 10.1007/s004930100016

    work page doi:10.1007/s004930100016 2001

  2. [2]

    N. Alon, J. Pach, R. Pinchasi, R. Radoičić, and M. Sharir. Crossing patterns of semi-algebraic sets. Journal of Combinatorial Theory, Series A, 111(2):310–326, 2005. doi: 10.1016/j.jcta.2004.12.008

    work page doi:10.1016/j.jcta.2004.12.008 2005

  3. [3]

    N. Alon, E. Fischer, and I. Newman. Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM Journal on Computing, 37(3):959–976, 2007. doi: 10.1137/050627915

    work page doi:10.1137/050627915 2007

  4. [4]

    N. Alon, J. Balogh, B. Bollobás, and R. Morris. The structure of almost all graphs in a hereditary property. Journal of Combinatorial Theory, Series B, 101(2):85–110, 2011. doi: 10.1016/j.jctb.2010.10.001

    work page doi:10.1016/j.jctb.2010.10.001 2011

  5. [5]

    N. Alon, S. Moran, and A. Yehudayoff. Sign rank and the Vapnik–Chervonenkis dimension.Sbornik: Mathematics, 208(12):1724–1757, 2017. doi: 10.4213/sm8780

    doi:10.4213/sm8780 2017

  6. [6]

    Bucić, J

    M. Bucić, J. Fox, and H. T. Pham. Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures.arXiv preprint, 2024

    2024

  7. [7]

    Bucić, T

    M. Bucić, T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. I. a loglog step towards Erdős–Hajnal.International Mathematics Research Notices, 2024(12):9991–10004, 2024. doi: 10.1093/ imrn/rnae096

    2024

  8. [8]

    T.-W. Chao, Z. Xu, C. H. Yip, and S. Zhang. Uniform set systems with small VC-dimension.International Mathematics Research Notices, 2025(17):rnaf269, 2025. doi: 10.1093/imrn/rnaf269

    work page doi:10.1093/imrn/rnaf269 2025

  9. [9]

    Chernikov and S

    A. Chernikov and S. Starchenko. Regularity lemma for distal structures.Journal of the European Mathematical Society, 20(10):2437–2466, 2018. doi: 10.4171/JEMS/816

    work page doi:10.4171/jems/816 2018

  10. [10]

    Chernikov and S

    A. Chernikov and S. Starchenko. Definable regularity lemmas for NIP hypergraphs.The Quarterly Journal of Mathematics, 72(4):1401–1433, 2021. doi: 10.1093/qmath/haab011

    work page doi:10.1093/qmath/haab011 2021

  11. [11]

    Chernikov, D

    A. Chernikov, D. Galvin, and S. Starchenko. Cutting lemma and Zarankiewicz’s problem in distal structures.Selecta Mathematica, 26:25, 2020. doi: 10.1007/s00029-020-0551-2

    work page doi:10.1007/s00029-020-0551-2 2020

  12. [12]

    Chernikov, S

    A. Chernikov, S. Starchenko, and M. M. Thomas. Ramsey growth in some NIP structures.Journal of the Institute of Mathematics of Jussieu, 20(1):1–29, 2021. doi: 10.1017/S1474748018000335

    work page doi:10.1017/s1474748018000335 2021

  13. [13]

    Chudnovsky

    M. Chudnovsky. The Erdős–Hajnal conjecture—a survey.Journal of Graph Theory, 75(2):178–190, 2014. doi: 10.1002/jgt.21730. 17

    work page doi:10.1002/jgt.21730 2014

  14. [14]

    Chudnovsky and S

    M. Chudnovsky and S. Safra. The Erdős–Hajnal conjecture for bull-free graphs.Journal of Combinatorial Theory, Series B, 98(6):1301–1310, 2008. doi: 10.1016/j.jctb.2008.02.005

    work page doi:10.1016/j.jctb.2008.02.005 2008

  15. [15]

    Chudnovsky, J

    M. Chudnovsky, J. Fox, A. Scott, P. Seymour, and S. Spirkl. Towards Erdős–Hajnal for graphs with no 5-hole.Combinatorica, 39(5):983–991, 2019. doi: 10.1007/s00493-019-3957-8

    work page doi:10.1007/s00493-019-3957-8 2019

  16. [16]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Erdős–Hajnal for graphs with no 5-hole.Proceedings of the London Mathematical Society, 126(3):997–1014, 2023. doi: 10.1112/plms.12504

    work page doi:10.1112/plms.12504 2023

  17. [17]

    Conlon, J

    D. Conlon, J. Fox, J. Pach, B. Sudakov, and A. Suk. Ramsey-type results for semi-algebraic rela- tions.Transactions of the American Mathematical Society, 366(9):5043–5065, 2014. doi: 10.1090/ S0002-9947-2014-06044-6

    2014

  18. [18]

    T. T. Do. Zarankiewicz’s problem for semi-algebraic hypergraphs.Journal of Combinatorial Theory, Series A, 158:621–642, 2018. doi: 10.1016/j.jcta.2018.04.007

    work page doi:10.1016/j.jcta.2018.04.007 2018

  19. [19]

    Erdős and A

    P. Erdős and A. Hajnal. On spanned subgraphs of graphs. InContributions to Graph Theory and Its Applications, pages 80–96. Tech. Hochschule Ilmenau, Ilmenau, 1977

    1977

  20. [20]

    Erdős and A

    P. Erdős and A. Hajnal. Ramsey-type theorems.Discrete Applied Mathematics, 25(1–2):37–52, 1989. doi: 10.1016/0166-218X(89)90057-2

    work page doi:10.1016/0166-218x(89)90057-2 1989

  21. [21]

    Erdős and R

    P. Erdős and R. Rado. Combinatorial theorems on classifications of subsets of a given set.Proceedings of the London Mathematical Society, 2:417–439, 1952. doi: 10.1112/plms/s3-2.1.417

    work page doi:10.1112/plms/s3-2.1.417 1952

  22. [22]

    J. Forster. A linear lower bound on the unbounded error probabilistic communication complexity.Journal of Computer and System Sciences, 65(4):612–625, 2002. doi: 10.1016/S0022-0000(02)00019-3

    work page doi:10.1016/s0022-0000(02)00019-3 2002

  23. [23]

    Fox and B

    J. Fox and B. Sudakov. Induced Ramsey-type theorems.Advances in Mathematics, 219(6):1771–1800,

  24. [24]

    doi: 10.1016/j.aim.2008.07.009

    work page doi:10.1016/j.aim.2008.07.009 2008

  25. [25]

    J. Fox, J. Pach, and C. D. Tóth. Intersection patterns of curves.Journal of the London Mathematical Society, 83(2):389–406, 2011. doi: 10.1112/jlms/jdq082

    doi:10.1112/jlms/jdq082 2011

  26. [26]

    J. Fox, J. Pach, and A. Suk. A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing.SIAM Journal on Computing, 45(6):2199–2223, 2016. doi: 10.1137/15M1007355

    doi:10.1137/15m1007355 2016

  27. [27]

    J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. A semi-algebraic version of Zarankiewicz’s problem. Journal of the European Mathematical Society, 19(6):1785–1810, 2017. doi: 10.4171/JEMS/705

    work page doi:10.4171/jems/705 2017

  28. [28]

    J. Fox, J. Pach, and A. Suk. Erdős–Hajnal conjecture for graphs with bounded VC-dimension.Discrete & Computational Geometry, 61(4):809–829, 2019. doi: 10.1007/s00454-019-00074-1

    work page doi:10.1007/s00454-019-00074-1 2019

  29. [29]

    J. Fox, T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. II. sparse and dense sets in cographs.European Journal of Combinatorics, 124:104075, 2025. doi: 10.1016/j.ejc.2024.104075

    doi:10.1016/j.ejc.2024.104075 2025

  30. [30]

    Frankl and J

    P. Frankl and J. Pach. On disjointly representable sets.Combinatorica, 4(1):39–45, 1984. doi: 10.1007/ BF02579155

    1984

  31. [31]

    G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl–Pach upper bound is not tight for any uniformity.Journal of Combinatorial Theory, Series A, 217:106078, 2026. doi: 10.1016/j.jcta.2025.106078

    work page doi:10.1016/j.jcta.2025.106078 2026

  32. [32]

    Gishboliner and A

    L. Gishboliner and A. Shapira. On Rödl’s theorem for cographs.Electronic Journal of Combinatorics, 30 (4):Paper No. 4.13, 2023. doi: 10.37236/11603

    work page doi:10.37236/11603 2023

  33. [33]

    Huang, Y

    S. Huang, Y. Ju, and Y. Zhou. Erdős–hajnal beyond the five-vertex path.arXiv preprint arXiv:2606.06258,

    Pith/arXiv arXiv

  34. [34]

    doi: 10.48550/arXiv.2606.06258. 18

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2606.06258

  35. [35]

    Janzer and C

    O. Janzer and C. Pohoata. On the Zarankiewicz problem for graphs with bounded VC-dimension. Combinatorica, 44(4):839–848, 2024. doi: 10.1007/s00493-024-00095-2

    work page doi:10.1007/s00493-024-00095-2 2024

  36. [36]

    M. C. Laskowski. Vapnik-chervonenkis classes of definable sets.Journal of the London Mathematical Society, 45(2):377–384, 1992. doi: 10.1112/jlms/s2-45.2.377

    doi:10.1112/jlms/s2-45.2.377 1992

  37. [37]

    Lovász and B

    L. Lovász and B. Szegedy. Regularity partitions and the topology of graphons. InAn Irregular Mind, volume 21 ofBolyai Society Mathematical Studies, pages 415–446. János Bolyai Mathematical Society, Budapest, 2010

    2010

  38. [38]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VI. bounded VC-dimension.Advances in Mathematics, 482:110601, 2025. doi: 10.1016/j.aim.2025.110601

    work page doi:10.1016/j.aim.2025.110601 2025

  39. [39]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. IV. New graphs with the Erdős–Hajnal property.Transactions of the American Mathematical Society, 2026. Accepted for publication

    2026

  40. [40]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. V. All paths approach Erdős–Hajnal. Advances in Combinatorics, 2026. Accepted for publication

    2026

  41. [41]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VII. The five-vertex path.Proceedings of the London Mathematical Society, 2026. doi: 10.1112/plms.70133

    work page doi:10.1112/plms.70133 2026

  42. [42]

    Pach and J

    J. Pach and J. Solymosi. Crossing patterns of segments.Journal of Combinatorial Theory, Series A, 96 (2):316–325, 2001. doi: 10.1006/jcta.2001.3184

    work page doi:10.1006/jcta.2001.3184 2001

  43. [43]

    N. Sauer. On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147,

  44. [44]

    doi: 10.1016/0097-3165(72)90019-2

    doi:10.1016/0097-3165(72)90019-2

  45. [45]

    S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972

    1972

  46. [46]

    Simon.A Guide to NIP Theories, volume 44 ofLecture Notes in Logic

    P. Simon.A Guide to NIP Theories, volume 44 ofLecture Notes in Logic. Association for Symbolic Logic and Cambridge Scientific Publishers, 2015

    2015

  47. [47]

    I. Tomon. String graphs have the Erdős–Hajnal property.Journal of the European Mathematical Society, 26(1):275–287, 2024. doi: 10.4171/JEMS/1376

    work page doi:10.4171/jems/1376 2024

  48. [48]

    V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and its Applications, 16(2):264–280, 1971. doi: 10.1137/1116025

    doi:10.1137/1116025 1971

  49. [49]

    H. E. Warren. Lower bounds for approximation by nonlinear manifolds.Transactions of the American Mathematical Society, 133(1):167–178, 1968. doi: 10.2307/1994977

    work page doi:10.2307/1994977 1968

  50. [50]

    Yang and X

    T. Yang and X. Yu. Maxmum size of a uniform family with bounded VC-dimension.arXiv preprint arXiv:2508.14334, 2025. 19

    Pith/arXiv arXiv 2025