In this paper we develop an in-depth analysis of non-reversible Markov chains on denumerable state space from a similarity orbit perspective. In particular, we study the class of Markov chains whose transition kernel is in the similarity orbit of a normal transition kernel, such as that of birth–death chains or reversible Markov chains. We start by identifying a set of sufficient conditions for a Markov chain to belong to the similarity orbit of a birth–death chain. As by-products, we obtain a spectral representation in terms of non-self-adjoint resolutions of identity in the sense of Dunford [21] and offer a detailed analysis on the convergence rate, separation cutoff and L2-cutoff of this class of non-reversible Markov chains. We also look into the problem of estimating the integral functionals from discrete observations for this class. In the last part of this paper we investigate a particular similarity orbit of reversible Markov kernels, which we call the pure birth orbit, and analyse various possibly non-reversible variants of classical birth–death processes in this orbit.

Gallai [1] raised the question of determining t(n), the maximum number of triangles in graphs of n vertices with acyclic neighborhoods. Here we disprove his conjecture (t(n) ~ n2/8) by exhibiting graphs having n2/7.5 triangles. We improve the upper bound [11] of (n2 − n)/6 to t(n) ≤; n2/7.02 + O(n). For regular graphs, we further decrease this bound to n2/7.75 + O(n).

We prove that if $A \subseteq [X,\,2X]$ and $B \subseteq [Y,\,2Y]$ are sets of integers such that gcd (a, b) ⩾ D for at least δ|A||B| pairs (a, b) ε A × B then $|A||B|{ \ll _{\rm{\varepsilon }}}{\delta ^{ - 2 - \varepsilon }}XY/{D^2}$ . This is a new result even when δ = 1. The proof uses ideas of Koukoulopoulos and Maynard and some additional combinatorial arguments.

We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a stable potential. This result holds for all activities $\lambda$ for which the partition function satisfies a zero-free assumption in a neighbourhood of the interval $[0,\lambda ]$. As a corollary, for all finiterange stable potentials, we obtain a quasipolynomial-time deterministic algorithm for all $\lambda \lt 1/(e^{B + 1} \hat C_\phi )$ where $\hat C_\phi$ is a temperedness parameter and $B$ is the stability constant of $\phi$. In the special case of a repulsive potential such as the hard-sphere gas we improve the range of activity by a factor of at least $e^2$ and obtain a quasipolynomial-time deterministic approximation algorithm for all $\lambda \lt e/\Delta _\phi$, where $\Delta _\phi$ is the potential-weighted connective constant of the potential $\phi$. Our algorithm approximates coefficients of the cluster expansion of the partition function and uses the interpolation method of Barvinok to extend this approximation throughout the zero-free region.

For two stochastically dependent random variables X and Y taking values in {0,…, m−1}, we study the distribution of the random residue U = XY mod m. Our main result is an upper bound for the distance Δm = supx∈[0,1] [mid ] P(U/m [les ] x)−x[mid ]. For independent and uniformly distributed X and Y, the exact distribution of U is derived and shown to be stochastically smaller than the uniform distribution on {0,…, m−1}. Moreover, in this case Δm is given explicitly.

The notion of cross-intersecting set pair system of size $m$ , $ (\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m )$ with $A_i\cap B_i=\emptyset$ and $A_i\cap B_j\ne \emptyset$ , was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le\binom{a+b}{a}$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$ . Our central problem is to see how this bound changes with the additional condition $|A_i\cap B_j|=1$ for $i\ne j$ . Such a system is called $1$ -cross-intersecting. We show that these systems are related to perfect graphs, clique partitions of graphs, and finite geometries. We prove that their maximum size is

• at least $5^{n/2}$ for $n$ even, $a=b=n$ ,

• equal to $\bigl (\lfloor \frac{n}{2}\rfloor +1\bigr )\bigl (\lceil \frac{n}{2}\rceil +1\bigr )$ if $a=2$ and $b=n\ge 4$ ,

• at most $|\cup _{i=1}^m A_i|$ ,

• asymptotically $n^2$ if $\{A_i\}$ is a linear hypergraph ( $|A_i\cap A_j|\le 1$ for $i\ne j$ ),

• asymptotically ${1\over 2}n^2$ if $\{A_i\}$ and $\{B_i\}$ are both linear hypergraphs.

We consider supercritical site percolation on the $d$ -dimensional hypercube $Q^d$ . We show that typically all components in the percolated hypercube, besides the giant, are of size $O(d)$ . This resolves a conjecture of Bollobás, Kohayakawa, and Łuczak from 1994.

We show that for every $\eta \gt 0$ every sufficiently large $n$-vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta )\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs.

Further, we show that in the same setting, $D$ contains every $k$-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$.

Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$.

It is well known that the height profile of a critical conditioned Galton–Watson tree with finite offspring variance converges, after a suitable normalisation, to the local time of a standard Brownian excursion. In this work, we study the distance profile, defined as the profile of all distances between pairs of vertices. We show that after a proper rescaling the distance profile converges to a continuous random function that can be described as the density of distances between random points in the Brownian continuum random tree. We show that this limiting function a.s. is Hölder continuous of any order $\alpha<1$ , and that it is a.e. differentiable. We note that it cannot be differentiable at 0, but leave as open questions whether it is Lipschitz, and whether it is continuously differentiable on the half-line $(0,\infty)$ . The distance profile is naturally defined also for unrooted trees contrary to the height profile that is designed for rooted trees. This is used in our proof, and we prove the corresponding convergence result for the distance profile of random unrooted simply generated trees. As a minor purpose of the present work, we also formalize the notion of unrooted simply generated trees and include some simple results relating them to rooted simply generated trees, which might be of independent interest.

We show that an $n$-uniform maximal intersecting family has size at most $e^{-n^{0.5+o(1)}}n^n$. This improves a recent bound by Frankl ((2019) Comb. Probab. Comput. 28(5) 733–739.). The Spread Lemma of Alweiss et al. ((2020) Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.) plays an important role in the proof.

Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplified model for network security. In the game we consider in this paper, a team of r revolutionaries tries to hold an unguarded meeting consisting of m revolutionaries. A team of s spies wants to prevent this forever. For given r and m, the minimum number of spies required to win on a graph G is the spy number σ(G,r,m). We present asymptotic results for the game played on random graphs G(n,p) for a large range of p = p(n), r=r(n), and m=m(n). The behaviour of the spy number is analysed completely for dense graphs (that is, graphs with average degree at least n1/2+ε for some ε > 0). For sparser graphs, some bounds are provided.

For k-graphs F0 and H, an F0-packing of H is a family $\mathscr{F}$ of pairwise edge-disjoint copies of F0 in H. Let νF0(H) denote the maximum size |$\mathscr{F}$| of an F0-packing of H. Already in the case of graphs, computing νF0(H) is NP-hard for most fixed F0 (Dor and Tarsi [6]).

In this paper, we consider the case when F0 is a fixed linear k-graph. We establish an algorithm which, for ζ > 0 and a given k-graph H, constructs in time polynomial in |V(H)| an F0-packing of H of size at least νF0(H) − ζ |V(H)|k. Our result extends one of Haxell and Rödl, who established the analogous algorithm for graphs.

We explore the asymptotic distributions of sequences of integer-valued additive functions defined on the symmetric group endowed with the Ewens probability measure as the order of the group increases. Applying the method of factorial moments, we establish necessary and sufficient conditions for the weak convergence of distributions to discrete laws. More attention is paid to the Poisson limit distribution. The particular case of the number-of-cycles function is analysed in more detail. The results can be applied to statistics defined on random permutation matrices.

Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove that the values ρ() can be made arbitrarily large. The problem lies in the clique sum operation. As our main result, we show that excluding a planar graph with a fixed number of apex vertices gives rise to a minor-closed class with small degenerate value. As corollaries, we obtain that (i) the degenerate value of every class of graphs of bounded local tree-width is at most 6, and (ii) the degenerate value of the class of Kn-minor-free graphs is at most n + 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 and n + 2 of its chromatic number, respectively.

It is known that w.h.p. the hitting time τ2σ for the random graph process to have minimum degree 2σ coincides with the hitting time for σ edge-disjoint Hamilton cycles [4, 9, 13]. In this paper we prove an online version of this property. We show that, for a fixed integer σ ⩾ 2, if random edges of Kn are presented one by one then w.h.p. it is possible to colour the edges online with σ colours so that at time τ2σ each colour class is Hamiltonian.

In [11] it is shown that the theory of almost all graphs is first-order complete. Furthermore, in [3] a collection of first-order axioms are given from which any first-order property or its negation can be deduced. Here we show that almost all Steinhaus graphs satisfy the axioms of almost all graphs and conclude that a first-order property is true for almost all graphs if and only if it is true for almost all Steinhaus graphs. We also show that certain classes of subgraphs of vertex transitive graphs are first-order complete. Finally, we give a new class of higher-order axioms from which it follows that large subgraphs of specified type exist in almost all graphs.

To bound the probability of a union of n events from a single set of events, Bonferroni inequalities are sometimes used. There are sharper bounds which are called Sobel–Uppuluri–Galambos inequalities. When two (or more) sets of events are involved, bounds are considered on the probability of intersection of several such unions, one union from each set. We present a method for unified treatment of bivariate lower and upper bounds in this note. The lower bounds obtained are new and at least as good as lower bounds appearing in the literature so far. The upper bounds coincide with existing bivariate Sobel–Uppuluri–Galambos type upper bounds derived by the method of indicator functions. A numerical example is given to illustrate that the new lower bounds can be strictly better than existing ones.

We derive a generalization of a theorem of Raimi proving there is a partition of natural numbers with given densities of classes which meet structured translates of any other class of a partition of natural numbers.