It is a fundamental question in disease modeling how the initial seeding of an epidemic, spreading over a network, determines its final outcome. One important goal has been to find the seed configuration, which infects the most individuals. Although the identified optimal configurations give insight into how the initial state affects the outcome of an epidemic, they are unlikely to occur in real life. In this paper we identify two important seeding scenarios, both motivated by historical data, that reveal a complex phenomenon.

We prove a theorem that can be thought of as a common generalization of the Discrete Nodal Theorem and (one direction of) Cheeger’s Inequality for graphs. A special case of this result will assert that if the second and third eigenvalues of the Laplacian are at least ε apart, then the subgraphs induced by the positive and negative supports of the eigenvector belonging to λ2 are not only connected, but edge-expanders (in a weighted sense, with expansion depending on ε).

We study the distribution of ages in the mean field forest fire model introduced by Ráth and Tóth. This model is an evolving random graph whose dynamics combine Erdős–Rényi edge-addition with a Poisson rain of lightning strikes. All edges in a connected component are deleted when any of its vertices is struck by lightning. We consider the asymptotic regime of lightning rates for which the model displays self-organized criticality. The age of a vertex increases at unit rate, but it is reset to zero at each burning time.

The theory of graph limits is only understood to a somewhat satisfactory degree in the cases of dense graphs and of bounded degree graphs. There is, however, a lot of interest in the intermediate cases. It appears that one of the most important constituents of graph limits in the general case will be Markov spaces (Markov chains on measurable spaces with a stationary distribution). This motivates our goal to extend some important theorems from finite graphs to Markov spaces or, more generally, to measurable spaces.

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths – a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following.

The reconfiguration graph \(R_{k}(G)\) for the \(k\)-colorings of a graph\(~G\) has as vertex set the set of all possible proper \(k\)-colorings of \(G\) and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that if \(G\) is a planar graph with \(n\) vertices, then \(R_{12}(G)\) has diameter at most \(6n\).

Environmental factors, and in particular diet, are known to play a key role in the development of Coronary Heart Disease. Many of these factors were unveiled by detailed nutritional epidemiology studies, focusing on the role of a single nutrient or food at a time.

We prove that if \(G\) is a sparse graph — it belongs to a fixed class of bounded expansion \(C\) — and \(d ∈ N\) is fixed, then the \(d\)th power of \(G\) can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.

For a hereditary class C of graphs, let s_C(n) be the minimum function such that each n-vertex graph in C has a balanced separator of order at most s_C(n), and let nabla_C(r) be the minimum function bounding the expansion of C, in the sense of bounded expansion theory of Nešetřil and Ossona de Mendez. The results of Plotkin, Rao, and Smith (1994) and Esperet and Raymond (2018) imply that if s_C(n)=Theta(n^{1-epsilon}) for some epsilon>0, then nabla_C(r)=Omega(r^{1/(2.epsilon)-1}/polylog r) and nabla_C(r)=O(r^{1/epsilon-1}polylog r).

We call a multigraph non-homotopic if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on \(n>1\) vertices can have arbitrarily many edges.