In this paper we consider random distance graphs motivated by applications in neurobiology. These models can be viewed as examples of inhomogeneous random graphs, notably outside of the so-called rank-1 case. Treating these models in the context of the general theory of inhomogeneous graphs helps us to derive the asymptotics for the size of the largest connected component. In particular, we show that certain random distance graphs behave exactly as the classical Erdős–Rényi model, not only in the supercritical phase (as already known) but in the subcritical case as well.

The Horton–Strahler ordering method, originating in hydrology, formulates the hierarchical structure of branching patterns using a quantity called the bifurcation ratio. The main result of this paper is the central limit theorem for the bifurcation ratio of a general branch order. This is a generalized form of the central limit theorem for the lowest bifurcation ratio, which was previously proved. Some useful relations regarding the Horton–Strahler analysis are also derived in the proofs of the main theorems.

A celebrated result of Rödl and Ruciński states that for every graph $F$, which is not a forest of stars and paths of length 3, and fixed number of colours $r\geqslant 2$ there exist positive constants $c,C$ such that for $p\leqslant cn^{-1/m_{2}(F)}$ the probability that every colouring of the edges of the random graph $G(n,p)$ contains a monochromatic copy of $F$ is $o(1)$ (the ‘0-statement’), while for $p\geqslant Cn^{-1/m_{2}(F)}$ it is $1-o(1)$ (the ‘1-statement’). Here $m_{2}(F)$ denotes the 2-density of $F$. On the other hand, the case where $F$ is a forest of stars has a coarse threshold which is determined by the appearance of a certain small subgraph in $G(n,p)$. Recently, the natural extension of the 1-statement of this theorem to $k$-uniform hypergraphs was proved by Conlon and Gowers and, independently, by Friedgut, Rödl and Schacht. In particular, they showed an upper bound of order $n^{-1/m_{k}(F)}$ for the 1-statement, where $m_{k}(F)$ denotes the $k$-density of $F$. Similarly as in the graph case, it is known that the threshold for star-like hypergraphs is given by the appearance of small subgraphs. In this paper we show that another type of threshold exists if $k\geqslant 4$: there are $k$-uniform hypergraphs for which the threshold is determined by the asymmetric Ramsey problem in which a different hypergraph has to be avoided in each colour class. Along the way we obtain a general bound on the 1-statement for asymmetric Ramsey properties in random hypergraphs. This extends the work of Kohayakawa and Kreuter, and of Kohayakawa, Schacht and Spöhel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.

Given a finite group $G$, the generating graph $\unicode[STIX]{x1D6E4}(G)$ of $G$ has as vertices the (nontrivial) elements of $G$ and two vertices are adjacent if and only if they are distinct and generate $G$ as group elements. In this paper we investigate properties about the degrees of the vertices of $\unicode[STIX]{x1D6E4}(G)$ when $G$ is an alternating group or a symmetric group of degree $n$. In particular, we determine the vertices of $\unicode[STIX]{x1D6E4}(G)$ having even degree and show that $\unicode[STIX]{x1D6E4}(G)$ is Eulerian if and only if $n\geqslant 3$ and $n$ and $n-1$ are not equal to a prime number congruent to 3 modulo 4.

The classical Kővári–Sós–Turán theorem states that if G is an n-vertex graph with no copy of Ks,t as a subgraph, then the number of edges in G is at most O(n2−1/s). We prove that if one forbids Ks,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 Kr-free graph with no induced copy of Ks,t. This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.

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.

In this paper, it is proved that the complement of the zero-divisor graph of a partially ordered set is weakly perfect if it has finite clique number, completely answering the question raised by Joshi and Khiste [‘Complement of the zero divisor graph of a lattice’, Bull. Aust. Math. Soc. 89 (2014), 177–190]. As a consequence, the intersection graph of an intersection-closed family of nonempty subsets of a set is weakly perfect if it has finite clique number. These results are applied to annihilating-ideal graphs and intersection graphs of submodules.

An r-uniform hypergraph is called an r-graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear r-graph H and a positive integer n, the linear Turán number exL(n,H) is the maximum number of edges in a linear r-graph G that does not contain H as a subgraph. For each ℓ ≥ 3, let Crℓ denote the r-uniform linear cycle of length ℓ, which is an r-graph with edges e1, . . ., eℓ such that, for all i ∈ [ℓ−1], |ei ∩ ei+1|=1, |eℓ ∩ e1|=1 and ei ∩ ej = ∅ for all other pairs {i,j}, i ≠ j. For all r ≥ 3 and ℓ ≥ 3, we show that there exists a positive constant c = cr,ℓ, depending only r and ℓ, such that exL(n,Crℓ) ≤ cn1+1/⌊ℓ/2⌋. This answers a question of Kostochka, Mubayi and Verstraëte [30]. For even ℓ, our result extends the result of Bondy and Simonovits [7] on the Turán numbers of even cycles to linear hypergraphs.

Using our results on linear Turán numbers, we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants a = am,r and b = bm,r, depending only on m and r, such that

\begin{equation} R(C^r_{2m}, K^r_t)\leq a \Bigl(\frac{t}{\ln t}\Bigr)^{{m}/{(m-1)}} \quad\text{and}\quad R(C^r_{2m+1}, K^r_t)\leq b t^{{m}/{(m-1)}}. \end{equation}

It is proved that every non-trivial Latin square has an upper embedding in a non-orientable surface and every Latin square of odd order has an upper embedding in an orientable surface. In the latter case, detailed results about the possible automorphisms and their actions are also obtained.

Inspired by the recent work of M. Nakasuji, O. Phuksuwan and Y. Yamasaki, we combine interpolated multiple zeta values and Schur multiple zeta values into one object, which we call interpolated Schur multiple zeta values. Our main result will be a Jacobi–Trudi formula for a certain class of these new objects. This generalizes an analogous result for Schur multiple zeta values and implies algebraic relations between interpolated multiple zeta values.

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 ≈ k2. Most of the paper is concerned with the case k = 2. We show that m2 tends to an explicitly defined constant and that μ2 ≈ 4.1704288. . . .

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

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges and $d_{1}\geq d_{2}\geq \cdots \geq d_{n}>0$ its sequence of vertex degrees. If $\unicode[STIX]{x1D707}_{1}\geq \unicode[STIX]{x1D707}_{2}\geq \cdots \geq \unicode[STIX]{x1D707}_{n-1}>\unicode[STIX]{x1D707}_{n}=0$ are the Laplacian eigenvalues of $G$, then the Kirchhoff index of $G$ is $\mathit{Kf}(G)=n\sum _{i=1}^{n-1}\unicode[STIX]{x1D707}_{i}^{-1}$. We prove some new lower bounds for $\mathit{Kf}(G)$ in terms of some of the parameters $\unicode[STIX]{x1D6E5}=d_{1}$, $\unicode[STIX]{x1D6E5}_{2}=d_{2}$, $\unicode[STIX]{x1D6E5}_{3}=d_{3}$, $\unicode[STIX]{x1D6FF}=d_{n}$, $\unicode[STIX]{x1D6FF}_{2}=d_{n-1}$ and the topological index $\mathit{NK}=\prod _{i=1}^{n}d_{i}$.

Bollobás and Scott (Random Struct. Alg.21 (2002) 414–430) asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+o(1))m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+o(1))m edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobás, Krivelevich and Sudakov shows that for infinitely many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4−o(1))m edges in one of the two classes.

We consider community detection in degree-corrected stochastic block models. We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block membership of all but a vanishing fraction of nodes, in the regime where the lowest degree is of order log(n) or higher. Recovery succeeds even for very heterogeneous degree distributions. The algorithm does not rely on parameters as input. In particular, it does not need to know the number of communities.

A random binary search tree grown from the uniformly random permutation of [n] is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction ck of vertices of a fixed rank k ≥ 0 is shown to decay exponentially with k. We prove that the ranks of the uniformly random, fixed size sample of vertices are asymptotically independent, each having the distribution {ck}. Notoriously hard to compute, the exact fractions ck have been determined for k ≤ 3 only. We present a shortcut enabling us to compute c4 and c5 as well; both are ratios of enormous integers, the denominator of c5 being 274 digits long. Prompted by the data, we prove that, in sharp contrast, the largest prime divisor of the denominator of ck is at most 2k+1 + 1. We conjecture that, in fact, the prime divisors of every denominator for k > 1 form a single interval, from 2 to the largest prime not exceeding 2k+1 + 1.

We propose two distance-based topological indices (level index and Gini index) as measures of disparity within a single tree and within tree classes. The level index and the Gini index of a single tree are measures of balance within the tree. On the other hand, the Gini index for a class of random trees can be used as a comparative measure of balance between tree classes. We establish a general expression for the level index of a tree. We compute the Gini index for two random classes of caterpillar trees and see that a random multinomial model of trees with finite height has a countable number of limits in [0, ⅓], whereas a model with independent level numbers fills the spectrum (0, ⅓].

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.

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−1n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + ϵ)pn is O(p−1n)-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 (Combinatorica22 (2002), 591–596). We also show that our results are best possible up to a constant factor.

We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number k, the smallest number m = m(k) such that every digraph can be coloured with m colours where each vertex has the same colour as at most a 1/k proportion of its out-neighbours. We show that m(k) ∈ {2k − 1,2k}. We also prove a result supporting the conjecture that m(2) = 3. Moreover, we prove similar results for a more general concept called majority choosability.