The extremal function of a graph is the supremum of densities of graphs not containing as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) …
The Alon-Jaeger-Tarsi conjecture states that for any finite field of size at least 4 and any nonsingular matrix over there exists a vector such that neither nor has a 0 component. In joint work with János Nagy we proved this conjecture when the size of the field is sufficiently …
I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time , where and denote the numbers of vertices and edges, respectively. This improves the -time algorithm for this problem on unit disk …
The Gyárfás-Sumner conjecture says that for every forest , there is a function such that the chromatic number is at most for every -free graph ("-free" means with no induced subgraph isomorphic to , and is the size of the largest clique of ). This well-known conjecture has been proved only for a …
Majority dynamics on a graph is a deterministic process such that every vertex updates its -assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph , the random initial -assignment converges to a -agreement with high …
The aim of the Young Researchers in Extremal and Probabilistic Combinatorics is to bring together early career researchers working on these topics. The workshop will consist of several 25 minute talks across three days from October 20 to 22, 2021. Due to Covid the workshop will be held online. Invited Speakers & Program Oct. 20 …
Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a -graphic delta-matroid for an abelian group , which generalizes a graphic delta-matroid. For an abelian group , a -labelled graph is a graph whose …
A family of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from has a common element, and moreover, no set can be added to while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a …
The independence number of a tree decomposition of a graph is the smallest integer such that each bag of induces a subgraph with independence number at most . If a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can …
