We give the crossing number of the join product $W_{4}+D_{n}$, where $W_{4}$ is the wheel on five vertices and $D_{n}$ consists of $n$ isolated vertices. The proof is based on calculating the minimum number of crossings between two different subgraphs from the set of subgraphs which do not cross the edges of the graph $W_{4}$ and from the set of subgraphs which cross the edges of $W_{4}$ exactly once.

A digraph is called oriented if there is at most one arc between two distinct vertices. An oriented graph $D$ is nonsingular if its adjacency matrix $A(D)$ is nonsingular. We characterise all nonsingular oriented graphs from three classes: graphs in which cycles are vertex disjoint, graphs in which all cycles share exactly one common vertex and graphs formed by cycles sharing a common path. As a straightforward corollary, the singularity of oriented bicyclic graphs is determined.

The inducibility of a graph H measures the maximum number of induced copies of H a large graph G can have. Generalizing this notion, we study how many induced subgraphs of fixed order k and size ℓ a large graph G on n vertices can have. Clearly, this number is $\left( {\matrix{n \cr k}}\right)$ for every n, k and $\ell \in \left\{ {0,\left( {\matrix{k \cr 2}} \right)}\right\}$. We conjecture that for every n, k and $0 \lt \ell \lt \left( {\matrix{k \cr 2}}\right)$ this number is at most $ (1/e + {o_k}(1)) {\left( {\matrix{n \cr k}} \right)}$. If true, this would be tight for ℓ ∈ {1, k − 1}.

In support of our ‘Edge-statistics Conjecture’, we prove that the corresponding density is bounded away from 1 by an absolute constant. Furthermore, for various ranges of the values of ℓ we establish stronger bounds. In particular, we prove that for ‘almost all’ pairs (k, ℓ) only a polynomially small fraction of the k-subsets of V(G) have exactly ℓ edges, and prove an upper bound of $ (1/2 + {o_k}(1)){\left( {\matrix{n \cr k}}\right)}$ for ℓ = 1.

Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun’s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov’s symmetrization, Sperner’s theorem and various counting techniques.

We prove that, with high probability, in every 2-edge-colouring of the random tournament on n vertices there is a monochromatic copy of every oriented tree of order $O(n{\rm{/}}\sqrt {{\rm{log}} \ n} )$. This generalizes a result of the first, third and fourth authors, who proved the same statement for paths, and is tight up to a constant factor.

For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O({n^{1/3}}{\log ^{2/3}}n)$. This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. We also show that if, for a pair α, β of real numbers, there exist infinitely many graphs for which the two spread times are nα and nβ in expectation, then $0 \le \alpha \le 1$ and $\alpha \le \beta \le {1 \over 3} + {2 \over 3} \alpha $; and we show each such pair α, β is achievable.

With entries of the adjacency matrix of a simple graph being regarded as elements of $\mathbb{F}_{2}$, it is proved that a finite commutative ring $R$ with $1\neq 0$ is a Boolean ring if and only if either $R\in \{\mathbb{F}_{2},\mathbb{F}_{2}\times \mathbb{F}_{2}\}$ or the eigenvalues (in the algebraic closure of $\mathbb{F}_{2}$) corresponding to the zero-divisor graph of $R$ are precisely the elements of $\mathbb{F}_{4}\setminus \{0\}$ . This is achieved by observing a way in which algebraic behavior in a Boolean ring is encoded within Pascal’s triangle so that computations can be carried out by appealing to classical results from number theory.

We give sufficient conditions for the non-triviality of the Poisson boundary of random walks on $H(\mathbb{Z})$ and its subgroups. The group $H(\mathbb{Z})$ is the group of piecewise projective homeomorphisms over the integers defined by Monod [Groups of piecewise projective homeomorphisms. Proc. Natl Acad. Sci. USA110(12) (2013), 4524–4527]. For a finitely generated subgroup $H$ of $H(\mathbb{Z})$, we prove that either $H$ is solvable or every measure on $H$ with finite first moment that generates it as a semigroup has non-trivial Poisson boundary. In particular, we prove the non-triviality of the Poisson boundary of measures on Thompson’s group $F$ that generate it as a semigroup and have finite first moment, which answers a question by Kaimanovich [Thompson’s group $F$ is not Liouville. Groups, Graphs and Random Walks (London Mathematical Society Lecture Note Series). Eds. T. Ceccherini-Silberstein, M. Salvatori and E. Sava-Huss. Cambridge University Press, Cambridge, 2017, pp. 300–342, 7.A].

We show that, on graphs which have precisely three distinct Laplacian eigenvalues, heat diffusion enjoys a monotonic behaviour.

Akbari and Alipour [1] conjectured that any Latin array of order n with at least n2/2 symbols contains a transversal. For large n, we confirm this conjecture, and moreover, we show that n399/200 symbols suffice.

The hedgehog Ht is a 3-uniform hypergraph on vertices $1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$ such that, for any pair (i, j) with 1 ≤ i < j ≤ t, there exists a unique vertex k > t such that {i, j, k} is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog Ht is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r(Ht) = O(t2 ln t).

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least

$$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$

The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2m)/n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least

$${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$

Given a graph G and a bijection f : E(G) → {1, 2,…,e(G)}, we say that a trail/path in G is f-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.

In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1-o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1).

We prove that the free uniform spanning forest of any bounded degree proper plane graph is connected almost surely, answering a question of Benjamini, Lyons, Peres and Schramm. We provide a quantitative form of this result, calculating the critical exponents governing the geometry of the uniform spanning forests of transient proper plane graphs with bounded degrees and codegrees. We find that the same exponents hold universally over this entire class of graphs provided that measurements are made using the hyperbolic geometry of their circle packings rather than their usual combinatorial geometry.

In this work, we use rigorous probabilistic methods to study the asymptotic degree distribution, clustering coefficient, and diameter of geographical attachment networks. As a type of small-world network model, these networks were first proposed in the physical literature, where they were analyzed only with heuristic arguments and computational simulations.

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.

The no restart random walk (NRRW) is a random network growth model driven by a random walk that builds the graph while moving on it, adding and connecting a new leaf node to the current position of the walker every s steps. We show a fundamental dichotomy in NRRW with respect to the parity of s: for ${s}=1$ we prove that the random walk is transient and non-leaf nodes have degrees bounded above by an exponential distribution; for s even we prove that the random walk is recurrent and non-leaf nodes have degrees bounded below by a power law distribution. These theoretical findings highlight and confirm the diverse and rich behaviour of NRRW observed empirically.

We study the average nearest-neighbour degree a(k) of vertices with degree k. In many real-world networks with power-law degree distribution, a(k) falls off with k, a property ascribed to the constraint that any two vertices are connected by at most one edge. We show that a(k) indeed decays with k in three simple random graph models with power-law degrees: the erased configuration model, the rank-1 inhomogeneous random graph, and the hyperbolic random graph. We find that in the large-network limit for all three null models, a(k) starts to decay beyond $n^{(\tau-2)/(\tau-1)}$ and then settles on a power law $a(k)\sim k^{\tau-3}$, with $\tau$ the degree exponent.

We consider subgraph counts in general preferential attachment models with power-law degree exponent $\tau > 2$. For all subgraphs H, we find the scaling of the expected number of subgraphs as a power of the number of vertices. We prove our results on the expected number of subgraphs by defining an optimization problem that finds the optimal subgraph structure in terms of the indices of the vertices that together span it and by using the representation of the preferential attachment model as a Pólya urn model.

Archdeacon and Grable (1995) proved that the genus of the random graph $G\in {\mathcal{G}}_{n,p}$ is almost surely close to $pn^{2}/12$ if $p=p(n)\geqslant 3(\ln n)^{2}n^{-1/2}$. In this paper we prove an analogous result for random bipartite graphs in ${\mathcal{G}}_{n_{1},n_{2},p}$. If $n_{1}\geqslant n_{2}\gg 1$, phase transitions occur for every positive integer $i$ when $p=\unicode[STIX]{x1D6E9}((n_{1}n_{2})^{-i/(2i+1)})$. A different behaviour is exhibited when one of the bipartite parts has constant size, i.e., $n_{1}\gg 1$ and $n_{2}$ is a constant. In that case, phase transitions occur when $p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/2})$ and when $p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/3})$.