Recently there has been much interest in studying random graph analogues of well-known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of G(n, p) with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of G(n, p) with minimum degree at least (2/5 + o(1))pn is (p−1n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + ϵ)pn is O(p−1n)-close to r-partite for some r = r(ϵ). These are random graph analogues of a result by Andrásfai, Erdős and Sós (Discrete Math.8 (1974), 205–218), and a result by Thomassen (Combinatorica22 (2002), 591–596). We also show that our results are best possible up to a constant factor.

In this paper we prove lower and upper bounds for the extinction time of the contact process on random geometric graphs with connection radius tending to infinity. We obtain that for any infection rate λ > 0, the contact process on these graphs survives a time super-exponential in the number of vertices.

In network modelling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in the form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a Joint Degree Matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence, and conjectured that it mixes rapidly (in polynomial time) for arbitrary degree sequences. Although the conjecture is still open, it has been proved for special degree sequences, in particular for those of undirected and directed regular simple graphs, half-regular bipartite graphs, and graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite ‘splitted’ degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs.

A cutset is a non-empty finite subset of ℤd which is both connected and co-connected. A cutset is odd if its vertex boundary lies in the odd bipartition class of ℤd. Peled [18] suggested that the number of odd cutsets which contain the origin and have n boundary edges may be of order eΘ(n/d) as d → ∞, much smaller than the number of general cutsets, which was shown by Lebowitz and Mazel [15] to be of order dΘ(n/d). In this paper, we verify this by showing that the number of such odd cutsets is (2+o(1))n/2d.

Assume that the edges of the complete graph Kn are given independent uniform [0, 1] weights. We consider the expected minimum total weight μk of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μk ≈ k2. Most of the paper is concerned with the case k = 2. We show that m2 tends to an explicitly defined constant and that μ2 ≈ 4.1704288. . . .

This paper deals with a combinatorial problem concerning colourings of uniform hypergraphs with large girth. We prove that if H is an n-uniform non-r-colourable simple hypergraph then its maximum edge degree Δ(H) satisfies the inequality

$$ \Delta(H)\geqslant c\cdot r^{n-1}\ffrac{n(\ln\ln n)^2}{\ln n} $$

As an application of our probabilistic technique we establish a lower bound for the classical van der Waerden number W(n, r), the minimum natural N such that in an arbitrary colouring of the set of integers {1,. . .,N} with r colours there exists a monochromatic arithmetic progression of length n. We prove that

$$ W(n,r)\geqslant c\cdot r^{n-1}\ffrac{(\ln\ln n)^2}{\ln n}. $$

The classical Kővári–Sós–Turán theorem states that if G is an n-vertex graph with no copy of Ks,t as a subgraph, then the number of edges in G is at most O(n2−1/s). We prove that if one forbids Ks,t as an induced subgraph, and also forbids any fixed graph H as a (not necessarily induced) subgraph, the same asymptotic upper bound still holds, with different constant factors. This introduces a non-trivial angle from which to generalize Turán theory to induced forbidden subgraphs, which this paper explores. Along the way, we derive a non-trivial upper bound on the number of cliques of fixed order in a Kr-free graph with no induced copy of Ks,t. This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.