双月刊出版的《组合数学、概率与计算》致力于组合数学、概率论和理论计算机科学三个领域。涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

"Combinatorics Probability and Computing" is a bi-monthly journal dedicated to the fields of combinatorial mathematics, probability theory, and theoretical computer science. The topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods, and random combinatorial structures; combinatorial probabilities and limit theorems of random combinatorial structures; algorithm theory (including complexity theory), randomized algorithms, probabilistic analysis of algorithms, computational learning theory, and optimization.

《Combinatorics Probability and Computing》是一本双月刊，专注于组合数学、概率论和理论计算机科学三个领域。期刊涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

Combinatorics Probability and Computing

Abstract In this paper we consider positional games where the winning sets are edge sets of tree-universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the edges of the complete graph $K_n$ , Maker has a strategy to claim a graph which contains copies of all spanning trees with maximum degree at most $cn/\log (n)$ , for a suitable constant $c$ and $n$ being large enough. We also prove an analogous result for Waiter-Client games. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. Moreover, they improve on a special case of earlier results by Johannsen, Krivelevich, and Samotij as well as Han and Yang for Maker-Breaker games.

Grzegorz Adamski

Sylwia Antoniuk

Małgorzata Bednarska-Bzdȩga

Dennis Clemens

Fabian Hamann

Yannick Mogge

Combinatorics Probability Computing

Tree universality in positional games

位置游戏中的树普遍性

Abstract We prove a new lower bound for the almost 20-year-old problem of determining the smallest possible size of an essential cover of the $n$ -dimensional hypercube $\{\pm 1\}^n$ , that is, the smallest possible size of a collection of hyperplanes that forms a minimal cover of $\{\pm 1\}^n$ and such that, furthermore, every variable appears with a non-zero coefficient in at least one of the hyperplane equations. We show that such an essential cover must consist of at least $10^{-2}\cdot n^{2/3}/(\log n)^{2/3}$ hyperplanes, improving previous lower bounds of Linial–Radhakrishnan, of Yehuda–Yehudayoff, and of Araujo–Balogh–Mattos.

Lisa Sauermann

Zixuan Xu

Essential covers of the hypercube require many hyperplanes

超立方体的基本覆盖需要许多超平面

Abstract We consider the performance of Glauber dynamics for the random cluster model with real parameter $q\gt 1$ and temperature $\beta \gt 0$ . Recent work by Helmuth, Jenssen, and Perkins detailed the ordered/disordered transition of the model on random $\Delta$ -regular graphs for all sufficiently large $q$ and obtained an efficient sampling algorithm for all temperatures $\beta$ using cluster expansion methods. Despite this major progress, the performance of natural Markov chains, including Glauber dynamics, is not yet well understood on the random regular graph, partly because of the non-local nature of the model (especially at low temperatures) and partly because of severe bottleneck phenomena that emerge in a window around the ordered/disordered transition. Nevertheless, it is widely conjectured that the bottleneck phenomena that impede mixing from worst-case starting configurations can be avoided by initialising the chain more judiciously. Our main result establishes this conjecture for all sufficiently large $q$ (with respect to $\Delta$ ). Specifically, we consider the mixing time of Glauber dynamics initialised from the two extreme configurations, the all-in and all-out, and obtain a pair of fast mixing bounds which cover all temperatures $\beta$ , including in particular the bottleneck window. Our result is inspired by the recent approach of Gheissari and Sinclair for the Ising model who obtained a similar flavoured mixing-time bound on the random regular graph for sufficiently low temperatures. To cover all temperatures in the RC model, we refine appropriately the structural results of Helmuth, Jenssen and Perkins about the ordered/disordered transition and show spatial mixing properties ‘within the phase’, which are then related to the evolution of the chain.

Andreas Galanis

Leslie Ann Goldberg

Paulina Smolarova

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics

通过Glauber动力学在所有温度下从随机正则图上的随机团模型中采样

Abstract We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ for any fixed integer $d \geq 2$ and that almost all $d$ -regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdős–Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim, and Oum.

Kevin Hendrey

Sergey Norin

Raphael Steiner

Jérémie Turcotte

Twin-width of sparse random graphs

稀疏随机图的双宽度

Abstract Let $T$ be a tree on $t$ vertices. We prove that for every positive integer $k$ and every graph $G$ , either $G$ contains $k$ pairwise vertex-disjoint subgraphs each having a $T$ minor, or there exists a set $X$ of at most $t(k-1)$ vertices of $G$ such that $G-X$ has no $T$ minor. The bound on the size of $X$ is best possible and improves on an earlier $f(t)k$ bound proved by Fiorini, Joret, and Wood (2013) with some fast-growing function $f(t)$ . Moreover, our proof is short and simple.

Abbreviation	Combinator. Probab. Comp.
Journal Impact	0.92
Quartiles(Global)	STATISTICS & PROBABILITY(Q3)

ISSN	0963-5483, 1469-2163
h-index	56

Publication Information	Publisher: Cambridge University Press，Publishing cycle: Bimonthly，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 1992，Proportion of original research papers: 100.00%，Self Citation Rate:11.10%， Gold OA Rate: 35.23%
Average review cycle	网友分享经验：较慢,6-12周
Average recruitment ratio	网友分享经验：容易

Combinatorics Probability and Computing

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

Tree universality in positional games

Essential covers of the hypercube require many hyperplanes

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics

Twin-width of sparse random graphs

Tight bound for the Erdős–Pósa property of tree minors

Essential covers of the hypercube require many hyperplanes

Tree universality in positional games

Twin-width of sparse random graphs

Tight bound for the Erdős–Pósa property of tree minors

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics