TY - JOUR AU - Bérczi, Kristóf AU - Borbényi, Márton AU - Lovász, László AU - Tóth, László Márton TI - Cycle matroids of graphings: From convergence to duality JF - JOURNAL OF COMBINATORIAL THEORY SERIES B J2 - J COMB THEORY B VL - 178 PY - 2026 SP - 118 EP - 144 PG - 27 SN - 0095-8956 DO - 10.1016/j.jctb.2025.12.003 UR - https://m2.mtmt.hu/api/publication/36692236 ID - 36692236 LA - English DB - MTMT ER - TY - JOUR AU - Bérczi, Kristóf AU - Borbényi, Márton AU - Lovász, László AU - Tóth, László Márton TI - Quotient-Convergence of Submodular Setfunctions JF - COMBINATORICA J2 - COMBINATORICA VL - 46 PY - 2026 IS - 1 PG - 21 SN - 0209-9683 DO - 10.1007/s00493-026-00199-x UR - https://m2.mtmt.hu/api/publication/36926336 ID - 36926336 LA - English DB - MTMT ER - TY - CHAP AU - Bérczi, Kristóf AU - Gehér, B. AU - Imolay, A. AU - Lovász, László AU - Maga, Balázs AU - Schwarcz, Tamás Bence ED - Koucky, M. ED - Bansal, N. TI - Matroid Products via Submodular Coupling T2 - STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing PB - Association for Computing Machinery (ACM) CY - New York, New York SN - 9798400715105 T3 - Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0737-8017 PY - 2025 SP - 2074 EP - 2085 PG - 12 DO - 10.1145/3717823.3718152 UR - https://m2.mtmt.hu/api/publication/36244915 ID - 36244915 N1 - Eötvös Loránd University, Budapest, Hungary HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary London School of Economics and Political Science, London, United Kingdom Export Date: 14 July 2025; Cited By: 0; Correspondence Address: K. Bérczi; Eötvös Loránd University, Budapest, Hungary; email: kristof.berczi@ttk.elte.hu LA - English DB - MTMT ER - TY - JOUR AU - Keliger, Dániel AU - Lovász, László AU - Móri, Tamás Ferenc AU - Ódor, Gergely TI - Switchover phenomenon for general graphs JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - 108 PY - 2025 IS - 3 SP - 560 EP - 581 PG - 22 SN - 0364-9024 DO - 10.1002/jgt.23184 UR - https://m2.mtmt.hu/api/publication/35467361 ID - 35467361 N1 - Department of Stochastics, Institute of Mathematics, Budapest University of Technology and Economics, Budapest, Hungary HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Network and Data Science, Central European University, Vienna, Austria Export Date: 18 October 2024 CODEN: JGTHD Correspondence Address: Lovász, L.; HUN-REN Alfréd Rényi Institute of MathematicsHungary; email: lovasz@renyi.hu AB - We study SIR-type epidemics (susceptible-infected-resistant) on graphs in two scenarios: (i) when the initial infections start from a well-connected central region and (ii) when initial infections are distributed uniformly. Previously, Ódor et al. demonstrated on a few random graph models that the expectation of the total number of infections undergoes a switchover phenomenon; the central region is more dangerous for small infection rates, while for large rates, the uniform seeding is expected to infect more nodes. We rigorously prove this claim under mild, deterministic assumptions on the underlying graph. If we further assume that the central region has a large enough expansion, the second moment of the degree distribution is bounded and the number of initial infections is comparable to the number of vertices, the difference between the two scenarios is shown to be macroscopic. © 2024 The Author(s). Journal of Graph Theory published by Wiley Periodicals LLC. LA - English DB - MTMT ER - TY - JOUR AU - Kunszenti-Kovács, Dávid AU - Lovász, László AU - Szegedy, Balázs TI - Random homomorphisms into the orthogonality graph JF - JOURNAL OF COMBINATORIAL THEORY SERIES B J2 - J COMB THEORY B VL - 167 PY - 2024 SP - 392 EP - 444 PG - 53 SN - 0095-8956 DO - 10.1016/j.jctb.2024.03.007 UR - https://m2.mtmt.hu/api/publication/33678606 ID - 33678606 AB - Subgraph densities have been defined, and served as basic tools, both in the case of graphons (limits of dense graph sequences) and graphings (limits of bounded-degree graph sequences). While limit objects have been described for the "middle ranges", the notion of subgraph densities in these limit objects remains elusive. We define subgraph densities in the orthogonality graphs on the unit spheres in dimension d, under appropriate sparsity condition on the subgraphs. These orthogonality graphs exhibit the main difficulties of defining subgraphs the "middle" range, and so we expect their study to serve as a key example to defining subgraph densities in more general Markov spaces. The problem can also be formulated as defining and computing random orthogonal representations of graphs. Orthogonal representations have played a role in information theory, optimization, rigidity theory and quantum physics, so to study random ones may be of interest from the point of view of these applications as well. LA - English DB - MTMT ER - TY - JOUR AU - Kunszenti-Kovács, Dávid AU - Lovász, László AU - Szegedy, Balázs TI - Subgraph densities in Markov spaces JF - ADVANCES IN MATHEMATICS J2 - ADV MATH VL - 437 PY - 2024 PG - 74 SN - 0001-8708 DO - 10.1016/j.aim.2023.109414 UR - https://m2.mtmt.hu/api/publication/34479868 ID - 34479868 AB - We generalize subgraph densities, arising in dense graph limit theory, to Markov spaces (symmetric measures on the square of a standard Borel space). More generally, we define an analogue of the set of homomorphisms in the form of a measure on maps of a finite graph into a Markov space. The existence of such homomorphism measures is not always guaranteed, but can be established under rather natural smoothness conditions on the Markov space and sparseness conditions on the graph. This continues a direction in graph limit theory in which such measures are viewed as limits of graph sequences. © 2023 Elsevier Inc. LA - English DB - MTMT ER - TY - JOUR AU - Lovász, László TI - The matroid of a graphing ☆ JF - JOURNAL OF COMBINATORIAL THEORY SERIES B J2 - J COMB THEORY B VL - 169 PY - 2024 SP - 542 EP - 560 PG - 19 SN - 0095-8956 DO - 10.1016/j.jctb.2024.08.001 UR - https://m2.mtmt.hu/api/publication/35283711 ID - 35283711 N1 - Export Date: 12 February 2025 CODEN: JCBTB Funding details: European Research Council, ERC, 810115 Funding text 1: Research supported by ERC Synergy Grant No. 810115. LA - English DB - MTMT ER - TY - JOUR AU - Pósfai, M. AU - Szegedy, Balázs AU - Bačić, I. AU - Blagojević, L. AU - Abért, Miklós AU - Kertész, János AU - Lovász, László AU - Barabási, A.-L. TI - Impact of physicality on network structure JF - NATURE PHYSICS J2 - NAT PHYS VL - 20 PY - 2024 IS - 1 SP - 142 EP - 149 PG - 8 SN - 1745-2473 DO - 10.1038/s41567-023-02267-1 UR - https://m2.mtmt.hu/api/publication/34686162 ID - 34686162 N1 - Department of Network and Data Science, Central European University, Vienna, Austria Alfréd Rényi Institute of Mathematics, Budapest, Hungary Institute of Physics, Belgrade, Serbia Network Science Institute, Northeastern University, Boston, MA, United States Department of Medicine, Brigham and Women’s Hospital, Harvard Medical School, Boston, MA, United States Export Date: 26 February 2024 Correspondence Address: Barabási, A.-L.; Department of Network and Data Science, Austria; email: barabasi@gmail.com Funding details: European Research Council, ERC, 810115-DYNASNET Funding text 1: This research was funded by ERC grant no. 810115-DYNASNET. AB - The emergence of detailed maps of physical networks, such as the brain connectome, vascular networks or composite networks in metamaterials, whose nodes and links are physical entities, has demonstrated the limits of the current network science toolset. Link physicality imposes a non-crossing condition that affects both the evolution and the structure of a network, in a way that the adjacency matrix alone—the starting point of all graph-based approaches—cannot capture. Here, we introduce a meta-graph that helps us to discover an exact mapping between linear physical networks and independent sets, which is a central concept in graph theory. The mapping allows us to analytically derive both the onset of physical effects and the emergence of a jamming transition, and to show that physicality affects the network structure even when the total volume of the links is negligible. Finally, we construct the meta-graphs of several real physical networks, which allows us to predict functional features, such as synapse formation in the brain connectome, that agree with empirical data. Overall, our results show that, to understand the evolution and behaviour of real complex networks, the role of physicality must be fully quantified. © 2023, The Author(s), under exclusive licence to Springer Nature Limited. LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre AU - Hubai, Tamás AU - Lovász, László TI - Locally common graphs JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - 102 PY - 2023 IS - 3 SP - 472 EP - 483 PG - 12 SN - 0364-9024 DO - 10.1002/jgt.22881 UR - https://m2.mtmt.hu/api/publication/33086820 ID - 33086820 N1 - Combinatorics and Applications Research Division, Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Computer Science, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary Export Date: 8 November 2022 CODEN: JGTHD Correspondence Address: Csóka, E.; Combinatorics and Applications Research Division, Hungary; email: csokaendre@gmail.com Funding details: KKP 138270 Funding details: European Research Council, ERC, 810115 Funding text 1: The research was supported by European Research Council Synergy grant No. 810115. Endre Csóka was supported by the NRDI grant KKP 138270. We would like to thank the anonymous referees for their helpful comments. Open Access Funding provided by EISZ ‐ Eotvos Lorand University. AB - Goodman proved that the sum of the number of triangles in a graph on nodes and its complement is at least ; in other words, this sum is minimized, asymptotically, by a random graph with edge density 1/2. Erdős conjectured that a similar inequality will hold for in place of , but this was disproved by Thomason. But an analogous statement does hold for some other graphs, which are called common graphs. Characterization of common graphs seems, however, out of reach. Franek and Rödl proved that is common in a weaker, local sense. Using the language of graph limits, we study two versions of locally common graphs. We sharpen a result of Jagger, Štovíček and Thomason by showing that no graph containing can be locally common, but prove that all such graphs are weakly locally common. We also show that not all connected graphs are weakly locally common. LA - English DB - MTMT ER - TY - JOUR AU - Grzesik, A. AU - Král', D. AU - Lovász, László AU - Volec, J. TI - Cycles of a given length in tournaments JF - JOURNAL OF COMBINATORIAL THEORY SERIES B J2 - J COMB THEORY B VL - 158 PY - 2022 SP - 117 EP - 145 PG - 29 SN - 0095-8956 DO - 10.1016/j.jctb.2022.07.007 UR - https://m2.mtmt.hu/api/publication/33106524 ID - 33106524 N1 - Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, Kraków, 30-348, Poland Faculty of Informatics, Masaryk University, Botanická 68A, Brno, 602 00, Czech Republic Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, United States Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Trojanova 13, Prague, 120 00, Czech Republic Cited By :3 Export Date: 18 January 2024 CODEN: JCBTB Funding details: MUNI/I/1677/2018 Funding details: National Science Foundation, NSF, DMS-1705204 Funding details: European Research Council, ERC Funding details: Horizon 2020, 648509 Funding details: Masarykova Univerzita, MU Funding text 1: The work of the first, second and last authors has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 648509 ). The second and the last were also supported by the MUNI Award in Science and Humanities ( MUNI/I/1677/2018 ) of the Grant Agency of Masaryk University . The work of the third author was supported by NSF Postdoctoral Fellowship Award DMS-1705204 . This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains. Funding text 2: The work of the first, second and last authors has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 648509). The second and the last were also supported by the MUNI Award in Science and Humanities (MUNI/I/1677/2018) of the Grant Agency of Masaryk University. The work of the third author was supported by NSF Postdoctoral Fellowship Award DMS-1705204. This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains. AB - We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let c(l) be the limit of the ratio of the maximum number of cycles of length l in an n-vertex tournament and the expected number of cycles of length l in the random n-vertex tournament, when n tends to infinity. It is well-known that c(3) = 1 and c(4) = 4/3. We show that c(l) = 1 if and only if l is not divisible by four, which settles a conjecture of Bartley and Day. If l is divisible by four, we show that 1 + 2 center dot (2/pi)(l) <= c(l) <= 1 + (2/pi+ o(1))(l) and determine the value c(l) exactly for l = 8. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length l when l is not divisible by four or l is an element of{4, 8}. (c) 2022 Elsevier Inc. All rights reserved. LA - English DB - MTMT ER -