GPGábor Pete

Gábor Pete

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Gábor Pete has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sparse reconstruction in spin systems II: Ising and other factor of IID measures

    by Pál Galicza, Gábor Pete

    For a sequence of Boolean functions $$f_n : \{-1,1\}^{V_n} \longrightarrow \{-1,1\}$$ f n : { - 1 , 1 } V n ⟶ { - 1 , 1 } , with random input given by some probability measure $$\mathbb {P}_n$$ P n , we say that there is sparse reconstruction for $$f_n$$ f n if there is a sequence of subsets $$U_n \subseteq V_n$$ U n ⊆ V n of coordinates satisfying $$|U_n| = o(|V_n|)$$ | U n | = o ( | V n | ) such that knowing the spins in $$U_n$$ U n gives us a non-vanishing amount of information about the value of $$f_n$$ f n . In the first part of this work, we showed that if the $$\mathbb {P}_n$$ P n s are product measures, then no sparse reconstruction is possible for any sequence of transitive functions. In this sequel, we consider spin systems that are relatives of IID measures in one way or another, with our main focus being on the Ising model on finite transitive graphs or exhaustions of lattices. We prove that no sparse reconstruction is possible for the entire high temperature regime on Euclidean boxes and the Curie-Weiss model, while sparse reconstruction for the majority function of the spins is possible in the critical and low temperature regimes. We give quantitative bounds for two-dimensional boxes and the Curie-Weiss model, sharp in the latter case. The proofs employ several different methods, including factor of IID and FK random cluster representations, strong spatial mixing, a generalization of discrete Fourier analysis to Divide-and-Color models, and entropy inequalities.


  • Open Access

    Author Correction: Physical networks as network-of-networks

    by Gábor Pete, Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, Márton Pósfai

  • Open Access

    Physical networks as network-of-networks

    by Gábor Pete, Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, Márton Pósfai

    Physical networks are made of nodes and links that are physical objects embedded in a geometric space. Understanding how the mutual volume exclusion between these elements affects the structure and function of physical networks calls for a suitable generalization of network theory. Here, we introduce a network-of-networks framework where we describe the shape of each extended physical node as a network embedded in space and these networks are bound together by physical links. Relying on this representation, we introduce a minimal model of network growth and we show for a general class of physical networks that volume exclusion induces heterogeneity in both node volume and degree, with the two becoming correlated. These emergent properties strongly affect the dynamics on physical networks: by calculating their Laplacian spectrum as a function of the coupling strength between the nodes we show that degree-volume correlations suppress the role of hubs as early spreaders in diffusive dynamics. We apply the network-of-networks framework to describe several real systems and find properties analog to the minimal model networks. The prevalence of these properties points towards general growth mechanisms that do not depend on the specifics of the systems.


  • Open Access

    Sparse reconstruction in spin systems. I: iid spins

    by Pál Galicza, Gábor Pete

    For a sequence of Boolean functions $${f_n}:{\{ - 1,1\} ^{{V_n}}} \to \{ - 1,1\} $$ f n : { − 1 , 1 } V n → { − 1 , 1 } , defined on increasing configuration spaces of random inputs, we say that there is sparse reconstruction if there is a sequence of subsets Un ⊆ Vn of the coordinates satisfying ∣Un∣ = o(∣Vn∣) such that knowing the coordinates in Un gives us a non-vanishing amount of information about the value of fn.We first show that, if the underlying measure is a product measure, then no sparse reconstruction is possible for any sequence of transitive functions. We discuss the question in different frameworks, measuring information content in L2 and with entropy. We also highlight some interesting connections with cooperative game theory. Beyond transitive functions, we show that the left-right crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. Some of these results answer questions posed by Itai Benjamini.


  • Open Access

    Stake-governed tug-of-war and the biased infinity Laplacian

    by Alan Hammond, Gábor Pete

    In tug-of-war, two players compete by moving a counter along edges of a graph, each winning the right to move at a given turn according to the flip of a possibly biased coin. The game ends when the counter reaches the boundary, a fixed subset of the vertices, at which point one player pays the other an amount determined by the boundary vertex. Economists and mathematicians have independently studied tug-of-war for many years, focussing respectively on resource-allocation forms of the game, in which players iteratively spend precious budgets in an effort to influence the bias of the coins that determine the turn victors; and on PDE arising in fine mesh limits of the constant-bias game in a Euclidean setting. In this article, we offer a mathematical treatment of a class of tug-of-war games with allocated budgets: each player is initially given a fixed budget which she draws on throughout the game to offer a stake at the start of each turn, and her probability of winning the turn is the ratio of her stake and the sum of the two stakes. We consider the game played on a tree, with boundary being the set of leaves, and the payment function being the indicator of a single distinguished leaf. We find the game value and the essentially unique Nash equilibrium of a leisurely version of the game, in which the move at any given turn is cancelled with constant probability after stakes have been placed. We show that the ratio of the players' remaining budgets is maintained at its initial value $\lambda$; game value is a biased infinity harmonic function; and the proportion of remaining budget that players stake at a given turn is given in terms of the spatial gradient and the $\lambda$-derivative of game value. We also indicate examples in which the solution takes a different form in the non-leisurely game.

  • Open Access

    Finite-energy infinite clusters without anchored expansion

    by Gábor Pete, Ádám Timár

    Hermon and Hutchcroft have recently proved the long-standing conjecture that in Bernoulli(p) bond percolation on any nonamenable transitive graph G, at any p > p_c(G), the probability that the cluster of the origin is finite but has a large volume n decays exponentially in n. A corollary is that all infinite clusters have anchored expansion almost surely. They have asked if these results could hold more generally, for any finite energy ergodic invariant percolation. We give a counterexample, an invariant percolation on the 4-regular tree.

  • Open Access

    Kazhdan groups have cost 1

    by Tom Hutchcroft, Gábor Pete

    We prove that every countably infinite group with Kazhdan’s property (T) has cost 1, answering a well-known question of Gaboriau. It remains open if they have fixed price 1.


  • SPEEDING UP NON-MARKOVIAN FIRST-PASSAGE PERCOLATION WITH A FEW EXTRA EDGES

    by Alexey Medvedev, Gábor Pete

    One model of real-life spreading processes is that of first-passage percolation (also called the SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with independent and identically distributed heavy-tailed passage times on edges. On the other hand, random graphs are often locally tree-like, and spreading on trees with leaves might be very slow due to bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power-law distribution P(xi > t) similar to t(-alpha) with infinite mean. For any finite connected graph G with a root s, we find the largest number of vertices kappa(G , s) that are infected in finite expected time, and prove that for every k <= kappa (G, s), the expected time to infect k vertices is at most O(k(1/alpha)). Then we show that adding a single edge from s to a random vertex in a random tree T typically increases kappa(T , s) from a bounded variable to a fraction of the size of T, thus severely accelerating the process. We examine this acceleration effect on some natural models of random graphs: critical Galton-Watson trees conditioned to be large, uniform spanning trees of the complete graph, and on the largest cluster of near-critical Erdos-Renyi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.