Densities in large permutations and parameter testing

详细信息    查看全文

• 作者：Roman Glebov^a ; ^{roman.l.glebov@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Carlos Hoppen^b ; ^{choppen@ufrgs.br" class="auth_mail" title="E-mail the corresponding author} ; Tereza Klimo&scaron ; ová ; ^c ; ^{tereza@kam.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author} ; Yoshiharu Kohayakawa^d ; ^{yoshi@ime.usp.br" class="auth_mail" title="E-mail the corresponding author} ; Daniel Krá ; l&rsquo ; ^e ; ^f ; ^{d.kral@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Hong Liu^e ; ^{h.liu.9@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：Complete
• 页码：89-99
• 全文大小：436 K

文摘

A classical theorem of Erdős, Lovász and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.