Skip to main content
x

Longer-term seeding effects on epidemic processes: a network approach

Gergely Ódor, Domonkos Czifra, Júlia Komjáthy, László Lovász, Márton Karsai
2022-03-26
In this paper we touch upon three phenomena observed in real life as well as in simulations; in one case, we state mathematical results about the appearance of the phenomenon on arbitrary graphs (networks) under rather general conditions. We discuss a phenomenon of critical fluctuations, demonstrating that an epidemic can behave very differently even if it runs on the same network, with the same transmission probabilities and started from the same initial seeds.

Twin-width and generalized coloring numbers

Jan Dreier, Jakub Gajarský, Yiting Jiangc, Patrice Ossona de Mendez, Jean-Florent Raymond
2021-11-28
In Twin-width and generalized coloring numbers paper, we prove that a graph \(G\) with no \(K\, s,s\,\)-subgraph and twin-width \(d\) has \(r\)-admissibility and \(r\)-coloring numbers bounded from above by an exponential function of \(r\) and that we can construct graphs achieving such a dependency in \(r\).

Towards solving the 7-in-a-row game

Domonkos Czifra, Endre Csóka, Zsolt Zombori, Géza Makay
2021-11-17

Our paper explores the game theoretic value of the 7-in-a-row game. We reduce the problem to solving a finite board game, which we target using Proof Number Search. We present a number of heuristic improvements to Proof Number Search and examine their effect within the context of this particular game. Although our paper does not solve the 7-in-a-row game, our experiments indicate that we have made significant progress towards it.

Switchover phenomenon induced by epidemic seeding on geometric networks

Gergely Ódor, Domonkos Czifra, Júlia Komjáthy, László Lovász, Márton Karsai
2021-10-12

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.

Age evolution in the mean field forest fire model via multitype branching processes

Edward Crane, Balázs Ráth, Dominic Yeo
2021-05-13

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.

Flows on measurable spaces

László Lovász
2021-05-08

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 of graphs with low complexity: The case of classes with bounded linear rankwidth

Jaroslav Nešetřil, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz
2021-01-04

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.

An update on reconfiguring 10-colorings of planar graphs

Zdeněk Dvořák, Carl Feghali
2020-12-24

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\).

A systematic comprehensive longitudinal evaluation of dietary factors associated with acute myocardial infarction and fatal coronary heart disease

Albert-László Barabási, Soodabeh Milanlouei, Giulia Menichetti, Yanping Li, Joseph Loscalzo, Walter C. Willett
2020-11-27

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.

Clustering Powers of Sparse Graphs

Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Xuding Zhu
2020-10-30

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.