Turán-Type Bounds for Graphs Containing Large $F$-Sparse Sets
We study Turán-type extremal problems for graphs containing a large $F$-sparse vertex set, meaning a vertex set whose induced subgraph contains few copies of $F$. For integers $r>s\ge 1$, we prove that if a $K_{r+1}$-free graph $G$ on $n$ vertices contains a set $M$ of size $m\ge \lceil sn/r\rceil$ such that $G[M]$ is $K_{s+1}$-free, then \[ e(G)\le m(n-m)+t_s(m)+t_{r-s}(n-m). \] We characterize the equality cases as the complete $r$-partite graphs whose vertex classes split into two balanced groups of total sizes $m$ and $n-m$, consisting of $s$ and $r-s$ classes, respectively. We also…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.10832
curl -X POST /api/v1/records/arxiv/2607.10832/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.10832/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'