In 1987, Alavi, Malde, Schwenk and Erdős conjectured that the independence polynomial of any tree is unimodal. Although it attracts many researchers' attention, it is still open. Motivated by this conjecture, in this paper, we prove that rooted products of some graphs preserve real rootedness of independence polynomials. As application, we not only give a unified proof for some known results, but also we can apply them to generate infinite kinds of trees whose independence polynomials have only real zeros. Thus their independence polynomials are unimodal.

We consider a random graph model that was recently proposed as a model for complex networks by Krioukov et al. (2010). In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has previously been shown that this model has various properties associated with complex networks, including a power-law degree distribution and a strictly positive clustering coefficient. The model is specified using three parameters: the number of nodes N, which we think of as going to infinity, and $\alpha, \nu > 0$, which we think of as constant. Roughly speaking, $\alpha$ controls the power-law exponent of the degree sequence and $\nu$ the average degree. Earlier work of Kiwi and Mitsche (2015) has shown that, when $\alpha \lt 1$ (which corresponds to the exponent of the power law degree sequence being $\lt 3$), the diameter of the largest component is asymptotically almost surely (a.a.s.) at most polylogarithmic in N. Friedrich and Krohmer (2015) showed it was a.a.s. $\Omega(\log N)$ and improved the exponent of the polynomial in $\log N$ in the upper bound. Here we show the maximum diameter over all components is a.a.s. $O(\log N),$ thus giving a bound that is tight up to a multiplicative constant.

Letting ℳ denote the space of finite measures on ℕ, and μλ ∊ ℳ denote the Poisson distribution with parameter λ, the function W : [0, 1]2 → ℳ given by W(x, y) = μc log x log y is called the PAG graphon with density c. It is known that this is the limit, in the multigraph homomorphism sense, of the dense preferential attachment graph (PAG) model with edge density c. This graphon can then in turn be used to generate the so-called W-random graphs in a natural way, and similar constructions also work in the slightly more general context of the so-called PAGκ models. The aim of this paper is to compare these dense PAGκ models with the W-random graph models obtained from the corresponding graphons. Motivated by the multigraph limit theory, we investigate the expected jumble-norm distance of the two models in terms of the number of vertices n. We present a coupling for which the expectation can be bounded from above by O(log3/2n · n−1/2), and provide a universal lower bound that is coupling-independent, but without the logarithmic term.

A new network evolution model is introduced in this paper. The model is based on cooperations of N units. The units are the nodes of the network and the cooperations are indicated by directed links. At each evolution step N units cooperate, which formally means that they form a directed N-star subgraph. At each step either a new unit joins the network and it cooperates with N − 1 old units, or N old units cooperate. During the evolution both preferential attachment and uniform choice are applied. Asymptotic power law distributions are obtained both for in-degrees and for out-degrees.

We couple a multi-type stochastic epidemic process with a directed random graph, where edges have random weights (traversal times). This random graph representation is used to characterise the fractions of individuals infected by the different types of vertices among all infected individuals in the large population limit. For this characterisation, we rely on the theory of multi-type real-time branching processes. We identify a special case of the two-type model in which the fraction of individuals of a certain type infected by individuals of the same type is maximised among all two-type epidemics approximated by branching processes with the same mean offspring matrix.

The accessibility percolation model is investigated on random rooted labeled trees. More precisely, the number of accessible leaves (i.e. increasing paths) Zn and the number of accessible vertices Cn in a random rooted labeled tree of size n are jointly considered in this work. As n → ∞, we prove that (Zn, Cn) converges in distribution to a random vector whose probability generating function is given in an explicit form. In particular, we obtain that the asymptotic distributions of Zn + 1 and Cn are geometric distributions with parameters e/(1 + e) and 1/e, respectively. Much of our analysis is performed in the context of local weak convergence of random rooted labeled trees.

We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are ‘jointly connected’. Bollobás, Riordan, Slivken, and Smith (2017) proved that, when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $\Theta({1}/{(n\ln n)})$. We show that this threshold is sharp, and that it lies at ${1}/{(4n\ln n)}$.

Based on a simple object, an i.i.d. sequence of positive integer-valued random variables {an}n∊ℤ, we introduce and study two random structures and their connections. First, a population dynamics, in which each individual is born at time n and dies at time n + an. This dynamics is that of a D/GI/∞ queue, with arrivals at integer times and service times given by {an}n∊ℤ. Second, the directed random graph Tf on ℤ generated by the random map f(n) = n + an. Assuming only that E [a0] < ∞ and P [a0 = 1] > 0, we show that, in steady state, the population dynamics is regenerative, with one individual alive at each regeneration epoch. We identify a unimodular structure in this dynamics. More precisely, Tf is a unimodular directed tree, in which f(n) is the parent of n. This tree has a unique bi-infinite path. Moreover, Tf splits the integers into two categories: ephemeral integers, with a finite number of descendants of all degrees, and successful integers, with an infinite number. Each regeneration epoch is a successful individual such that all integers less than it are its descendants of some order. Ephemeral, successful, and regeneration integers form stationary and mixing point processes on ℤ.

We provide a deterministic algorithm that finds, in ɛ-O(1)n2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ-O(1) many complete bipartite graphs.

As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛnv(H), in time ɛ-OH(1)n2.

An (improper) graph colouring has defect d if each monochromatic subgraph has maximum degree at most d, and has clustering c if each monochromatic component has at most c vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than (2d+2)/(d+2)k is k-choosable with defect d. This improves upon a similar result by Havet and Sereni (J. Graph Theory, 2006). For clustered choosability of graphs with maximum average degree m, no (1-ɛ)m bound on the number of colours was previously known. The above result with d=1 solves this problem. It implies that every graph with maximum average degree m is $\lfloor{\frac{3}{4}m+1}\rfloor$-choosable with clustering 2. This extends a result of Kopreski and Yu (Discrete Math., 2017) to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree m is $\lfloor{\frac{7}{10}m+1}\rfloor$-choosable with clustering 9, and is $\lfloor{\frac{2}{3}m+1}\rfloor$-choosable with clustering O(m). As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth–moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.

For $G$ a finite non-Abelian group we write $c(G)$ for the probability that two randomly chosen elements commute and $k(G)$ for the largest integer such that any $k(G)$-colouring of $G$ is guaranteed to contain a monochromatic quadruple $(x,y,xy,yx)$ with $xy\neq yx$. We show that $c(G)\rightarrow 0$ if and only if $k(G)\rightarrow \infty$.

We study forcing pairs for quasirandom graphs. Chung, Graham, and Wilson initiated the study of families ${\mathcal{F}}$ of graphs with the property that if a large graph $G$ has approximately homomorphism density $p^{e(F)}$ for some fixed $p\in (0,1]$ for every $F\in {\mathcal{F}}$, then $G$ is quasirandom with density $p$. Such families ${\mathcal{F}}$ are said to be forcing. Several forcing families were found over the last three decades and characterizing all bipartite graphs $F$ such that $(K_{2},F)$ is a forcing pair is a well-known open problem in the area of quasirandom graphs, which is closely related to Sidorenko’s conjecture. In fact, most of the known forcing families involve bipartite graphs only.

We consider forcing pairs containing the triangle $K_{3}$. In particular, we show that if $(K_{2},F)$ is a forcing pair, then so is $(K_{3},F^{\rhd })$, where $F^{\rhd }$ is obtained from $F$ by replacing every edge of $F$ by a triangle (each of which introduces a new vertex). For the proof we first show that $(K_{3},C_{4}^{\rhd })$ is a forcing pair, which strengthens related results of Simonovits and Sós and of Conlon et al.

As usual, $P_{n}$ ($n\geq 1$) denotes the path on $n$ vertices. The gem is the graph consisting of a $P_{4}$ together with an additional vertex adjacent to each vertex of the $P_{4}$. A graph is called ($P_{5}$, gem)-free if it has no induced subgraph isomorphic to a $P_{5}$ or to a gem. For a graph $G$, $\unicode[STIX]{x1D712}(G)$ denotes its chromatic number and $\unicode[STIX]{x1D714}(G)$ denotes the maximum size of a clique in $G$. We show that $\unicode[STIX]{x1D712}(G)\leq \lfloor \frac{3}{2}\unicode[STIX]{x1D714}(G)\rfloor$ for every ($P_{5}$, gem)-free graph $G$.

The strong chromatic number χs(G) of a graph G on n vertices is the least number r with the following property: after adding $r\lceil n/r\rceil-n$ isolated vertices to G and taking the union with any collection of spanning disjoint copies of Kr in the same vertex set, the resulting graph has a proper vertex colouring with r colours. We show that for every c > 0 and every graph G on n vertices with Δ(G) ≥ cn, χs(G) ≤ (2+o(1))Δ(G), which is asymptotically best possible.

We prove the following 30 year-old conjecture of Győri and Tuza: the edges of every n-vertex graph G can be decomposed into complete graphs C1,. . .,Cℓ of orders two and three such that |C1|+···+|Cℓ| ≤ (1/2+o(1))n2. This result implies the asymptotic version of the old result of Erdős, Goodman and Pósa that asserts the existence of such a decomposition with ℓ ≤ n2/4.

We prove a lower bound on the difference between the spectral radius of the Cayley graph of a group $G$ and the spectral radius of the Schreier graph $H\backslash G$ for any subgroup $H$. As an application, we extend Kesten’s theorem on spectral radii to uniformly recurrent subgroups and give a short proof that the result of Lyons and Peres on cycle density in Ramanujan graphs [Lyons and Peres. Cycle density in infinite Ramanujan graphs. Ann. Probab.43(6) (2015), 3337–3358, Theorem 1.2] holds on average. More precisely, we show that if ${\mathcal{G}}$ is an infinite deterministic Ramanujan graph then the time spent in short cycles by a random trajectory of length $n$ is $o(n)$.

Let $G$ be a finite group and let $\text{Irr}(G)$ be the set of all irreducible complex characters of $G$. Let $\unicode[STIX]{x1D70C}(G)$ be the set of all prime divisors of character degrees of $G$. The character degree graph $\unicode[STIX]{x1D6E5}(G)$ associated to $G$ is a graph whose vertex set is $\unicode[STIX]{x1D70C}(G)$, and there is an edge between two distinct primes $p$ and $q$ if and only if $pq$ divides $\unicode[STIX]{x1D712}(1)$ for some $\unicode[STIX]{x1D712}\in \text{Irr}(G)$. We prove that $\unicode[STIX]{x1D6E5}(G)$ is $k$-regular for some natural number $k$ if and only if $\overline{\unicode[STIX]{x1D6E5}}(G)$ is a regular bipartite graph.

A tree functional is called additive if it satisfies a recursion of the form $F(T) = \sum_{j=1}^k F(B_j) + f(T)$, where B1, …, Bk are the branches of the tree T and f (T) is a toll function. We prove a general central limit theorem for additive functionals of d-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalized plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of d-ary increasing trees, but other examples (old and new) are covered as well.

We study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a vertex of degree 2, the fire gets directly passed on to the neighbouring edge; a vertex of degree at least 3, however, passes the fire either to all of its neighbours or none, each with probability ${\textstyle{1 \over 2}}$. If the fire goes out before the whole network is burnt, we again set fire to a uniform point. We are interested in the number of fires which must be set in order to burn the whole network, and the number of points which are burnt from two different directions. We analyse these quantities for a random multigraph having n vertices of degree 3 and α(n) vertices of degree 4, where α(n)/n → 0 as n → ∞, with independent and identically distributed standard exponential edge lengths. Depending on whether $\alpha(n) \gg \sqrt{n}$ or $\alpha(n)=O(\sqrt{n})$, we prove that, as n → ∞, these quantities converge jointly in distribution when suitably rescaled to either a pair of constants or to (complicated) functionals of Brownian motion. We use our analysis of this model to make progress towards a conjecture of Aronson, Frieze and Pittel (1998) concerning the number of vertices which remain unmatched when we use the Karp–Sipser algorithm to find a matching on the Erdős–Rényi random graph.

For an edge-coloured graph G, the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V(G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen’s conjecture in digraphs.