2013/03/22 by Maria Axenovich, Ryan R. Martin, Torsten Ueckerdt
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Cardinality (data modeling) #Combinatorics #Computer science #Discrete mathematics #Disjoint sets #Limits and Structures in Graph Theory #Mathematics #Pigeonhole principle #graph theory and CDMA systems #math.CO #msc:05C35 #msc:05C80
paper · pdf · doi:10.1016/j.ejc.2014.01.007
published as European J. Combin 39 (2014), 188--197 · 12 pages
arxiv created 2013/03/22 · openalex publication_date 2014/02/07 · arxiv updated 2014/05/06 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 \emphtwins 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) ≥ |V(G)|/2 - 1.