We discuss 1-factorizations of complete graphs that “match” a given Hadamard matrix. We prove the existence of these factorizations for two families of Hadamard matrices: Walsh matrices and certain Paley matrices.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. Alon et al. [‘Maximum cuts and judicious partitions in graphs without short cycles’, J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$, there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$.

We investigate how the Minkowski sum of two polytopes affects their graph and, in particular, their diameter. We show that the diameter of the Minkowski sum is bounded below by the diameter of each summand and above by, roughly, the product between the diameter of one summand and the number of vertices of the other. We also prove that both bounds are sharp. In addition, we obtain a result on polytope decomposability. More precisely, given two polytopes $P$ and $Q$, we show that $P$ can be written as a Minkowski sum with a summand homothetic to $Q$ if and only if $P$ has the same number of vertices as its Minkowski sum with $Q$.

We show that a coupling of non-colliding simple random walkers on the complete graph on n vertices can include at most n - log n walkers. This improves the only previously known upper bound of n - 2 due to Angel, Holroyd, Martin, Wilson and Winkler (Electron. Commun. Probab.18 (2013)). The proof considers couplings of i.i.d. sequences of Bernoulli random variables satisfying a similar avoidance property, for which there is separate interest.

We discuss percolation and random walks in a class of homogeneous ultrametric spaces together with similarities and differences in ultrametric and Euclidean spaces. We briefly outline the role of these models in the study of interacting systems. Several open problems are presented.

In this paper we consider the degree-wise effect of a second step for a random walk on a graph. We prove that under the configuration model, for any fixed degree sequence the probability of exceeding a given degree threshold is smaller after two steps than after one. This builds on recent work of Kramer et al. (2016) regarding the friendship paradox under random walks.

We extend the work of Antunović et al. (2016) on competing types in preferential attachment models to include cases where the types have different fitnesses, which may be either multiplicative or additive. We show that, depending on the values of the parameters of the models, there are different possible limiting behaviours depending on the zeros of a certain function. In particular, we show the existence of choices of the parameters where one type is favoured both by having higher fitness and by the type of attachment mechanism, but the other type has a positive probability of dominating the network in the limit.

We investigate the domination game and the game domination number $\unicode[STIX]{x1D6FE}_{g}$ in the class of split graphs. We prove that $\unicode[STIX]{x1D6FE}_{g}(G)\leq n/2$ for any isolate-free $n$-vertex split graph $G$, thus strengthening the conjectured $3n/5$ general bound and supporting Rall’s $\lceil n/2\rceil$-conjecture. We also characterise split graphs of even order with $\unicode[STIX]{x1D6FE}_{g}(G)=n/2$.

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.

Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have $\mathbb{P}({A_{n,\alpha}}) \to {\sqrt{1-2\alpha}}/{(1-\alpha})$, whereas if α > 1/2 we have $\mathbb{P}({A_{n,\alpha}}) \to 0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that $\mathbb{E}{[X]}$ undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions.

Denote by ${\mathcal H}_k$(n, p) the random k-graph in which each k-subset of {1,. . .,n} is present with probability p, independent of other choices. More or less answering a question of Balogh, Bohman and Mubayi, we show: there is a fixed ε > 0 such that if n = 2k + 1 and p > 1 - ε, then w.h.p. (that is, with probability tending to 1 as k → ∞), ${\mathcal H}_k$(n, p) has the ‘Erdős–Ko–Rado property’. We also mention a similar random version of Sperner's theorem.

We study the automorphism groups of countable homogeneous directed graphs (and some additional homogeneous structures) from the point of view of topological dynamics. We determine precisely which of these automorphism groups are amenable (in their natural topologies). For those which are amenable, we determine whether they are uniquely ergodic, leaving unsettled precisely one case (the ‘semi-generic’ complete multipartite directed graph). We also consider the Hrushovski property. For most of our results we use the various techniques of Angel et al [Random orderings and unique ergodicity of automorphism groups. J. Eur. Math. Soc., 16 (2014), 2059–2095], suitably generalized to a context in which the universal minimal flow is not necessarily the space of all orders. Negative results concerning amenability rely on constructions of the type considered in Zucker [Amenability and unique ergodicity of automorphism groups of Fraïssé structures. Fund. Math., 226 (2014), 41–61]. An additional class of structures (compositions) may be handled directly on the basis of very general principles. The starting point in all cases is the determination of the universal minimal flow for the automorphism group, which in the context of countable homogeneous directed graphs is given in Jasiński et al [Ramsey precompact expansions of homogeneous directed graphs. Electron. J. Combin., 21(4), (2014), 31] and the papers cited therein.

A class of graphs is bridge-addable if given a graph $G$ in the class, any graph obtained by adding an edge between two connected components of $G$ is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if ${\mathcal{G}}$ is bridge-addable and $G_{n}$ is a uniform $n$-vertex graph from ${\mathcal{G}}$, then $G_{n}$ is connected with probability at least $(1+o_{n}(1))e^{-1/2}$. The constant $e^{-1/2}$ is best possible, since it is reached for the class of all forests.

In this paper, we prove a form of uniqueness in this statement: if ${\mathcal{G}}$ is a bridge-addable class and the random graph $G_{n}$ is connected with probability close to $e^{-1/2}$, then $G_{n}$ is asymptotically close to a uniform $n$-vertex random forest in a local sense. For example, if the probability converges to $e^{-1/2}$, then $G_{n}$ converges in the sense of Benjamini–Schramm to the uniformly infinite random forest $F_{\infty }$. This result is reminiscent of so-called “stability results” in extremal graph theory, the difference being that here the stable extremum is not a graph but a graph class.

This paper studies the friendship paradox for weighted and directed networks, from a probabilistic perspective. We consolidate and extend recent results of Cao and Ross and Kramer, Cutler and Radcliffe, to weighted networks. Friendship paradox results for directed networks are given; connections to detailed balance are considered.

We study the chromatic number of the curve graph of a surface. We show that the chromatic number grows like $k\log k$ for the graph of separating curves on a surface of Euler characteristic $-k$. We also show that the graph of curves that represent a fixed nonzero homology class is uniquely $t$-colorable, where $t$ denotes its clique number. Together, these results lead to the best known bounds on the chromatic number of the curve graph. We also study variations for arc graphs and obtain exact results for surfaces of low complexity. Our investigation leads to connections with Kneser graphs, the Johnson homomorphism, and hyperbolic geometry.

Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.

The Holme‒Kim random graph process is a variant of the Barabási‒Álbert scale-free graph that was designed to exhibit clustering. In this paper we show that whether the model does indeed exhibit clustering depends on how we define the clustering coefficient. In fact, we find that the local clustering coefficient typically remains positive whereas global clustering tends to 0 at a slow rate. These and other results are proven via martingale techniques, such as Freedman's concentration inequality combined with a bootstrapping argument.

We use the Stein‒Chen method to obtain compound Poisson approximations for the distribution of the number of subgraphs in a generalised stochastic block model which are isomorphic to some fixed graph. This model generalises the classical stochastic block model to allow for the possibility of multiple edges between vertices. We treat the case that the fixed graph is a simple graph and that it has multiple edges. The former results apply when the fixed graph is a member of the class of strictly balanced graphs and the latter results apply to a suitable generalisation of this class to graphs with multiple edges. We also consider a further generalisation of the model to pseudo-graphs, which may include self-loops as well as multiple edges, and establish a parameter regime in the multiple edge stochastic block model in which Poisson approximations are valid. The results are applied to obtain Poisson and compound Poisson approximations (in different regimes) for subgraph counts in the Poisson stochastic block model and degree corrected stochastic block model of Karrer and Newman (2011).

One model of real-life spreading processes is that of first-passage percolation (also called the SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with independent and identically distributed heavy-tailed passage times on edges. On the other hand, random graphs are often locally tree-like, and spreading on trees with leaves might be very slow due to bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power-law distribution ℙ(ξ>t)∼t-α with infinite mean. For any finite connected graph G with a root s, we find the largest number of vertices κ(G,s) that are infected in finite expected time, and prove that for every k≤κ(G,s), the expected time to infect k vertices is at most O(k1/α). Then we show that adding a single edge from s to a random vertex in a random tree 𝒯 typically increases κ(𝒯,s) from a bounded variable to a fraction of the size of 𝒯, thus severely accelerating the process. We examine this acceleration effect on some natural models of random graphs: critical Galton--Watson trees conditioned to be large, uniform spanning trees of the complete graph, and on the largest cluster of near-critical Erdős‒Rényi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.

A filling of a closed hyperbolic surface is a set of simple closed geodesics whose complement is a disjoint union of hyperbolic polygons. The systolic length is the length of a shortest essential closed geodesic on the surface. A geodesic is called systolic, if the systolic length is realised by its length. For every $g\geq 2$, we construct closed hyperbolic surfaces of genus $g$ whose systolic geodesics fill the surfaces with complements consisting of only two components. Finally, we remark that one can deform the surfaces obtained to increase the systole.