BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Justin Salez

Justin Salez appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.CODiscrete Mathematicscond-mat.dis-nncond-mat.softcond-mat.stat-mechmath-phmath.DGmath.FAmath.MPphysics.flu-dyn

Catalog footprint

What is connected

19works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2022arXiv

Mixing time and expansion of non-negatively curved Markov chains

We establish three remarkable consequences of non-negative curvature for sparse Markov chains. First, their conductance decreases logarithmically with the number of states. Second, their displacement is at least diffusive until the mixing time. Third, they never exhibit the cutoff phenomenon. The first result provides a nearly sharp quantitative answer to a classical question of Ollivier, Milman and Naor. The second settles a conjecture of Lee and Peres for graphs with non-negative curvature. The third offers a striking counterpoint to the recently established cutoff for non-negatively curved chains with uniform expansion.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Separation cutoff for Activated Random Walks

We consider Activated Random Walks on arbitrary finite networks, with particles being inserted at random and absorbed at the boundary. Despite the non-reversibility of the dynamics and the lack of knowledge on the stationary distribution, we explicitly determine the relaxation time of the process, and prove that separation cutoff is equivalent to the product condition. We also provide sharp estimates on the center and width of the cutoff window. Finally, we illustrate those results by establishing explicit separation cutoffs on various networks, including: (i) large finite subgraphs of any fixed infinite non-amenable graph, with absorption at the boundary and (ii) large finite vertex-transitive graphs with absorption at a single vertex. The latter result settles a conjecture of Levine and Liang. Our proofs rely on the refined analysis of a strong stationary time recently discovered by Levine and Liang and involving the IDLA process.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Universality of cutoff for exclusion with reservoirs

We consider the reversible exclusion process with reservoirs on arbitrary networks. We characterize the spectral gap, mixing time, and mixing window of the process, in terms of certain simple statistics of the underlying network. Among other consequences, we establish a non-conservative analogue of Aldous's spectral gap conjecture, and we show that cutoff occurs if and only if the product condition is satisfied. We illustrate this by providing explicit cutoffs on discrete lattices of arbitrary dimensions and boundary conditions, which substantially generalize recent one-dimensional results. We also obtain cutoff phenomena in relative entropy, Hilbert norm, separation distance and supremum norm. Our proof exploits negative dependence in a novel, simple way to reduce the understanding of the whole process to that of single-site marginals. We believe that this approach will find other applications.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Cutoff for non-negatively curved Markov chains

Discovered in the context of card shuffling by Aldous, Diaconis and Shahshahani, the cutoff phenomenon has since then been established in a variety of Markov chains. However, proving cutoff remains a delicate affair, which requires a detailed knowledge of the chain. Identifying the general mechanisms underlying this phase transition -- without having to pinpoint its precise location -- remains one of the most fundamental open problems in the area of mixing times. In the present paper, we make a step in this direction by establishing cutoff for Markov chains with non-negative curvature, under a suitably refined product condition. The result applies, in particular, to random walks on abelian Cayley expanders satisfying a mild degree condition, hence in particular to \emph{almost all} abelian Cayley graphs. Our proof relies on a quantitative \emph{entropic concentration principle}, which we believe to lie behind all cutoff phenomena.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Sparse expanders have negative curvature

We prove that bounded-degree expanders with non-negative Ollivier-Ricci curvature do not exist, thereby solving a long-standing open problem suggested by Naor and Milman and publicized by Ollivier (2010). In fact, this remains true even if we allow for a vanishing proportion of large degrees, large eigenvalues, and negatively-curved edges. To establish this, we work directly at the level of Benjamini-Schramm limits, and exploit the entropic characterization of the Liouville property on stationary random graphs to show that non-negative curvature and spectral expansion are incompatible "at infinity". We then transfer this result to finite graphs via local weak convergence. The same approach also applies to the Bacry-Emery curvature condition CD$(0,\infty)$, thereby settling a recent conjecture of Cushing, Liu and Peyerimhoff (2019).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The interchange process on high-dimensional products

We resolve a long-standing conjecture of Wilson (2004), reiterated by Oliveira (2016), asserting that the mixing-time of the unit-rate Interchange Process on the $n$-dimensional hypercube is of order $n$. This follows from a sharp inequality established at the level of Dirichlet forms, from which we also deduce that macroscopic cycles emerge in constant time, and that the log-Sobolev constant of the exclusion process is of order $1$. Beyond the hypercube, our results apply to cartesian products of arbitrary graphs of fixed size, shedding light on a broad conjecture of Oliveira (2013).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A sharp log-Sobolev inequality for the multislice

We determine the log-Sobolev constant of the multi-urn Bernoulli-Laplace diffusion model with arbitrary parameters, up to a small universal multiplicative constant. Our result extends a classical estimate of Lee and Yau (1998) and confirms a conjecture of Filmus, O'Donnell and Wu (2018). Among other applications, we completely quantify the "small-set expansion" phenomenon on the multislice, and obtain sharp mixing-time estimates for the colored exclusion process on various graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Modified log-Sobolev inequalities for strong-Rayleigh measures

We establish universal modified log-Sobolev inequalities for reversible Markov chains on the boolean lattice $\{0,1\}^n$, under the only assumption that the invariant law $π$ satisfies a form of negative dependence known as the stochastic covering property. This condition is strictly weaker than the strong Rayleigh property, and is satisfied in particular by all determinantal measures, as well as any product measure over the set of bases of a balanced matroid. In the special case where $π$ is $k-$homogeneous, our results imply the celebrated concentration inequality for Lipschitz functions due to Pemantle & Peres (2014). As another application, we deduce that the natural Monte-Carlo Markov Chain used to sample from $π$ has mixing time at most $kn\log\log\frac{1}{π(x)}$ when initialized in state $x$. To the best of our knowledge, this is the first work relating negative dependence and modified log-Sobolev inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spectral atoms of unimodular random trees

We use the Mass Transport Principle to analyze the local recursion governing the resolvent $(A-z)^{-1}$ of the adjacency operator of unimodular random trees. In the limit where the complex parameter $z$ approaches a given location $λ$ on the real axis, we show that this recursion induces a decomposition of the tree into finite blocks whose geometry directly determines the spectral mass at $λ$. We then exploit this correspondence to obtain precise information on the pure-point support of the spectrum, in terms of expansion properties of the tree. In particular, we deduce that the pure-point support of the spectrum of any unimodular random tree with minimum degree $δ\ge 3$ and maximum degree $Δ$ is restricted to finitely many points, namely the eigenvalues of trees of size less than $\frac{Δ-2}{δ-2}$. More generally, we show that the restriction $δ\ge 3$ can be weakened to $δ\ge 2$, as long as the anchored isoperimetric constant of the tree remains bounded away from $0$. This applies in particular to any unimodular Galton-Watson tree without leaves, allowing us to settle a conjecture of Bordenave, Sen and Virág (2013).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The densest subgraph problem in sparse random graphs

We determine the asymptotic behavior of the maximum subgraph density of large random graphs with a prescribed degree sequence. The result applies in particular to the Erdős-Rényi model, where it settles a conjecture of Hajek [IEEE Trans. Inform. Theory 36 (1990) 1398-1414]. Our proof consists in extending the notion of balanced loads from finite graphs to their local weak limits, using unimodularity. This is a new illustration of the objective method described by Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Weighted sampling without replacement

Comparing concentration properties of uniform sampling with and without replacement has a long history which can be traced back to the pioneer work of Hoeffding (1963). The goal of this short note is to extend this comparison to the case of non-uniform weights, using a coupling between the two samples. When the items' weights are arranged in the same order as their values, we show that the induced coupling for the cumulative values is a submartingale coupling. As a consequence, the powerful Chernoff-type upper-tail estimates known for sampling with replacement automatically transfer to the case of sampling without replacement. For general weights, we use the same coupling to establish a sub-Gaussian concentration inequality. We also construct another martingale coupling which allows us to answer a question raised by Luh and Pippenger (2014) on sampling in Polya urns with different replacement numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cooperative Strings and Glassy Interfaces

We introduce a minimal theory of glass formation based on the ideas of molecular crowding and resultant string-like cooperative rearrangement, and address the effects of free interfaces. In the bulk case, we obtain a scaling expression for the number of particles taking part in cooperative strings, and we recover the Adam-Gibbs description of glassy dynamics. Then, by including thermal dilatation, the Vogel-Fulcher-Tammann relation is derived. Moreover, the random and string-like characters of the cooperative rearrangement allow us to predict a temperature-dependent expression for the cooperative length $ξ$ of bulk relaxation. Finally, we explore the influence of sample boundaries when the system size becomes comparable to $ξ$. The theory is in agreement with measurements of the glass-transition temperature of thin polymer films, and allows to quantify the temperature-dependent thickness $h_{\textrm{m}}$ of the interfacial mobile layer.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cutoff for non-backtracking random walks on sparse random graphs

A finite ergodic Markov chain is said to exhibit cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Discovered in the context of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now believed to be rather typical among fast mixing Markov chains. Yet, establishing it rigorously often requires a challengingly detailed understanding of the underlying chain. Here we consider non-backtracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window, and prove that the (suitably rescaled) cutoff profile approaches a remarkably simple, universal shape.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Every totally real algebraic integer is a tree eigenvalue

Graph eigenvalues are examples of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients. Conversely, the fact that every totally real algebraic integer occurs as an eigenvalue of some finite graph is a deep result, conjectured forty years ago by Hoffman, and proved seventeen years later by Estes. This short paper provides an independent and elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree. As a by-product, our result implies that the atoms of the limiting spectrum of $n\times n$ symmetric matrices with independent Bernoulli$\,\left(\frac{c}{n}\right)$ entries ($c>0$ is fixed as $n\to\infty$) are exactly the totally real algebraic integers. This settles an open problem raised by Ben Arous (2010).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Compulsive Gambler Process

In the compulsive gambler process there is a finite set of agents who meet pairwise at random times ($i$ and $j$ meet at times of a rate-$ν_{ij}$ Poisson process) and, upon meeting, play an instantaneous fair game in which one wins the other's money. We introduce this process and describe some of its basic properties. Some properties are rather obvious (martingale structure; comparison with Kingman coalescent) while others are more subtle (an "exchangeable over the money elements" property, and a construction reminiscent of the Donnelly-Kurtz look-down construction). Several directions for possible future research are described. One -- where agents meet neighbors in a sparse graph -- is studied here, and another -- a continuous-space extension called the {\em metric coalescent} -- is studied in Lanoue (2014).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Mezard-Parisi equation for matchings in pseudo-dimension d>1

We establish existence and uniqueness of the solution to the cavity equation for the random assignment problem in pseudo-dimension $d>1$, as conjectured by Aldous and Bandyopadhyay (Annals of Applied Probability, 2005) and Wästlund (Annals of Mathematics, 2012). This fills the last remaining gap in the proof of the original Mézard-Parisi prediction for this problem (Journal de Physique Lettres, 1985).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Matchings on infinite graphs

Elek and Lippner (2010) showed that the convergence of a sequence of bounded-degree graphs implies the existence of a limit for the proportion of vertices covered by a maximum matching. We provide a characterization of the limiting parameter via a local recursion defined directly on the limit of the graph sequence. Interestingly, the recursion may admit multiple solutions, implying non-trivial long-range dependencies between the covered vertices. We overcome this lack of correlation decay by introducing a perturbative parameter (temperature), which we let progressively go to zero. This allows us to uniquely identify the correct solution. In the important case where the graph limit is a unimodular Galton-Watson tree, the recursion simplifies into a distributional equation that can be solved explicitly, leading to a new asymptotic formula that considerably extends the well-known one by Karp and Sipser for Erdös-Rényi random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The cavity method for counting spanning subgraphs subject to local constraints

Using the theory of negative association for measures and the notion of random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree-like graphs. Specifically, the corresponding free entropy density is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton-Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitely. As an illustration, we provide an explicit-limit formula for the $b-$matching number of an Erdős-Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb N$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The rank of diluted random graphs

We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs $(G_n)_{n\geq0}$ converging locally to a Galton--Watson tree $T$ (GWT), we provide an explicit formula for the asymptotic multiplicity of the eigenvalue 0 in terms of the degree generating function $ϕ_*$ of $T$. In the first part, we show that the adjacency operator associated with $T$ is always self-adjoint; we analyze the associated spectral measure at the root and characterize the distribution of its atomic mass at 0. In the second part, we establish a sufficient condition on $ϕ_*$ for the expectation of this atomic mass to be precisely the normalized limit of the dimension of the kernel of the adjacency matrices of $(G_n)_{n\geq 0}$. Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.

0 citations0 reviewsNo code linkedOpen access