×

zbMATH — the first resource for mathematics

Densities in large permutations and parameter testing. (English) Zbl 1348.05010
Summary: A classical theorem of P. Erdős et al. [Graph theory and related topics, Proc. Conf. Honour W. T. Tutte, Waterloo/Ont. 1977, 165–172 (1979; Zbl 0462.05057)] 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 C. Hoppen et al. [in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 66–75 (2010; Zbl 1288.68187)].

MSC:
05A05 Permutations, words, matrices
05C42 Density (toughness, etc.)
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albert, M. H.; Atkinson, M. D.; Klazar, M., The enumeration of simple permutations, J. Integer Seq., 6, 2, 3, (2003) · Zbl 1065.05001
[2] Alon, N.; Fischer, E.; Newman, I.; Shapira, A., A combinatorial characterization of the testable graph properties: it’s all about regularity, SIAM J. Comput., 39, 1, 143-167, (2009) · Zbl 1197.05159
[3] Alon, N.; Shapira, A., Every monotone graph property is testable, SIAM J. Comput., 38, 2, 505-522, (2008) · Zbl 1229.05126
[4] Borgs, C.; Chayes, J.; Lovász, L.; Sós, V. T.; Szegedy, B.; Vesztergombi, K., Graph limits and parameter testing, (Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing - STOC’06, (2006), Association for Computing Machinery (ACM)), 261-270 · Zbl 1301.68199
[5] Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Convergent sequences of dense graphs I: subgraph frequencies, metric properties and testing, Adv. Math., 219, 6, 1801-1851, (2008) · Zbl 1213.05161
[6] Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V.; Vesztergombi, K., Convergent sequences of dense graphs II. multiway cuts and statistical physics, Ann. of Math., 176, 1, 151-219, (2012) · Zbl 1247.05124
[7] Borsuk, K., Drei Sätze über die n-dimensionale euklidische sphäre, Fund. Math., 1, 20, 177-190, (1933) · JFM 59.0560.01
[8] Erdős, P.; Lovász, L.; Spencer, J., Strong independence of graphcopy functions, (Graph Theory and Related Topics, (1979)), 165-172 · Zbl 0462.05057
[9] Glebov, R.; Grzesik, A.; Klimošová, T.; Král’, D., Finitely forcible graphons and permutons, J. Combin. Theory Ser. B, 110, 112-135, (2015) · Zbl 1302.05200
[10] O. Goldreich, S. Goldwasser, D. Ron, Property testing and its connection to learning and approximation, in: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS’96, 1996, pp. 339-348. · Zbl 1065.68575
[11] Goldreich, O.; Trevisan, L., Three theorems regarding testing graph properties, Random Structures Algorithms, 23, 1, 23-57, (2003) · Zbl 1048.68062
[12] Hoppen, C.; Kohayakawa, Y.; Moreira, C. G.; Ráth, B.; Sampaio, R. M., Limits of permutation sequences, J. Combin. Theory Ser. B, 103, 1, 93-113, (2013) · Zbl 1255.05174
[13] Hoppen, C.; Kohayakawa, Y.; Moreira, C. G.; Sampaio, R. M., Property testing and parameter testing for permutations, (Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’10, (2010), Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 66-75 · Zbl 1288.68187
[14] Hoppen, C.; Kohayakawa, Y.; Moreira, C. G.; Sampaio, R. M., Testing permutation properties through subpermutations, Theoret. Comput. Sci., 412, 29, 3555-3567, (2011) · Zbl 1223.68078
[15] C. Hoppen, Y. Kohayakawa, C.G.T. de, A. Moreira, R.M. Sampaio, Limits of permutation sequences through permutation regularity, 2011. arXiv preprint arXiv:1106.1663. · Zbl 1223.68078
[16] Klimošová, T.; Král’, D., Hereditary properties of permutations are strongly testable, (Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’14, (2014), Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 1164-1173 · Zbl 1423.05006
[17] Král’, D.; Pikhurko, O., Quasirandom permutations are characterized by 4-point densities, Geom. Funct. Anal., 23, 2, 570-579, (2013) · Zbl 1268.05006
[18] Lovász, L.; Szegedy, B., Limits of dense graph sequences, J. Combin. Theory Ser. B, 96, 6, 933-957, (2006) · Zbl 1113.05092
[19] Lovász, L.; Szegedy, B., Szemerédi’s lemma for the analyst, Geom. Funct. Anal., 17, 1, 252-270, (2007) · Zbl 1123.46020
[20] Lovász, L.; Szegedy, B., Testing properties of graphs and functions, Israel J. Math., 178, 1, 113-156, (2010) · Zbl 1246.05106
[21] Presutti, C. B.; Stromquist, W., Packing rates of measures and a conjecture for the packing density of 2413, (Permutation Patterns, London Math. Soc. Lecture Note Ser., vol. 376, (2010), Cambridge Univ. Press Cambridge), 287-316 · Zbl 1217.05053
[22] Rödl, V.; Duke, R. A., On graphs with small subgraphs of large chromatic number, Graphs Combin., 1, 1, 91-96, (1985) · Zbl 0581.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.