FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 13, 15:00 ~ 15:30 - Room B11
An Erdős-Lovász-Spencer Theorem for permutations and its consequences for parameter testing
Carlos Hoppen
Universidade Federal do Rio Grande do Sul, Brazil - choppen@ufrgs.br
The classical theorem of Erdős, Lovász and Spencer [Strong independence of graphcopy functions, Graph Theory and Related Topics, Academic Press (1979), 165--172] asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and apply the methods used in its proof to give an example of a permutation parameter that is both bounded and testable, but not finitely forcible.
Joint work with Roman Glebov (ETH Zürich, Switzerland), Tereza Klimošová (University of Warwick, United Kingdom), Yoshiharu Kohayakawa (Universidade de São Paulo, Brazil), Daniel Král (University of Warwick, United Kingdom) and Hong Liu (University of Illinois at Urbana-Champaign, United States).