pith. sign in

arxiv: 2606.25055 · v1 · pith:B23FM57Lnew · submitted 2026-06-23 · 🧮 math.CO

Pseudoshattering Pairs

Noga Alon , Varun Sivashankar This is my paper

Pith reviewed 2026-06-25 22:34 UTC · model grok-4.3

classification 🧮 math.CO
keywords pseudoshatteringLYM inequalitybipartite cyclesSauer-Shelah-Perles lemmaextremal combinatoricsvector familiescombinatorial dimension
0
0 comments X

The pith

A cyclic construction gives the largest families of [b]^k vectors where every pair induces a cycle in their coordinate bipartite graph, for large k.

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

The paper examines families of strings over an alphabet of size b and length k with the property that every two strings form a cycle when their coordinate pairs are viewed as edges in a bipartite graph between two copies of the alphabet. A natural construction is proposed that achieves large such families, and the authors conjecture it is optimal for large k. They establish an LYM-type upper bound that matches the construction asymptotically and exactly in cases where k is large and divisible by b. Refinements using circular orderings yield sharp bounds when k is congruent to -1 modulo b, and for b=3 an exact result holds for large k congruent to -1 mod 3. This connects to notions of dimension in learning theory via the pseudocube formulation of generalized Sauer-Shelah lemmas.

Core claim

We give a natural construction for such families and conjecture that it is optimal whenever k is large relative to b. We prove an LYM-type upper bound that is asymptotically tight with respect to this construction, and is exact when k is large and divisible by b. We then refine the argument using a circular ordering, obtaining the sharp full-support bound when k ≡ -1 mod b. In the case b=3, we prove the exact general result when k ≡ -1 mod 3 and k is sufficiently large.

What carries the argument

The bipartite graph on two copies of [b] with edges from the pairs (x_t, y_t) for coordinates t, and the requirement that this graph contains a cycle for every distinct pair x, y in the family.

If this is right

  • The size of such families is bounded above by the construction asymptotically.
  • The bound is exact when k is large and divisible by b.
  • A sharp full-support bound holds when k ≡ -1 mod b.
  • For b=3 and sufficiently large k ≡ -1 mod 3 the exact maximum size is achieved by the construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result would imply corresponding bounds on the Daniely-Shalev-Shwartz dimension for hypothesis classes over larger alphabets.
  • The cycle condition may characterize a generalized form of non-shatterability in product spaces.
  • Similar cycle-enforcing conditions could be studied in other extremal problems on grids or products.

Load-bearing premise

The LYM inequality or a suitable variant can be applied to upper-bound the size of families in which every pair of vectors induces a cycle in the coordinate-pair bipartite graph.

What would settle it

A family of vectors larger than the proposed cyclic construction for some b and k not covered by the exact cases would disprove the optimality conjecture.

read the original abstract

For two vectors $x,y\in [b]^k$, consider the bipartite graph with two copies of $[b]$ in which $i$ on the left is joined to $j$ on the right if $(x_t,y_t)=(i,j)$ for some coordinate $t$. We study the largest size of a family $C\subseteq [b]^k$ such that, for every two distinct $x,y\in C$, this bipartite graph contains a cycle. We give a natural construction for such families and conjecture that it is optimal whenever $k$ is large relative to $b$. We prove an LYM-type upper bound that is asymptotically tight with respect to this construction, and is exact when $k$ is large and divisible by $b$. We then refine the argument using a circular ordering, obtaining the sharp full-support bound when $k\equiv -1\pmod b$. In the case $b=3$, we prove the exact general result when $k\equiv -1\pmod 3$ and $k$ is sufficiently large. The problem is motivated by the Daniely--Shalev-Shwartz dimension and the pseudocube formulation of a higher-alphabet Sauer-Shelah-Perles lemma.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the maximum size of a family C ⊆ [b]^k such that for every distinct x, y ∈ C, the bipartite graph with parts [b] and [b] and edges corresponding to coordinate pairs (x_t, y_t) contains a cycle. A natural construction is presented and conjectured to be optimal for large k relative to b. An LYM-type upper bound is proved that is asymptotically tight with the construction and exact when k is large and divisible by b; a circular-ordering refinement yields the sharp full-support bound when k ≡ −1 (mod b), with an exact result for b=3 when k ≡ −1 (mod 3) and k sufficiently large. The work is motivated by the Daniely–Shalev-Shwartz dimension and pseudocube formulations of the Sauer–Shelah–Perles lemma.

Significance. If the claimed bounds and exactness results hold, the manuscript contributes new tight extremal bounds in the setting of pairwise cycle conditions on coordinate-pair graphs, extending LYM techniques to this pseudoshattering context. The asymptotic matching with the construction and the modular exactness results (especially for b=3) are strengths, as is the explicit link to learning-theoretic dimensions. These results could inform higher-alphabet generalizations of classical shattering lemmas.

minor comments (2)
  1. The abstract refers to 'the construction' without a brief description or reference to its section; adding one sentence would improve readability for readers outside the immediate area.
  2. Notation for the bipartite graph (two copies of [b]) is introduced in the abstract but should be restated with a numbered definition or equation in §2 for self-contained reading.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report highlights the asymptotic tightness, modular exactness results, and connections to learning-theoretic dimensions, which align with our goals. No specific major comments were raised.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation applies the standard LYM inequality (an external combinatorial fact) to families where every pair induces a cycle in the coordinate-pair bipartite graph. Upper bounds are obtained directly from this tool and shown to match the size of an explicit natural construction asymptotically and exactly in specified regimes (k large and divisible by b; refinements for k ≡ -1 mod b). No equations reduce to fitted parameters, self-definitions, or self-citation chains; the central claims rest on the independent LYM inequality rather than any internal renaming or ansatz smuggled from prior author work. The motivation from Daniely-Shalev-Shwartz dimension is separate from the proof steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of an LYM-type inequality to the cycle condition and on the optimality of a natural construction; no free parameters, invented entities, or non-standard axioms are introduced.

axioms (1)
  • domain assumption An LYM-type inequality applies to families of vectors in which every pair induces a cycle in the coordinate-pair bipartite graph.
    The paper invokes this inequality to obtain the stated upper bounds.

pith-pipeline@v0.9.1-grok · 5739 in / 1254 out tokens · 35343 ms · 2026-06-25T22:34:56.274834+00:00 · methodology

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

18 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    N. Alon, V. Sivashankar, and D. G. Zhu,Maximum shattering, J. Combin. Des.33(2025), no. 12, 456–470

    2025

  2. [2]

    Daniely and S

    A. Daniely and S. Shalev-Shwartz,Optimal learners for multiclass problems, inProceedings of the 27th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 35, PMLR, 2014, pp. 287–316

    2014

  3. [3]

    Das and T

    S. Das and T. Mészáros,Small arrays of maximum coverage, J. Combin. Des.26(2018), no. 11, 487–504

    2018

  4. [4]

    P. L. Erdős, Z. Füredi, and G. O. H. Katona,Two-part andk-Sperner families: new proofs using permutations, SIAM J. Discrete Math.19(2005), no. 2, 489–500

    2005

  5. [5]

    Frankl,Old and new applications of Katona’s circle, European J

    P. Frankl,Old and new applications of Katona’s circle, European J. Combin.95(2021), Article 103339

    2021

  6. [6]

    Gargano, J

    L. Gargano, J. Körner, and U. Vaccaro,Sperner capacities, Graphs Combin.9(1993), 31–46

    1993

  7. [7]

    Gysel, F

    R. Gysel, F. Lam, and D. Gusfield,Constructing perfect phylogenies and proper triangulations for three-state characters, Algorithms Mol. Biol.7(2012), Article 26

    2012

  8. [8]

    An Optimal Sauer Lemma Over $k$-ary Alphabets

    S. Hanneke, Q. Meng, S. Moran, and A. Shaeiri,An optimal Sauer lemma overk-ary alphabets, arXiv:2604.12952, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  9. [9]

    A. J. W. Hilton and E. C. Milner,Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2)18(1967), 369–384

    1967

  10. [10]

    G. O. H. Katona,A simple proof of the Erdős–Chao Ko–Rado theorem, J. Combin. Theory Ser. B13 (1972), no. 2, 183–184

    1972

  11. [11]

    G. O. H. Katona,The cycle method and its limits, inNumbers, Information and Complexity, Kluwer Academic Publishers, Boston, 2000, pp. 129–141

    2000

  12. [12]

    D. J. Kleitman and J. Spencer,Families ofk-independent sets, Discrete Math.6(1973), 255–262

    1973

  13. [13]

    L. D. Meshalkin,Eine Verallgemeinerung des Satzes von Sperner über Anzahl der Untermengen einer endlichen Menge, Teor. Veroyatnost. i Primenen.8(1963), 219–220

    1963

  14. [14]

    Pajor,Sous-espacesℓ n 1 des espaces de Banach, Hermann, Paris, 1985

    A. Pajor,Sous-espacesℓ n 1 des espaces de Banach, Hermann, Paris, 1985

    1985

  15. [15]

    Poljak, A

    S. Poljak, A. Pultr, and V. Rödl,On qualitatively independent partitions and related problems, Discrete Appl. Math.6(1983), 193–205

    1983

  16. [16]

    Sauer,On the density of families of sets, J

    N. Sauer,On the density of families of sets, J. Combinatorial Theory Ser. A13(1972), 145–147

    1972

  17. [17]

    Shelah,A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J

    S. Shelah,A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math.41(1972), 247–261

    1972

  18. [18]

    Shutters, S

    B. Shutters, S. Vakati, and D. Fernández-Baca,Incompatible quartets, triplets, and characters, Algorithms Mol. Biol.8(2013), Article 11. Department of Mathematics, Princeton University, Princeton, New Jersey, USA Email address:nalon@math.princeton.edu Department of Mathematics, Princeton University, Princeton, New Jersey, USA Email address:varunsiva@princeton.edu

    2013