Approximate Sampling and Counting of Graphs with Near-P-stable Degree Intervals

Erdős, Péter and Mezei, Tamás Róbert and Miklós, István (2024) Approximate Sampling and Counting of Graphs with Near-P-stable Degree Intervals. ANNALS OF COMBINATORICS. ISSN 0218-0006

Preview

Text s00026-023-00678-8.pdf Available under License Creative Commons Attribution. Download (750kB) | Preview

Abstract

The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, com- puter science, engineering etc. projects. One approach is using Markov chains. The best available current result about the well-studied switch Markov chain is that it is rapidly mixing on P -stable degree sequences (see DOI:10.1016/j.ejc.2021.103421). The switch Markov chain does not change any degree sequence. However, there are cases where degree intervals are specified rather than a single degree sequence. (A natural scenario where this problem arises is in hypothesis testing on social net- works that are only partially observed.) Rechner, Strowick, and M¨uller– Hannemann introduced in 2018 the notion of degree interval Markov chain which uses three (separately well studied) local operations (switch, hinge-flip and toggle), and employing on degree sequence realizations where any two sequences under scrutiny have very small coordinate-wise distance. Recently, Amanatidis and Kleer published a beautiful paper (DOI:10.4230/LIPIcs.STACS.2023.7), showing that the degree interval Markov chain is rapidly mixing if the sequences are coming from a system of very thin intervals which are centered not far from a regular degree se- quence. In this paper, we substantially extend their result, showing that the degree interval Markov chain is rapidly mixing if the intervals are centered at P -stable degree sequences.

Actions (login required)

Edit Item