It is shown that the size of a subgraph of Qn without a cycle of length 14 is of order o(|E(Qn)|).

Markov chain decomposition is a tool for analysing the convergence rate of a complicated Markov chain by studying its behaviour on smaller, more manageable pieces of the state space. Roughly speaking, if a Markov chain converges quickly to equilibrium when restricted to subsets of the state space, and if there is sufficient ergodic flow between the pieces, then the original Markov chain also must converge rapidly to equilibrium. We present a new version of the decomposition theorem where the pieces partition the state space, rather than forming a cover where pieces overlap, as was previously required. This new formulation is more natural and better suited to many applications. We apply this disjoint decomposition method to demonstrate the efficiency of simple Markov chains designed to uniformly sample circuits of a given length on certain Cayley graphs. The proofs further indicate that a Markov chain for sampling adsorbing staircase walks, a problem arising in statistical physics, is also rapidly mixing.

Let A be a finite non-empty set of integers. An asymptotic estimate of the size of the sum of several dilates was obtained by Bukh. The unique known exact bound concerns the sum |A + k⋅A|, where k is a prime and |A| is large. In its full generality, this bound is due to Cilleruelo, Serra and the first author.

Let k be an odd prime and assume that |A| > 8kk. A corollary to our main result states that |2⋅A + k⋅A|≥(k+2)|A|−k2−k+2. Notice that |2⋅P+k⋅P|=(k+2)|P|−2k, if P is an arithmetic progression.

A family of subsets of an n-set is k-locally thin if, for every k of its member sets, the ground set has at least one element contained in exactly 1 of them. We derive new asymptotic upper bounds for the maximum cardinality of locally thin set families for every even k. This improves on previous results of two of the authors with Monti.

We show that, if G is a graph of order n with maximal degree Δ(G) and minimal degree δ(G) whose complement contains no K2,s, s [ges ] 2, then G contains every tree T of order n−s+1 whose maximal degree is at most Δ(G) and whose vertex of second-largest degree is at most δ(G). We then show that this result implies that special cases of two conjectures are true. We verify that the Erdös–Sós conjecture, which states that a graph whose average degree is larger than k−1 contains every tree of order k+1, is true for graphs whose complement does not contain a K2,4, and the Komlós–Sós conjecture, which states that every graph of median degree at least k contains every tree of order k+1, is true for graphs whose complement does not contain a K2,3.

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 Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.

Let Hd(n,p) signify a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of Hd(n,p) and Hd(n,m) in the regime $(d-1)\binom{n-1}{d-1}p>1+\varepsilon$, resp. d(d−1)m/n>1+ϵ, where ϵ>0 is arbitrarily small but fixed as n → ∞. The proofs are based on a purely probabilistic approach.

Consider the following one-player game. Starting with the empty graph on n vertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one of r available colours. The player's goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove an upper bound on the typical duration of this game if F is from a large class of graphs including cliques and cycles of arbitrary size. Together with lower bounds published elsewhere, explicit threshold functions follow.

Szemerédi's regularity lemma and its variants are some of the most powerful tools in combinatorics. In this paper, we establish several results around the regularity lemma. First, we prove that whether or not we include the condition that the desired vertex partition in the regularity lemma is equitable has a minimal effect on the number of parts of the partition. Second, we use an algorithmic version of the (weak) Frieze–Kannan regularity lemma to give a substantially faster deterministic approximation algorithm for counting subgraphs in a graph. Previously, only an exponential dependence for the running time on the error parameter was known, and we improve it to a polynomial dependence. Third, we revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for several co-NP-complete problems. We show how to use the weak Frieze–Kannan regularity lemma to approximate the regularity of a pair of vertex subsets. We also show how to quickly find, for each ε′>ε, an ε′-regular partition with k parts if there exists an ε-regular partition with k parts. Finally, we give a simple proof of the permutation regularity lemma which improves the tower-type bound on the number of parts in the previous proofs to a single exponential bound.

Let denote the set of unrooted labelled trees of size n and let ℳ be a particular (finite, unlabelled) tree. Assuming that every tree of is equally likely, it is shown that the limiting distribution as n goes to infinity of the number of occurrences of ℳ is asymptotically normal with mean value and variance asymptotically equivalent to μn and σ2n, respectively, where the constants μ>0 and σ≥0 are computable.

Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WilfPlus, which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.

We consider statistical properties of random integer partitions. In order to compute means, variances and higher moments of various partition statistics, one often has to study generating functions of the form P(x)F(x), where P(x) is the generating function for the number of partitions. In this paper, we show how asymptotic expansions can be obtained in a quasi-automatic way from expansions of F(x) around x = 1, which parallels the classical singularity analysis of Flajolet and Odlyzko in many ways. Numerous examples from the literature, as well as some new statistics, are treated via this methodology. In addition, we show how to compute further terms in the asymptotic expansions of previously studied partition statistics.

Let F = {G1, …, Gt} be a family of n-vertex graphs defined on the same vertex-set V, and let k be a positive integer. A subset of vertices D ⊂ V is called an (F, k)-core if, for each v ∈ V and for each i = 1, …, t, there are at least k neighbours of v in Gi that belong to D. The subset D is called a connected (F, k)-core if the subgraph induced by D in each Gi is connected. Let δi be the minimum degree of Gi and let δ(F) = minti=1δi. Clearly, an (F, k)-core exists if and only if δ(F) [ges ] k, and a connected (F, k)-core exists if and only if δ(F) [ges ] k and each Gi is connected. Let c(k, F) and cc(k, F) be the minimum size of an (F, k)-core and a connected (F, k)-core, respectively. The following asymptotic results are proved for every t < ln ln δ and k < √lnδ:

formula here

The results are asymptotically tight for infinitely many families F. The results unify and extend related results on dominating sets, strong dominating sets and connected dominating sets.

It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is #P-hard in all but a few special points. On the other hand, several papers in the past few years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid $M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of a branch-decomposition of $M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.

Tutte proved that if e is an element of a 3-connected matroid M such that neither M\e nor M/e is 3-connected, then e is in a 3-circuit or a 3-cocircuit. In this paper, we prove a broad generalization of this result. Among the consequences of this generalization are that if X is an (n − 1)-element subset of an n-connected matroid M such that neither M\X nor M/X is connected, then, provided |E(M)| ≥ 2(n − 1)≥ 4, X is in both an n-element circuit and an n-element cocircuit. When n = 3, we describe the structure of M more closely using Δ − Y exchanges. Several related results are proved and we also show that, for all fields F other than GF(2), the set of excluded minors for F-representability is closed under both Δ − Y and Y − Δ exchanges.

In the present paper we consider compound Poisson approximation by Stein's method for dissociated random variables. We present some applications to problems in system reliability. In particular, our examples have the structure of an incomplete U-statistics. We mainly apply techniques from Barbour and Utev, who gave new bounds for the solutions of the Stein equation in compound Poisson approximation in two recent papers.

We show that evaluating the Tutte polynomial for the class of bicircular matroids is #P-hard at every point $(x,y)$ except those in the hyperbola $(x-1)(y-1)=1$ and possibly those on the lines $x=0$ and $x=-1$. Since bicircular matroids form a rather restricted subclass of transversal matroids, our results can be seen as a partial strengthening of a result by Colbourn, Provan and Vertigan, namely that the evaluation of the Tutte polynomial for the class of transversal matroids is #P-hard for all points except those in the hyperbola $(x-1)(y-1)=1$.

An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4.

We give an algorithm that, with high probability, recovers a planted $k$-partition in a random graph, where edges within vertex classes occur with probability $p$ and edges between vertex classes occur with probability $r\ge p+c\sqrt{p\log n/n}$. The algorithm can handle vertex classes of different sizes and, for fixed $k$, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.