Densities in large permutations and parameter testing |
| |
| Institution: | 1. School of Computer Science and Engineering, Hebrew University, Jerusalem, 9190401, Israel;2. Instituto de Matemática, UFRGS–Avenida Bento Gonçalves, 9500, 91509-900, Porto Alegre, RS, Brazil;3. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic;4. Instituto de Matemática e Estatística, USP–Rua do Matão 1010, 05508–090 São Paulo, SP, Brazil;5. Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK;6. Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
