TY - JOUR AU - Li, X. AU - Szegedy, Balázs TI - On the logarithmic calculus and Sidorenko's conjecture JF - ACTA MATHEMATICA HUNGARICA J2 - ACTA MATH HUNG VL - Accepted: 2025 PY - 2026 SP - & SN - 0236-5294 DO - 10.1007/s10474-026-01582-2 UR - https://m2.mtmt.hu/api/publication/37075955 ID - 37075955 AB - We study a type of calculus for proving inequalities between subgraph densities that is based on Jensen's inequality for the logarithmic function.As a demonstration of the method we verify the conjecture of Erdös-Simonovits and Sidorenko for various families of graphs.In particular we give a short analytic proof for a result by Conlon, Fox and Sudakov. Using this, we prove the forcing conjecture for bipartite graphs in which one vertex is complete to the other side. LA - English DB - MTMT ER - TY - JOUR AU - Benczúr, András, ifj AU - Gyimóthy, Tibor AU - Szegedy, Balázs TI - Mesterséges intelligencia témájú kutatások Magyarországon JF - MAGYAR TUDOMÁNY J2 - MAGYAR TUDOMÁNY VL - 186 PY - 2025 IS - 4 SP - 663 EP - 675 PG - 13 SN - 0025-0325 DO - 10.1556/2065.186.2025.4.7 UR - https://m2.mtmt.hu/api/publication/36103030 ID - 36103030 LA - Hungarian DB - MTMT ER - TY - JOUR AU - Bonamassa, Ivan AU - Ráth, Balázs AU - Pósfai, Márton AU - Abért, Miklós AU - Keliger, Dániel AU - Szegedy, Balázs AU - Kertész, János AU - Lovász, László AU - Barabási, Albert-László TI - Logarithmic kinetics and bundling in random packings of elongated 3D physical links JF - PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA J2 - P NATL ACAD SCI USA VL - 122 PY - 2025 IS - 32 SN - 0027-8424 DO - 10.1073/pnas.2427145122 UR - https://m2.mtmt.hu/api/publication/36294977 ID - 36294977 N1 - This research was funded by ERC grant No. 810115-DYNASNET. B.R. acknowledges partial funds from NKFI-FK-142124 of NKFI (National Research, Development and Innovation Office). AB - We explore the impact of excluded volume interactions on the local assembly of linear physical networks, where nodes are spheres and links are rigid cylinders with varying length. To focus on the effect of elongated links, we introduce a minimal 3D model that helps us zoom into confined regions of these networks whose distant parts are sequentially connected by the random deposition of physical links with a very large aspect ratio. We show that the nonequilibrium kinetics at which these elongated links, or spaghetti, adhere to the available volume without mutual crossings is logarithmic in time, as opposed to the algebraic growth in lower dimensions for needle-like packings. We attribute this qualitatively different behavior to a delay in the activation of depletion forces caused by the 3D nature of the problem. Equally important, we find that this slow kinetics is metastable, allowing us to analytically predict the kinetic scaling characterizing an algebraic growth due to the nucleation of local bundles. Our findings offer a theoretical benchmark to study the local assembly of physical networks, with implications for the modeling of nest-like packings far from equilibrium. LA - English DB - MTMT ER - TY - JOUR AU - Candela, Pablo AU - Gonzalez Sanchez, Diego AU - Szegedy, Balázs TI - On measure-preserving \mathbb{F}_{p}^{\omega}-systems of order k JF - JOURNAL D ANALYSE MATHEMATIQUE J2 - J ANAL MATH VL - Published: 13 July 2025 PY - 2025 SP - & SN - 0021-7670 DO - 10.1007/s11854-025-0381-4 UR - https://m2.mtmt.hu/api/publication/36318073 ID - 36318073 AB - Building on previous work in the nilspace-theoretic approach to the study of Host–Kra factors of measure-preserving systems, we prove that every ergodic \mathbb{F}_{p}^{\omega} F p ω -system of order k is a factor of an Abramov \mathbb{F}_{p}^{\omega} F p ω -system of order k . This answers a question of Jamneshan, Shalom and Tao. LA - English DB - MTMT ER - TY - CONF AU - Candela, P. AU - Gonzalez Sanchez, Diego AU - Szegedy, Balázs TI - Higher-order Fourier analysis via spectral algorithms T2 - Proceedings of the 13th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'25 PY - 2025 SP - & UR - https://m2.mtmt.hu/api/publication/36436058 ID - 36436058 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 - 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 - GEN AU - Pablo, Candela AU - Gonzalez Sanchez, Diego AU - Szegedy, Balázs TI - On measure-preserving Fωp-systems of order k PY - 2024 PG - 15 UR - https://m2.mtmt.hu/api/publication/34760336 ID - 34760336 AB - Building on previous work in the nilspace-theoretic approach to the study of Host-Kra factors of measure-preserving systems, we prove that every ergodic Fωp-system of order k is a factor of an Abramov Fωp-system of order k. This answers a question of Jamneshan, Shalom and Tao. LA - English DB - MTMT ER - TY - GEN AU - Pablo, Candela AU - Gonzalez Sanchez, Diego AU - Szegedy, Balázs TI - On Fω2-affine-exchangeable probability measures PY - 2024 PG - 62 UR - https://m2.mtmt.hu/api/publication/35447049 ID - 35447049 AB - For any standard Borel space B, let P(B) denote the space of Borel probability measures on B. In relation to a difficult problem of Aldous in exchangeability theory, and in connection with arithmetic combinatorics, Austin raised the question of describing the structure of affine-exchangeable probability measures on product spaces indexed by the vector space Fω2, i.e., the measures in P(BFω2) that are invariant under the coordinate permutations on BFω2 induced by all affine automorphisms of Fω2. We answer this question by describing the extreme points of the space of such affine-exchangeable measures. We prove that there is a single structure underlying every such measure, namely, a random infinite-dimensional cube (sampled using Haar measure adapted to a specific filtration) on a group that is a countable power of the 2-adic integers. Indeed, every extreme affine-exchangeable measure in P(BFω2) is obtained from a P(B)-valued function on this group, by a vertex-wise composition with this random cube. The consequences of this result include a description of the convex set of affine-exchangeable measures in P(BFω2) equipped with the vague topology (when B is a compact metric space), showing that this convex set is a Bauer simplex. We also obtain a correspondence between affine-exchangeability and limits of convergent sequences of (compact-metric-space valued) functions on vector spaces Fn2 as n→∞. Via this correspondence, we establish the above-mentioned group as a general limit domain valid for any such sequence. LA - English DB - MTMT ER -