The Alon-Shikhelman conjecture for finite families $\mathcal{H}$ is proved and an elementary proof of the Alon-Shapira-Sudakov result when $\mathcal{H}$ is finite is obtained.
Abstract
For graphs $G, T$ and a graph-family $\mathcal{H}$, let $ex(G,T,\mathcal{H})$ denote the maximum possible number of copies of $T$ in an $\mathcal{H}$-free subgraph of $G$. Alon and Shikhelman conjectured that for every family of graphs $\mathcal{H}$ with $\chi(H)>s$ for every $H \in \mathcal{H}$, it is NP-hard to compute $ex(G,K_s,\mathcal{H})$, and even to approximate it up to additive error $n^{s-\delta}$ on $n$-vertex graphs, for any fixed $\delta>0$. The case $s=2$ was established in a breakthrough result of Alon, Shapira and Sudakov. We prove the Alon-Shikhelman conjecture for finite families $\mathcal{H}$. In particular, we obtain an elementary proof of the Alon-Shapira-Sudakov result when $\mathcal{H}$ is finite.
Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman [Algorithmica, 2022] conjectured that if $e(T)>0$ and no member of $\mathcal{F}$ is a subgraph...
Yi-Han Chen, Jia-Lin He, Xi-He Li et al.· 1 citation· ⚡1
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, an...
Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht· 0 citations
For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\g...
For graphs $H$ and $F$, let $\text{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Gerbner, Gy\H{o}ri, Methuku, and Vizer proved that $\text{ex}(n,C_{2\ell},C_{2k})=\Theta(n^\ell)$ for $k>\ell\ge2$. They determined the leading term for $\ell=2$, but for $k>\ell\ge3$ their general...
For a graph $G$, let $\text{cg}(G)$ be the maximum $k\in \mathbb N$ for which $G$ contains a $k$-vertex cograph as an induced subgraph. The Erd\H{o}s-Hajnal conjecture asserts that for every proper hereditary graph class $\mathcal{G}$, there exists $\gamma\in(0,1]$ such that every $n$-vertex graph $G\in\mathcal{G}$ sat...
An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, R\"{o}dl, and Schacht conjectured that, for any fixed graph $F$, th...
Hyunwoo Lee· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
