论文标题
用禁止的子图片分裂
Splits with forbidden subgraphs
论文作者
论文摘要
在本说明中，我们修复了图$ h $，并询问可以“拆分”一个大小$ n $的每个顶点，以使结果图为$ h $ free。形式上：图是$（n，k）$ - 图形，如果其顶点集是最多$ k $的$ n $零件的成对差异，则每个两个不同的部分之间都有边缘。让 $ f（n，h）= \ min \ {k \ in \ mathbb n：\ mbox {有一个$（n，k）$ - 图$ g $，以至于$ h \ not \ not \ subseteq g $} \}。 $$ Barbanera和Ueckerdt观察到$ f（n，h）= 2 $对于任何图形$ h $，不是双分部分。如果图$ h $是两部分，并且具有明确定义的Turán指数，即$ {\ rm ex}（n，h）=θ（n^r）对于某些$ r $，我们表明$ω（n^{2/r -1}）= f（n，r -1}）= f（n，h）= f（n，h）= o（n^n^n^n^n^{2/r-1} $ r-1} \ r-r-r-n} =我们将此结果扩展到所有两分图的图形，上层和下图恩指数没有太大差异。此外，我们证明$ f（n，k_ {2，t}）=θ（n^{1/3}）$对于任何固定的$ t $。
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$.
