We resolve a conjecture proposed by D.E. Knuth concerning a recurrence arising in the satisfiability problem. Knuth's recurrence resembles recurrences arising in the analysis of tries, in particular PATRICIA tries, and asymmetric leader election. We solve Knuth's recurrence exactly and asymptotically, using analytic techniques such as the Mellin transform and analytic depoissonization.

We study random unlabelled k-trees by combining the colouring approach by Gainer-Dewar and Gessel (2014) with the cycle-pointing method by Bodirsky, Fusy, Kang and Vigerske (2011). Our main applications are Gromov–Hausdorff–Prokhorov and Benjamini–Schramm limits that describe their asymptotic geometric shape on a global and local scale as the number of (k + 1)-cliques tends to infinity.

Let $\gamma(G)$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n-vertex graph of minimum degree at least d, then

$$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$

In this paper the main result is that if G is any n-vertex d-regular graph of girth at least five, then

$$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$

$d \rightarrow \infty$

$$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$

Furthermore, if G is a disjoint union of ${n}/{(2d)}$ complete bipartite graphs $K_{d,d}$ , then ${\gamma_\circ}(G) = \frac{n}{2}$ . We also prove that there are n-vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that ${\gamma_\circ}(G) \sim {n}/{2}$ as $d \rightarrow \infty$ . Therefore both the girth and regularity conditions are required for the main result.

NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proved to be easy. We show the intractability of random instances of a graph colouring problem: this graph problem is hard on average unless all NP problems under all samplable (i.e. generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial distortion of probabilities. This poses significant technical difficulties.

We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x, y \in \mathbb{Q}$ with $xy \not =1$, it is #P-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph.

In this paper we consider a bipartite version of Schütte's well-known tournament problem. A bipartite tournament $T=(A,B,E)$ with teams $A$ and $B$, and set of arcs $E$, has the property $S_{k,l}$ if for any subsets $K\subseteq A$ and $L\subseteq B$, with $|K| =k$ and $| L | =l$, there exist conquerors of $K$ and $L$ in opposite teams. The task is to estimate, for fixed $k$ and $l$, the minimum number $f(k,l)=| A | + | B | $ of players in a tournament satisfying property $S_{k,l}$. We achieve this goal by reformulating the problem in terms of intersecting set families and applying probabilistic as well as constructive methods. Intriguing connections with some famous problems of this area have emerged in this way, leading to new open questions.

We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall and Spencer in 2002 [14]. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2−s, (a + 1)2−s] × [b2−t, (b + 1)2−t] for a, b, s, t ∈ ℤ⩾ 0. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n4.09), which implies that the mixing time is at most O(n5.09). We complement this by showing that the relaxation time is at least Ω(n1.38), improving upon the previously best lower bound of Ω(n log n) coming from the diameter of the chain.

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is the union of r comparability (or more generally, perfect) graphs, then either G or its complement contains a clique of size $n^{1/(r+1)}$ .

This bound is known to be tight for $r=1$ . The question whether it is optimal for $r\ge 2$ was studied by Dumitrescu and Tóth. We prove that it is essentially best possible for $r=2$ , as well: we introduce a probabilistic construction of two comparability graphs on n vertices, whose union contains no clique or independent set of size $n^{1/3+o(1)}$ .

Using similar ideas, we can also construct a graph G that is the union of r comparability graphs, and neither G nor its complement contain a complete bipartite graph with parts of size $cn/{(log n)^r}$ . With this, we improve a result of Fox and Pach.

In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings.

In a paper published in this journal, Alon, Kohayakawa, Mauduit, Moreira and Rödl proved that the minimal possible value of the normality measure of an N-element binary sequence satisfies

\begin{equation*} \biggl( \frac{1}{2} + o(1) \biggr) \log_2 N \leq \min_{E_N \in \{0,1\}^N} \mathcal{N}(E_N) \leq 3 N^{1/3} (\log N)^{2/3} \end{equation*}

In my recent paper [1] there is a mistake in the proof of Corollary 3. The first line of the displayed equation in that proof asserts that

\[\int_G|\langle u,\pi^g v\rangle_V|^2\,\rm{d} g = \int_G\langle u\otimes u,(\pi^g\otimes \pi^g)(v\otimes v)\rangle_{V\otimes V}\, \rm{d} g.\]

We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms (QuickSort, InsertionSort, BubbleSort). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The ‘realistic’ cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2n log n, InsertionSort to n2/4 and BubbleSort to n2/2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ (n log2n), Θ(n2), Θ (n2 log n). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.

It is well known that a matroid is a transversal matroid if and only if it is a matching matroid (in the sense that it is the restriction of the matching structure of some graph to a subset of its vertices). A simple proof of that result is now known and in this paper it is used to answer the long-standing question of which transversal matroids are “strict” matching matroids; i.e. actually equal to the matching structure of a graph. We develop a straightforward test of “coloop-surfeit” that can be applied to any transversal matroid, and our main theorem shows that a transversal matroid is a strict matching matroid if and only if it has even rank and coloop-surfeit. Furthermore, the proofs are algorithmic and enable the construction of an appropriate graph from any presentation of a strict matching matroid.

A tight upper bound on the number of elements in a connected matroid with fixed rank and largest cocircuit size is given. This upper bound is used to show that a connected matroid with at least thirteen elements contains either a circuit or a cocircuit with at least six elements. In the language of matroid Ramsey numbers, n(6, 6) = 13: this is the largest currently known matroid Ramsey number.

Let G = (V, E) be a graph with n vertices, chromatic number χ(G) and list chromatic number χ[lscr ](G). Suppose each vertex of V(G) is assigned a list of t colours. Albertson, Grossman and Haas [1] conjectured that at least [formula here] vertices can be coloured properly from these lists.

Albertson, Grossman and Haas [1] and Chappell [3] proved partial results concerning this conjecture. This paper presents algorithms that colour at least the number of vertices given in the bounds of Albertson, Grossman and Haas, and Chappell. In particular, it follows that the conjecture is valid for all bipartite graphs and that, for every bipartite graph and every assignment of lists with t colours in each list where 0 [les ] t [les ] χ[lscr ](G), it is possible to colour at least (1 − (1/2)t)n vertices in polynomial time. Thus, if G is bipartite and [Lscr ] is a list assignment with [mid ]L(v)[mid ] [ges ] log2n for all v ∈ V, then G is [Lscr ]-list colourable in polynomial time.

We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extent of our knowledge, the first approach that deals with pair potentials of unbounded range.

We study several parameters of a random Bienaymé–Galton–Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $\xi$ with mean $1$ and nonzero finite variance $\sigma ^2$ . Let $f(s)=\mathbb{E}\{s^\xi \}$ be the generating function of the random variable $\xi$ . We show that the independence number is in probability asymptotic to $qn$ , where $q$ is the unique solution to $q = f(1-q)$ . One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n/\log (1/f'(1-q))$ . Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1 = \mathbb{P}\{\xi =1\}\gt 0$ , then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log (1/p_1)$ . If $p_1 = 0$ and $\kappa$ is the first integer $i\gt 1$ with $\mathbb{P}\{\xi =i\}\gt 0$ , then the leaf-height is in probability asymptotic to $\log _\kappa \log n$ .

For a random graph on n vertices where the edges appear with individual rates, we give exact formulas for the expected time at which the number of components has gone down to k and the expected length of the corresponding minimal spanning forest.

For a random bipartite graph we give a formula for the expected time at which a k-assignment appears. This result has a bearing on the random assignment problem.

We give combinatorial descriptions of two stochastic growth models for series-parallel networks introduced by Hosam Mahmoud by encoding the growth process via recursive tree structures. Using decompositions of the tree structures and applying analytic combinatorics methods allows a study of quantities in the corresponding series-parallel networks. For both models we obtain limiting distribution results for the degree of the poles and the length of a random source-to-sink path, and furthermore we get asymptotic results for the expected number of source-to-sink paths. Moreover, we introduce generalizations of these stochastic models by encoding the growth process of the networks via further important increasing tree structures.