IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Splits with Forbidden Graphs

  • Sept. 18, 2020
  • 2:30 p.m.

Abstract

In this talk, we fix a graph $H$ and ask into how many vertices 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 set is a pairwise disjoint union of $n$ parts of size at most $k$, such that there is an edge between any two distinct parts. Let

$$ f(n,H) = \min \{k \in \mathbb N : \text{there is an } (n,k)\text{-graph } G \text{ 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) = \Theta(n^r)$ for some $r$, we show that $\Omega (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 upper and a lower Turán exponents do not differ by much. In addition, we prove that $f(n, K _ {2,t}) =\Theta(n^{1/3})$ for any fixed integer $t\geq 2$.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC