From the 1 of 7 linked papers with an AI index.
7 papers
Far-apart ErdÅs--Pósa property of long cycles
Maria Chudnovsky, Vida DujmoviÄ, Gwenaël Joret +4
The authors prove that for any graph, either it contains many cycles of length at least ℓ that are pairwise far apart, or a small vertex set can be removed to eliminate all such lo…
Induced subgraph density. IV. New graphs with the ErdÅs-Hajnal property
Tung Nguyen, Alex Scott, Paul Seymour
ErdÅs and Hajnal conjectured that for every graph , there exists such that every -free graph has a clique or a stable set of size at least (a graph is -…
Short reachability networks
Carla Groenland, Tom Johnston, Jamie Radcliffe +1
We investigate the following generalisation of permutation networks. We say a sequence of transpositions in forms a -reachability network if, for ev…
Shotgun assembly of random graphs
Tom Johnston, Gal Kronenberg, Alexander Roberts +1
In the graph shotgun assembly problem, we are given the balls of radius around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…
Improved bounds for 1-independent percolation on
Paul Balister, Tom Johnston, Michael Savery +1
A 1-independent bond percolation model on a graph is a probability distribution on the spanning subgraphs of in which, for all vertex-disjoint sets of edges and …
A multidimensional Ramsey Theorem
António Girão, Gal Kronenberg, Alex Scott
Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is stil…