Twins in graphs

Abstract

A basic pigeonhole principle insures an existence of two objects of the same type if the number of objects is larger than the number of types. Can such a principle be extended to a more complex combinatorial structure? Here, we address such a question for graphs. We call two disjoint subsets $A,B$ of vertices \emph{\textbf{twins}} if they have the same cardinality and induce subgraphs of the same size. Let $t(G)$ be the largest $k$ such that $G$ has twins on $k$ vertices each. We provide the bounds on $t(G)$ in terms of the number of edges and vertices using discrepancy results for induced subgraphs. In addition, we give conditions under which $t(G)=|V(G)|/2$ and show that if $G$ is a forest then $t(G)\ge |V(G)|/2-1$.

12 pages