EPSRC Reference: 
EP/X013642/1 
Title: 
DMSEPSRC INDUCED SUBGRAPHS AND GRAPH STRUCTURE 
Principal Investigator: 
Scott, Professor AD 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematical Institute 
Organisation: 
University of Oxford 
Scheme: 
Standard Research  NR1 
Starts: 
01 August 2022 
Ends: 
31 July 2027 
Value (£): 
364,473

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
There are two natural ways to describe the local structure of a graph or network: by asking what graphs occur as minors, and by asking what graphs occur as induced subgraphs. The theory of graph minors was developed by Robertson and Seymour in an influential series of papers, and gives a very satisfactory picture. However,
the picture for induced subgraphs is more complex and much less is known.
A central problem in the field is the ErdosHajnal conjecture. It has been known since the results of Ramsey and of Erdos and of Szekeres in the 1930s that every graph has a clique or stable set of size at least logarithmic in the number of vertices. However, Erdos and Hajnal conjectured in the 1980s that forbidding any induced subgraph H causes a dramatic jump, resulting in cliques or stable sets of polynomial size. Recently the PI's (joint with two others) settled the smallest open case, which had been a famous question since the problem was first proposed in the 1980's; and even more recently they have made substantial progress on the next smallest case. These two steps both used new techniques, and it is hoped that these techniques will lead to further progress on this and related problems.
More broadly, what is the structure that results when some graph H is excluded as an induced subgraph? We don't expect to get a structure that is necessary and sufficient for excluding a graph H, when H is large (this already seems hopeless for graphs H with six vertices); but it is more likely that there is a structure that is necessary for excluding H and sufficient for excluding some larger graph. This would be the first step towards a general structural theory for induced subgraphs.
The aim of this proposal is to spend a period of focused collaboration, to work on the ErdosHajnal conjecture and related problems, and to build new tools for understanding the structure of graphs with forbidden induced subgraphs. The proposal builds on a substantial existing collaborationbetween the PIs, who have written more than 45 papers together in the last few years. The grant will give them time and resources for a further period of intense collaboration, to drive further progress in this area.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.ox.ac.uk 