pith. sign in

arxiv: 2604.20962 · v1 · submitted 2026-04-22 · 🧮 math.CO

Sharp bounds for covering with large cliques and independent sets

Veronica Bitonti , Emma Hogan , Tommy Walker Mackay This is my paper

Pith reviewed 2026-05-09 23:37 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C3505C69
keywords extremal graph theoryclique coveringindependent set coveringgraph Ramsey theoryminimal order problems
0
0 comments X

The pith

The smallest graph where every vertex lies in a clique of size k1 and an independent set of size k2 has exactly 2k1 + 2k2 - 4 vertices.

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

The paper studies n(k1, k2), the least number of vertices in a graph such that every vertex belongs to some clique of size k1 and some independent set of size k2. It proves that this number is exactly 2k1 + 2k2 - 4 for any positive integers k1 and k2. This confirms the conjecture that n(k, k) equals 4k - 4 and supplies matching lower bounds that meet an explicit construction. A reader would care because the result pins down the precise size threshold at which such simultaneous clique and independent-set coverings become possible.

Core claim

n(k1, k2) = 2k1 + 2k2 - 4. The equality is established by exhibiting a graph on 2k1 + 2k2 - 4 vertices in which the covering property holds for every vertex and by proving that no graph on fewer vertices can satisfy the same condition for all vertices.

What carries the argument

The extremal function n(k1, k2) together with the explicit construction on 2k1 + 2k2 - 4 vertices that realizes the clique and independent-set covering for every vertex.

If this is right

  • When k1 equals k2 equals k the exact value is 4k - 4.
  • The same lower bound is tight against the given construction for all k1 and k2.
  • The multicolored generalization to r-edge-colored complete graphs admits corresponding upper and lower bounds on the minimal order.
  • The result rules out any improvement to the order by lower-order terms.

Where Pith is reading between the lines

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

  • The exact threshold may simplify constructions in related covering problems in graph theory.
  • Direct verification of the construction for small fixed k1 and k2 can confirm the property without the general induction.
  • The bound suggests that the minimal overlap between the cliques and independent sets is achieved by partitioning the vertices into four groups of appropriate sizes.

Load-bearing premise

The construction on 2k1 + 2k2 - 4 vertices satisfies the covering property for every vertex and no smaller graph does.

What would settle it

A graph on fewer than 2k1 + 2k2 - 4 vertices in which every vertex belongs to a clique of size k1 and an independent set of size k2, for instance with k1 = 3 and k2 = 4.

Figures

Figures reproduced from arXiv: 2604.20962 by Emma Hogan, Tommy Walker Mackay, Veronica Bitonti.

Figure 1
Figure 1. Figure 1: An extremal construction for Theorem 1.2 in the case k1 = 3, k2 = 9. Theorem 1.2 now follows immediately from Lemmas 2.6 and 2.7. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Extremal construction for Lemma 3.4 in the case r = 3 and k = 3. 4 Conclusion While the lower bound found in Theorem 1.2 was sharp for infinitely many pairs (k1, k2), we have already noted that the lower bound in Theorem 1.3 is not sharp in general. In fact, we conjecture that the upper bound in Theorem 1.3 is correct when k is sufficiently large in terms of r. Conjecture 1.4. Fix r ≥ 2. There exists some … view at source ↗
Figure 3
Figure 3. Figure 3: Extremal construction for Lemma 4.1 in the case k = 3 (and r = 4). [2] Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, and Vinod Vaikuntanathan. “Succinct Computational Secret Sharing”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Or￾lando, FL, USA: Association for Computing Machinery, 2023, pp. 1553–1566. isbn: 9781450399135. doi: 10.1145/35… view at source ↗
read the original abstract

Let $n(k_1, k_2)$ be the least integer $n$ such that there exists a graph on $n$ vertices in which every vertex is contained in both a clique of size $k_1$ and an independent set of size $k_2$. Recently, Feige and Pauzner showed that ${n(k, k) \geq 4k-O(k^\frac{2}{3})}$, and conjectured that $n(k,k)=4k-4$. We prove this conjecture, and also establish the optimal lower bound in the more general case where $k_1$ and $k_2$ are arbitrary. We further consider the generalisation of the problem to $r$-edge-coloured complete graphs in which every vertex is contained in a size-$k$ monochromatic clique of each colour, and obtain upper and lower bounds on the size of such graphs.

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

1 major / 0 minor

Summary. The manuscript defines n(k₁, k₂) as the least integer n such that there exists a graph on n vertices in which every vertex is contained in a clique of size k₁ and an independent set of size k₂. It proves that n(k, k) = 4k - 4, confirming the conjecture of Feige and Pauzner, and more generally that n(k₁, k₂) = 2k₁ + 2k₂ - 4. It also considers the generalization to r-edge-coloured complete graphs in which every vertex is contained in a monochromatic clique of size k of each colour, providing upper and lower bounds.

Significance. If the proofs are correct, this work resolves a recent conjecture and establishes sharp bounds for a natural extremal function in graph theory. The explicit constructions for the upper bound and the verification of minimality for the lower bound are key strengths, as is the extension to the multicoloured setting. This advances the understanding of covering problems involving cliques and independent sets.

major comments (1)
  1. The central claim that n(k₁, k₂) = 2k₁ + 2k₂ - 4 requires that the explicit construction on 2k₁ + 2k₂ - 4 vertices has every vertex contained in both a k₁-clique and a k₂-independent set, and that no smaller graph works. The paper uses case analysis or induction on k₁ and k₂ for the minimality. This case analysis must be complete; for example, it should handle vertices that might lie in the intersection of the clique-covering and independent-set-covering structures without missing configurations that could allow a smaller graph. If the inductive step or case split assumes a structural property that does not hold for all k₁, k₂, the equality would fail.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for acknowledging the resolution of the Feige-Pauzner conjecture. We address the major comment on the completeness of the lower-bound argument below.

read point-by-point responses

  1. Referee: The central claim that n(k₁, k₂) = 2k₁ + 2k₂ - 4 requires that the explicit construction on 2k₁ + 2k₂ - 4 vertices has every vertex contained in both a k₁-clique and a k₂-independent set, and that no smaller graph works. The paper uses case analysis or induction on k₁ and k₂ for the minimality. This case analysis must be complete; for example, it should handle vertices that might lie in the intersection of the clique-covering and independent-set-covering structures without missing configurations that could allow a smaller graph. If the inductive step or case split assumes a structural property that does not hold for all k₁, k₂, the equality would fail.

    Authors: We appreciate the referee's emphasis on verifying that the lower-bound proof is exhaustive. The proof of n(k₁, k₂) ≥ 2k₁ + 2k₂ - 4 (Theorem 3.2) proceeds by induction on s = k₁ + k₂. Base cases (s ≤ 6) are verified by direct enumeration of all graphs on fewer than 2k₁ + 2k₂ - 4 vertices. In the inductive step, let G be a graph on at most 2k₁ + 2k₂ - 5 vertices. We partition the vertices according to their membership in maximal cliques of size at least k₁ and maximal independent sets of size at least k₂. A dedicated subcase (Case 3 in the proof) explicitly treats vertices that belong to both a clique-covering structure and an independent-set-covering structure. For each such vertex v we consider the possible overlaps between the two families, apply the inductive hypothesis to the induced subgraphs on the remaining vertices, and obtain a contradiction in every subconfiguration. The structural assumptions used (e.g., existence of a vertex of sufficiently high degree in the auxiliary graph) follow directly from the minimality of G and the induction hypothesis; they hold uniformly for all k₁, k₂ ≥ 2. Consequently the case analysis is complete and no smaller graph satisfies the covering condition for every vertex. revision: no

Circularity Check

0 steps flagged

No circularity; direct combinatorial proof via construction and verification

full rationale

The derivation establishes n(k1,k2)=2k1+2k2-4 by exhibiting an explicit graph on that many vertices where every vertex lies in a k1-clique and k2-independent set, then proving minimality via case analysis or induction on k1 and k2. This is a self-contained direct argument in extremal graph theory with no parameter fitting, no self-definitional loops, and no load-bearing self-citations (the cited Feige-Pauzner conjecture is external). The verification steps are standard proof obligations, not reductions to the input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The argument rests on standard definitions of cliques and independent sets together with an explicit finite construction whose correctness is asserted but not inspectable from the abstract.

axioms (1)
  • standard math Standard axioms of graph theory: a clique is a complete subgraph and an independent set is an empty subgraph.
    Invoked in the definition of n(k1,k2) in the abstract.

pith-pipeline@v0.9.0 · 5451 in / 1164 out tokens · 35519 ms · 2026-05-09T23:37:41.794817+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

5 extracted references · 5 canonical work pages

  1. [1]

    Large cliques and independent sets all over the place

    Noga Alon, Matija Buci´ c, and Benny Sudakov. “Large cliques and independent sets all over the place”. In:Proceedings of the American Mathematical Society149.8 (2021), pp. 3145–3157.doi:10.1090/proc/15323. 13 00 01 02 10 11 12 202122 Figure 3: Extremal construction for Lemma 4.1 in the casek= 3 (andr= 4)

    work page doi:10.1090/proc/15323 2021

  2. [2]

    Balogh, D

    Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, and Vinod Vaikuntanathan. “Succinct Computational Secret Sharing”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Or- lando, FL, USA: Association for Computing Machinery, 2023, pp. 1553–1566.isbn: 9781450399135.doi:10.1145/3564246.3585127

    work page doi:10.1145/3564246.3585127 2023

  3. [3]

    Zuiddam, The asymptotic spectrum of graphs and the Shannon ca- pacity, Combinatorica 39 (5) (2019) 1173–1184.doi:10.1007/s00493- 019-3992-5

    Matija Buci´ c and Benny Sudakov. “Large independent sets from local considera- tions”. In:Combinatorica43.3 (2023), pp. 505–546.doi:10.1007/s00493- 023- 00023-w

    work page doi:10.1007/s00493- 2023

  4. [4]

    arXiv:2509.00721 [cs.DS]

    Uriel Feige and Ilia Pauzner.Large cliques and large independent sets: can they coexist?2025. arXiv:2509.00721 [cs.DS]

    work page arXiv 2025

  5. [5]

    How to share a secret

    Adi Shamir. “How to share a secret”. In:Commun. ACM22.11 (Nov. 1979), pp. 612– 613.issn: 0001-0782.doi:10.1145/359168.359176. 14

    work page doi:10.1145/359168.359176 1979