# Sharp Poincar\'e and log-Sobolev inequalities for the switch chain on regular bipartite graphs

@article{Tikhomirov2020SharpPA, title={Sharp Poincar\'e and log-Sobolev inequalities for the switch chain on regular bipartite graphs}, author={Konstantin E. Tikhomirov and Pierre Youssef}, journal={arXiv: Probability}, year={2020} }

Consider the switch chain on the set of $d$-regular bipartite graphs on $n$ vertices with $3\leq d\leq n^{c}$, for a small universal constant $c>0$. We prove that the chain satisfies a Poincare inequality with a constant of order $O(nd)$; moreover, when $d$ is fixed, we establish a log-Sobolev inequality for the chain with a constant of order $O_d(n\log n)$. We show that both results are optimal. The Poincare inequality implies that in the regime $3\leq d\leq n^c$ the mixing time of the switch… Expand

#### Figures from this paper

#### 3 Citations

A triangle process on regular graphs

- Computer Science, Mathematics
- IWOCA
- 2021

It is shown that the triangleswitch chain is, in fact, irreducible on d-regular graphs with n vertices, for all n and d ≥ 3. Expand

Cutoff for Rewiring Dynamics on Perfect Matchings

- Mathematics
- 2021

We establish cutoff for a natural random walk (RW ) on the set of perfect matchings (PMs), based on ‘rewiring’. An n-PM is a pairing of 2n objects. The k-PM RW selects k pairs uniformly at random… Expand

Sampling hypergraphs with given degrees

- Computer Science, Mathematics
- Discret. Math.
- 2021

This work describes and analyzes a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence, and gives some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a constant. Expand

#### References

SHOWING 1-10 OF 61 REFERENCES

Simple Markov-chain algorithms for generating bipartite graphs and tournaments

- Mathematics, Computer Science
- SODA '97
- 1997

A simple Markov chain has one state for every graph (or bipartite graph) with the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. Expand

Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved

- Mathematics, Computer Science
- STOC '88
- 1988

The permanent function arises naturally in a number of fields, including algebra, combinatorial enumeration and the physical sciences, and has been an object of study by mathematicians for many years (see [14] for background). Expand

Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences

- Computer Science, Mathematics
- SODA 2019
- 2018

This work resolves an open problem posed by Greenhill and Sfragara (2017) regarding the switch chain on undirected graphs and relies on a comparison argument with a Markov chain defined by Jerrum and Sinclair for sampling graphs that almost have a given degree sequence. Expand

Subgraphs of random graphs with specified degrees

- Mathematics
- 2011

If a graph is chosen uniformly at random from all the graphs with a given degree sequence, what can be said about its subgraphs? The same can be asked of bipartite graphs, equivalently 0-1 matrices.… Expand

Sampling regular graphs and a peer-to-peer network

- Mathematics, Computer Science
- SODA '05
- 2005

A related Markov chain for d-regular graphs on a varying number of vertices is introduced and it is proved that the related chain has mixing time which is bounded by a polynomial in N, the expected number of Vertices, under reasonable assumptions about the arrival and departure process. Expand

COMPARISON THEOREMS FOR REVERSIBLE MARKOV CHAINS

- Mathematics
- 1993

By symmetry, P has eigenvalues 1 = I03 > I381 > ?> I 31xI- 1 2 -1. This paper develops methods for getting upper and lower bounds on 8i3 by comparison with a second reversible chain on the same state… Expand

The mixing time of switch Markov chains: A unified approach

- Computer Science, Mathematics
- Eur. J. Comb.
- 2022

This paper shows that on any P -stable family of unconstrained/bipartite/directed degree sequences the switch Markov chain is rapidly mixing, and is an almost uniform sampler for power-law and heavy-tailed degree sequences. Expand

Sampling hypergraphs with given degrees

- Computer Science, Mathematics
- Discret. Math.
- 2021

This work describes and analyzes a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence, and gives some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a constant. Expand