Sharp bounds for covering with large cliques and independent sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915950690828288 |
|---|---|
| author | Bitonti, Veronica Hogan, Emma Mackay, Tommy Walker |
| author_facet | Bitonti, Veronica Hogan, Emma Mackay, Tommy Walker |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_20962 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sharp bounds for covering with large cliques and independent sets Bitonti, Veronica Hogan, Emma Mackay, Tommy Walker Combinatorics 05C69 (Primary) 05C35 (Secondary) 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. |
| title | Sharp bounds for covering with large cliques and independent sets |
| topic | Combinatorics 05C69 (Primary) 05C35 (Secondary) |
| url | https://arxiv.org/abs/2604.20962 |