5 results
Filters
Settings
Now showing1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Twin-width VIIIa: Delineation(Elsevier, 2026-07-31); ; ; ; We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated ) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures D of subclasses of C, FO model checking is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22], permutation graphs [BKTW, JACM ’22] and tournaments [GT, European Journal of Combinatorics ’25] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, directed path graphs with boundedly many roots are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.Publicationtype: Journal Article34 5 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Colourings without monochromatic disjoint pairs(2018-05); ; The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.Publicationtype: Journal Article158 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Counting results for sparse pseudorandom hypergraphs IWe establish a so-called counting lemma that allows embeddings of certain linear uniform hypergraphs into sparse pseudorandom hypergraphs, generalizing a result for graphs (Kohayakawa et al., 2004). Applications of our result are presented in the companion paper (Counting results for sparse pseudorandom hypergraphs II).Publicationtype: Journal Article100 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Counting results for sparse pseudorandom hypergraphs IIWe present a variant of a universality result of Rödl (1986) for sparse, 3-uniform hypergraphs contained in strongly jumbled hypergraphs. One of the ingredients of our proof is a counting lemma for fixed hypergraphs in sparse “pseudorandom” hypergraphs, which is proved in the companion paper (Counting results for sparse pseudorandom hypergraphs I).Publicationtype: Journal Article111 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Ramsey numbers for bipartite graphs with small bandwidth(2015-08-01); ; ; We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.Publicationtype: Journal Article139