
arXiv: 2006.14466
In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = \min \{k \in \mathbb N : \mbox{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turán exponent, i.e., ${\rm ex}(n, H) = Θ(n^r)$ for some $r$, we show that $Ω(n^{2/r -1}) = f(n, H) = O (n^{2/r-1} \log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turán exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Θ(n^{1/3})$ for any fixed $t$.
12 pages; In v1 and v2, there were missing floors and ceilings in Theorem 5 that in some cases would lead to an incorrect result. In v3, we correct this minor error
ddc:510, Extremal problems in graph theory, Graph representations (geometric and intersection representations, etc.), split, Enumeration in graph theory, 05C35, 05D40, 510, forbidden subgraphs, extremal function, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, info:eu-repo/classification/ddc/510
ddc:510, Extremal problems in graph theory, Graph representations (geometric and intersection representations, etc.), split, Enumeration in graph theory, 05C35, 05D40, 510, forbidden subgraphs, extremal function, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, info:eu-repo/classification/ddc/510
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
