{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T16:02:51Z","timestamp":1774454571567,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:00:00Z","timestamp":1741910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:00:00Z","timestamp":1741910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007397","name":"Charles University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Ne\u0161et\u0159il and Ossona de Mendez recently proposed a new definition of graph convergence called structural convergence. The structural convergence framework is based on the probability of satisfaction of logical formulas from a fixed fragment of first-order formulas. The flexibility of choosing the fragment allows to unify the classical notions of convergence for sparse and dense graphs. Since the field is relatively young, the range of examples of convergent sequences is limited and only a few methods of construction are known. Our aim is to extend the variety of constructions by considering the gadget construction. We show that, when restricting to the set of sentences, the application of gadget construction on elementarily convergent sequences yields an elementarily convergent sequence. On the other hand, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. We give several different sufficient conditions to ensure the full convergence. One of them states that the resulting sequence is first-order convergent if the replaced edges are dense in the original sequence of structures.<\/jats:p>","DOI":"10.1007\/s00493-025-00140-8","type":"journal-article","created":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T12:16:20Z","timestamp":1741954580000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Gadget Construction and Structural Convergence"],"prefix":"10.1007","volume":"45","author":[{"given":"David","family":"Hartman","sequence":"first","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Hons","sequence":"additional","affiliation":[]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,14]]},"reference":[{"key":"140_CR1","doi-asserted-by":"publisher","DOI":"10.1214\/ejp.v6-96","author":"Itai Benjamini","year":"2001","unstructured":"Benjamini, Itai, Schramm, Oded: Recurrence of distributional limits of finite planar graphs. Electron. J. Prob. (2001). https:\/\/doi.org\/10.1214\/ejp.v6-96","journal-title":"Electron. J. Prob."},{"key":"140_CR2","doi-asserted-by":"publisher","unstructured":"Borgs, Christian, Chayes, Jennifer, Lov\u00e1sz, L\u00e1szl\u00f3, S\u00f3s, Vera T., Vesztergombi, Katalin: Counting Graph Homomorphisms. In: Topics in Discrete Mathematics: Dedicated to Jarik Ne \u0161 et \u0159 il on the Occasion of his 60th Birthday. Springer, pp. 315\u2013371 (2006). https:\/\/doi.org\/10.1007\/3-540-33700-8_18","DOI":"10.1007\/3-540-33700-8_18"},{"key":"140_CR3","unstructured":"Chang, Chen C., Keisler, Howard J.: Model Theory. Elsevier Science & Technology Books, p. 649 (1990). ISBN: 9780080880075"},{"issue":"2","key":"140_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"Andrzej Ehrenfeucht","year":"1961","unstructured":"Ehrenfeucht, Andrzej: An application of games to the completeness problem for formalized theories. Fundam. Math. 49(2), 129\u2013141 (1961)","journal-title":"Fundam. Math."},{"issue":"4","key":"140_CR5","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s00493-007-2214-8","volume":"27","author":"G\u00e1bor Elek","year":"2007","unstructured":"Elek, G\u00e1bor.: Note on limits of finite graphs. Combinatorica 27(4), 503\u2013507 (2007). https:\/\/doi.org\/10.1007\/s00493-007-2214-8","journal-title":"Combinatorica"},{"issue":"6","key":"140_CR6","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/s00493-021-4445-5","volume":"42","author":"G\u00e1bor Elek","year":"2021","unstructured":"Elek, G\u00e1bor., Tardos, G\u00e1bor.: Convergence and limits of finite trees. Combinatorica 42(6), 821\u2013852 (2021). https:\/\/doi.org\/10.1007\/s00493-021-4445-5","journal-title":"Combinatorica"},{"key":"140_CR7","doi-asserted-by":"publisher","unstructured":"Feder, Tom\u00e1s, Vardi, Moshe Y.: Monotone monadic SNP and constraint satisfaction. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC \u201993. ACM Press (1993). https:\/\/doi.org\/10.1145\/167088.167245","DOI":"10.1145\/167088.167245"},{"key":"140_CR8","unstructured":"Fra\u00efss\u00e9, Roland: Sur quelques classifications des syst \u00e8 mes de relations. Th\u00e8ses pr\u00e9sent\u00e9es \u00e0 la Facult\u00e9 des Sciences de l\u2019Universit\u00e9 de Paris. impr. Durand (1955)"},{"key":"140_CR9","unstructured":"Frucht, Robert: Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Mathematica 6, 239\u2013250 (1939). http:\/\/www.numdam.org\/item\/CM_1939__6__239_0\/"},{"key":"140_CR10","doi-asserted-by":"publisher","unstructured":"Gaifman, Haim: On local and non-local properties. In: Proceedings of the Herbrand Symposium. Elsevier, pp. 105\u2013135 (1982). https:\/\/doi.org\/10.1016\/s0049-237x(08)71879-2","DOI":"10.1016\/s0049-237x(08)71879-2"},{"key":"140_CR11","unstructured":"Garey, Michael R., Johnson, David S.: Computers and intractability. a guide to the theory of NP-completeness. W. H. Freeman, p. 338 (1990). ISBN: 0716710455"},{"key":"140_CR12","doi-asserted-by":"publisher","unstructured":"Hartman, David, Hons, Tom\u00e1\u0161, Ne\u0161et\u0159il, Jaroslav: Rooting algebraic vertices of convergent sequences. In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. Masaryk University Press (2023). https:\/\/doi.org\/10.5817\/cz.muni.eurocomb23-075","DOI":"10.5817\/cz.muni.eurocomb23-075"},{"key":"140_CR13","doi-asserted-by":"publisher","unstructured":"Hartman, David, Hons, Tom\u00e1\u0161, Ne\u0161et\u0159il, Jaroslav: Structural convergence and algebraic roots. Combinatorics, Probability and Computing, pp. 1\u20139 (2024). ISSN: 1469-2163. https:\/\/doi.org\/10.1017\/s0963548324000427","DOI":"10.1017\/s0963548324000427"},{"issue":"4","key":"140_CR14","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/bf01297617","volume":"69","author":"Zden\u011bk Hedrl\u00edn","year":"1965","unstructured":"Hedrl\u00edn, Zden\u011bk, Pultr, Ale\u0161: Symmetric relations (undirected graphs) with given semigroups. Monatshefte f \u00fc r Mathematik 69(4), 318\u2013322 (1965). https:\/\/doi.org\/10.1007\/bf01297617","journal-title":"Monatshefte f \u00fc r Mathematik"},{"key":"140_CR15","doi-asserted-by":"publisher","unstructured":"Hell, Pavol, Ne\u0161et\u0159il, Jaroslav: Graphs and Homomorphisms. Oxford University Press. (2004). https:\/\/doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"140_CR16","first-page":"310","volume-title":"A Shorter Model Theory","author":"Wilfrid Hodges","year":"1997","unstructured":"Hodges, Wilfrid: A Shorter Model Theory, p. 310. Cambridge University Press (1997). (ISBN: 0521587131)"},{"key":"140_CR17","unstructured":"Hons, Tom\u00e1\u0161: Using gadget construction in structural convergence. MA thesis. Charles University, Faculty of Mathematics and Physics, Computer Science Institute (2023)"},{"issue":"1","key":"140_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s11083-005-9005-x","volume":"22","author":"Jan Hubi\u010dka","year":"2005","unstructured":"Hubi\u010dka, Jan, Ne\u0161et\u0159il, Jaroslav: Finite Paths are Universal. Order 22(1), 21\u201340 (2005). https:\/\/doi.org\/10.1007\/s11083-005-9005-x","journal-title":"Order"},{"key":"140_CR19","doi-asserted-by":"crossref","unstructured":"\u0141o\u015b, Jerzy: Quelques remarques, th\u00e9or\u00e8mes et probl\u00e8mes sur les classes d\u00e9finissables d\u2019alg\u00e8bres. Mathematical interpretation of formal systems (1955)","DOI":"10.1016\/S0049-237X(09)70306-4"},{"key":"140_CR20","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L\u00e1szl\u00f3: Large networks and graph limits. American Mathematical Society (2012). ISBN: 9780821890851","DOI":"10.1090\/coll\/060"},{"issue":"6","key":"140_CR21","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1016\/j.jctb.2006.05.002","volume":"96","author":"L\u00e1szl\u00f3 Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L\u00e1szl\u00f3., Szegedy, Bal\u00e1zs: Limits of dense graph sequences. J. Combin. Theory Ser. B 96(6), 933\u2013957 (2006). https:\/\/doi.org\/10.1016\/j.jctb.2006.05.002","journal-title":"J. Combin. Theory Ser. B"},{"key":"140_CR22","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, Jaroslav, de Mendez, Patrice Ossona: A unified approach to structural limits and limits of graphs with bounded tree-depth. Memoirs Am. Math. Soc. (2020). https:\/\/doi.org\/10.1090\/memo\/1272","DOI":"10.1090\/memo\/1272"},{"issue":"4","key":"140_CR23","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1002\/rsa.20719","volume":"51","author":"Jaroslav Ne\u0161et\u0159il","year":"2017","unstructured":"Ne\u0161et\u0159il, Jaroslav, de Mendez, Patrice Ossona: Cluster analysis of local convergent sequences of structures. Random Struct. Algorithms 51(4), 674\u2013728 (2017). https:\/\/doi.org\/10.1002\/rsa.20719","journal-title":"Random Struct. Algorithms"},{"key":"140_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.37236\/5628","volume":"23","author":"Jaroslav Ne\u0161et\u0159il","year":"2016","unstructured":"Ne\u0161et\u0159il, Jaroslav, de Mendez, Patrice Ossona: Modeling limits in hereditary classes: reduction and application to trees. Electron. J. Comb. 23, 2 (2016). https:\/\/doi.org\/10.37236\/5628","journal-title":"Electron. J. Comb."},{"issue":"8","key":"140_CR25","doi-asserted-by":"publisher","first-page":"1899","DOI":"10.1016\/j.jpaa.2016.09.006","volume":"221","author":"Jaroslav Ne\u0161et\u0159il","year":"2017","unstructured":"Ne\u0161et\u0159il, Jaroslav, de Mendez, Patrice Ossona: Towards a characterization of universal categories. J. Pure Appl. Algebra 221(8), 1899\u20131905 (2017). https:\/\/doi.org\/10.1016\/j.jpaa.2016.09.006","journal-title":"J. Pure Appl. Algebra"},{"key":"140_CR26","unstructured":"Pultr, Ale\u0161, Trnkov\u00e1, V\u011bra: Combinatorial, algebraic, and topological representations of groups, semigroups, and categories. North-Holland Pub. Co., p. 372 (1980). ISBN: 044485083X"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00140-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00140-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00140-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:13:43Z","timestamp":1746522823000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00140-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,14]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["140"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00140-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,14]]},"assertion":[{"value":"6 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}