Mader proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k2 edges, where equality holds for the complete bipartite digraph DKk,n-k. For dense strongly k-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly k-connected n-vertex digraph D contains a strongly k-connected spanning subgraph with at most kn + 800k(k + Δ(D)) edges, where Δ(D) denotes the maximum degree of the complement of the underlying undirected graph of a digraph D. Here, the additional term 800k(k + Δ(D)) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k2 edges, which is essentially optimal since 800k2 cannot be reduced to the number less than k(k - 1)/2.

We also prove an analogous result for strongly k-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.

In this paper we prove polynomial versions of the Carlson–Simpson theorem and the Graham–Rothschild theorem on parameter sets. To do so we prove a useful extension of the polynomial Hales–Jewett theorem.

We consider a random generalized railway defined as a random 3-regular multigraph where some vertices are regarded as switches that only allow traffic between certain pairs of attached edges. It is shown that the probability that the generalized railway is functioning is linear in the proportion of switches. Thus there is no threshold phenomenon for this property.

We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-triangles converge to 1/8. Since the random graph $\mathcal{G}$n,1/2 is, in particular, 3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern [10]. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ⩾ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.

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$.

For a graph $H$ and a hypercube $Q_n$, $\textrm{ex}(Q_n, H)$ is the largest number of edges in an $H$-free subgraph of $Q_n$. If $\lim _{n \rightarrow \infty } \textrm{ex}(Q_n, H)/|E(Q_n)| \gt 0$, $H$ is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise, it has zero Turán density. Determining $\textrm{ex}(Q_n, H)$ and even identifying whether $H$ has a positive or zero Turán density remains a widely open question for general $H$. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of graphs, ones having so-called partite representation, that have zero Turán density. He asked whether this gives a characterisation, that is, whether a graph has zero Turán density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of graphs which have no partite representation, but on the other hand, have zero Turán density. In addition, we show that any graph whose every block has partite representation has zero Turán density in a hypercube.

For c ∈ (0,1) let n(c) denote the set of n-vertex perfect graphs with density c and let n(c) denote the set of n-vertex graphs without induced C5 and with density c.

We show that with otherwise, where H is the binary entropy function.

Further, we use this result to deduce that almost all graphs in n(c) have homogeneous sets of linear size. This answers a question raised by Loebl and co-workers.

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.

A chordal graph is a graph with no induced cycles of length at least $4$. Let $f(n,m)$ be the maximal integer such that every graph with $n$ vertices and $m$ edges has a chordal subgraph with at least $f(n,m)$ edges. In 1985 Erdős and Laskar posed the problem of estimating $f(n,m)$. In the late 1980s, Erdős, Gyárfás, Ordman and Zalcstein determined the value of $f(n,n^2/4+1)$ and made a conjecture on the value of $f(n,n^2/3+1)$. In this paper we prove this conjecture and answer the question of Erdős and Laskar, determining $f(n,m)$ asymptotically for all $m$ and exactly for $m \leq n^2/3+1$.

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 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.

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.

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.

Suppose M and N are distinct matroids on a set E such that, for every e ∈ E, the deletion of e from M equals the deletion of e from N or the contraction of e from M equals the contraction of e from N. In this note we prove that, apart from some easily specified exceptions, one of M and N must be a relaxation of the other.

In generalisation of the beta law obtained under the GEM/Poisson–Dirichlet distribution in Hirth [12] we undertake here an analogous construction which results in the Dirichlet law. Our proof makes use of Hoppe's Pólya-like urn model in population genetics.

A spread-out lattice animal is a finite connected set of edges in $\{\{x,y\}\subset \mathbb{Z}^d\;:\;0\lt \|x-y\|\le L\}$. A lattice tree is a lattice animal with no loops. The best estimate on the critical point $p_{\textrm{c}}$ so far was achieved by Penrose (J. Stat. Phys. 77, 3–15, 1994) : $p_{\textrm{c}}=1/e+O(L^{-2d/7}\log L)$ for both models for all $d\ge 1$. In this paper, we show that $p_{\textrm{c}}=1/e+CL^{-d}+O(L^{-d-1})$ for all $d\gt 8$, where the model-dependent constant $C$ has the random-walk representation

\begin{align*} C_{\textrm{LT}}=\sum _{n=2}^\infty \frac{n+1}{2e}U^{*n}(o),&& C_{\textrm{LA}}=C_{\textrm{LT}}-\frac 1{2e^2}\sum _{n=3}^\infty U^{*n}(o), \end{align*}

$U^{*n}$

$n$

$d$

$\{x\in{\mathbb R}^d\;: \|x\|\le 1\}$

$p$

Random increasing k-trees represent an interesting and useful class of strongly dependent graphs that have been studied widely, including being used recently as models for complex networks. In this paper we study an informative notion called BFS-profile and derive, by several analytic means, asymptotic estimates for its expected value, together with the limiting distribution in certain cases; some interesting consequences predicting more precisely the shapes of random k-trees are also given. Our methods of proof rely essentially on a bijection between k-trees and ordinary trees, the resolution of linear systems, and a specially framed notion called Flajolet–Odlyzko admissibility.

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.

Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called Pólya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.

Erdős asked if, for every pair of positive integers g and k, there exists a graph H having girth (H) = k and the property that every r-colouring of the edges of H yields a monochromatic cycle Ck. The existence of such graphs H was confirmed by the third author and Ruciński.

We consider the related numerical problem of estimating the order of the smallest graph H with this property for given integers r and k. We show that there exists a graph H on R10k2; k15k3 vertices (where R = R(Ck; r) is the r-colour Ramsey number for the cycle Ck) having girth (H) = k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic Ck Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered.