Pith. sign in

REVIEW

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1712.01709 v2 pith:OCM3A3HN submitted 2017-12-04 math.CO

Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences

classification math.CO
keywords degreesequencesresultsdirectedbipartitemarkovmixingregular
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. Several results were proved on rapidly mixing Markov chains on regular simple, on regular directed, on half-regular directed and on half-regular bipartite degree sequences. In this paper, the main result is the following: Let $U$ and $V$ be disjoint finite sets, and let $0 < c_1 \le c_2 < |U|$ and $0 < d_1 \le d_2 < |V|$ be integers. Furthermore, assume that the bipartite degree sequence on $U \cup V$ satisfies $c_1 \le d(v) \le c_2\ : \ \forall v\in V$ and $d_1 \le d(u) \le d_2 \ : \ \forall u\in U$. Finally assume that $(c_2-c_1 -1)(d_2 -d_1 -1) < 1 + \max \{c_1(|V| -d_2), d_1(|V|- c_2) \}$. Then the swap Markov chain on this bipartite degree sequence is rapidly mixing. The technique applies on directed degree sequences as well, with very similar parameter values. These results are germane to the recent results of Greenhill and Sfragara about fast mixing MCMC processes on simple and directed degree sequences, where the maximum degrees are $O(\sqrt{\# \mbox{ of edges}})$. The results are somewhat comparable on directed degree sequences: while the GS results are better applicable for degree sequences developed under some scale-free random process, our new results are better fitted to degree sequences developed under the Erd\H{o}s -- R\'enyi model. For example our results cover all regular degree sequences, the GS model is not applicable when the average degree is $ > n/16.$

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.