JournalTOCs

Combinatorics, Probability and Computing
[SJR: 1.013] [H-I: 35] [4 followers] Follow

Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163
Published by Cambridge University Press

[365 journals]

Triangle-Free Subgraphs of Random Graphs
- Authors: PETER ALLEN; JULIA BÖTTCHER, YOSHIHARU KOHAYAKAWA, BARNABY ROBERTS
  Pages: 141 - 161
  Abstract: 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 −1 n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + ϵ)pn is O(p −1 n)-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 (Combinatorica 22 (2002), 591–596). We also show that our results are best possible up to a constant factor.
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000219
  Issue No: Vol. 27, No. 2 (2018)
Super-Exponential Extinction Time of the Contact Process on Random
Geometric Graphs
- Authors: VAN HAO CAN
  Pages: 162 - 185
  Abstract: 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.
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000372
  Issue No: Vol. 27, No. 2 (2018)
New Classes of Degree Sequences with Fast Mixing Swap Markov Chain
Sampling
- Authors: PÉTER L. ERDŐS; ISTVÁN MIKLÓS, ZOLTÁN TOROCZKAI
  Pages: 186 - 207
  Abstract: 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.
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000499
  Issue No: Vol. 27, No. 2 (2018)
The Growth Constant of Odd Cutsets in High Dimensions
- Authors: OHAD NOY FELDHEIM; YINON SPINKA
  Pages: 208 - 227
  Abstract: 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 .
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000438
  Issue No: Vol. 27, No. 2 (2018)
On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- Authors: ALAN FRIEZE; TONY JOHANSSON
  Pages: 228 - 244
  Abstract: 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 ≈ k 2. Most of the paper is concerned with the case k = 2. We show that m 2 tends to an explicitly defined constant and that μ 2 ≈ 4.1704288. . . .
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000426
  Issue No: Vol. 27, No. 2 (2018)
Colourings of Uniform Hypergraphs with Large Girth and Applications
- Authors: ANDREY KUPAVSKII; DMITRY SHABANOV
  Pages: 245 - 273
  Abstract: 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}$$ for some absolute constant c > 0. 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}.$$
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000475
  Issue No: Vol. 27, No. 2 (2018)
Induced Turán Numbers
- Authors: PO-SHEN LOH; MICHAEL TAIT, CRAIG TIMMONS, RODRIGO M. ZHOU
  Pages: 274 - 288
  Abstract: The classical Kővári–Sós–Turán theorem states that if G is an n-vertex graph with no copy of K s,t as a subgraph, then the number of edges in G is at most O(n 2−1/s ). We prove that if one forbids K s,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 K r -free graph with no induced copy of K s,t . This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.
  PubDate: 2018-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000542
  Issue No: Vol. 27, No. 2 (2018)