Local-Global Interactions in Combinatorics
Lead Research Organisation:
University of Oxford
Department Name: Mathematical Institute
Abstract
A fundamental question in many parts of the mathematical sciences is how local and global structure interact. For instance, what can we say about the local structures of a large, complicated network? How is global structure constrained by what we see locally? Problems of this type arise in many areas, including for example model theory, geometric group theory, topology, combinatorics, computer science, statistical physics, biology, probability, network science, and data analysis. Practical examples include DNA sequencing, where fragments of a genetic sequence need to be assembled to a global sequence, and problems in big data, where the global structure is too large to access directly and its properties must be inferred from 'local' information.
The aim of this research is to address fundamental questions about the relationship between local and global structure in graphs and networks. This will generate new theory and new structural understanding, as well as leading to new insights into the analysis of algorithms.
The aim of this research is to address fundamental questions about the relationship between local and global structure in graphs and networks. This will generate new theory and new structural understanding, as well as leading to new insights into the analysis of algorithms.
People |
ORCID iD |
| Alexander Scott (Principal Investigator) |
Publications
Axenovich M
(2024)
A note on interval colourings of graphs
in European Journal of Combinatorics
Balister P
(2022)
Counting partitions of Gn,1/2$$ {G}_{n,1/2} $$ with degree congruence conditions
in Random Structures & Algorithms
Balister P
(2022)
A Note on Infinite Antichain Density
in SIAM Journal on Discrete Mathematics
Balister P
(2021)
A note on infinite antichain density
Blanco P
(2024)
On tree decompositions whose trees are minors
in Journal of Graph Theory
Campbell R
(2023)
Product structure of graph classes with bounded treewidth
in Combinatorics, Probability and Computing
Chudnovsky M
(2023)
Strengthening Rödl's theorem
in Journal of Combinatorial Theory, Series B
Chudnovsky M
(2024)
Bipartite graphs with no K6 minor
in Journal of Combinatorial Theory, Series B
Chudnovsky M
(2023)
Polynomial bounds for chromatic number VII. Disjoint holes
in Journal of Graph Theory
Chudnovsky M
(2023)
Erdos-Hajnal for graphs with no 5-hole
in Proceedings of the London Mathematical Society
| Description | The award has led to a huge body of research, spread across more than fifty research papers. The unifying theme through this research is the relationship between local and global structure: how is global complexity felt on the local scale? Problems of this type lead to a variety of fundamental mathematical questions. The work supported by the award addresses a broad range of these questions in the context of graphs and networks. A central series of papers concerns the topic of graph colouring; indeed, one of the initial motivations of this research was a sequence of conjectures concerning the "local" structure of networks that are complicated on a large scale. In a sequence of breakthrough papers with Paul Seymour and others, these conjectures have been resolved, and there is now a much clearer theoretical picture of the relationship between local and global structure. |
| Exploitation Route | The work funded by this award has been extensively cited, and presented in many conferences and seminars. There has been a very substantial impact in the area of graph colouring, where it has opened up new questions and areas of investigation, as well as impact in Ramsey theory and on the Erdos-Hajnal Conjecture. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| Description | An extremely large body of research came out of this grant. The breakthroughs on graph colouring have changed the field, and led to new lines of research; as well as resolving some well-known conjectures, this work has opened up a new area of work on polynomial bounds in graph colouring and related problems. The papers on "pure pairs" have heavily impacted subsequent work in Ramsey Theory, and particularly on the Erdos-Hajnal Conjecture, where the spectacular recent progress has its roots in work funded by this award. As a whole, the work is spread across a broad area of extremal, structural and probabilistic combinatorics, and has been heavily cited. |
| First Year Of Impact | 2022 |
| Description | Active clustering |
| Organisation | Nokia |
| Department | Nokia Bell Labs |
| Country | United States |
| Sector | Private |
| PI Contribution | Academic expertise and ideas |
| Collaborator Contribution | Academic and programming expertise and ideas |
| Impact | Quentin Lutz, Élie de Panafieu, Alex Scott and Maya Stein, Active clustering for labeling training data, NeurIPS 2021, |
| Start Year | 2021 |
| Description | Active clustering |
| Organisation | University of Chile |
| Country | Chile |
| Sector | Academic/University |
| PI Contribution | Academic expertise and ideas |
| Collaborator Contribution | Academic and programming expertise and ideas |
| Impact | Quentin Lutz, Élie de Panafieu, Alex Scott and Maya Stein, Active clustering for labeling training data, NeurIPS 2021, |
| Start Year | 2021 |
| Description | Collaboration with Paul Seymour |
| Organisation | Princeton University |
| Country | United States |
| Sector | Academic/University |
| PI Contribution | Research expertise and ideas |
| Collaborator Contribution | Research expertise and ideas |
| Impact | Alex Scott, Paul Seymour and Sophie Spirkl, Polynomial bounds for chromatic number. II. Excluding a star-forest, Journal of Graph Theory, to appear |
| Start Year | 2021 |
| Description | Collaboration with Paul Seymour |
| Organisation | University of Waterloo |
| Country | Canada |
| Sector | Academic/University |
| PI Contribution | Research expertise and ideas |
| Collaborator Contribution | Research expertise and ideas |
| Impact | Alex Scott, Paul Seymour and Sophie Spirkl, Polynomial bounds for chromatic number. II. Excluding a star-forest, Journal of Graph Theory, to appear |
| Start Year | 2021 |
| Description | Paul Balister |
| Organisation | University of Oxford |
| Department | Mathematical Institute Oxford |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | Academic expertise and ideas (this is joint work with another member of the Mathematical Institute in Oxford who is not funded by this grant) |
| Collaborator Contribution | Academic expertise and ideas |
| Impact | Balister P, Powierski E, Scott A, Tan J, (2022). A Note on Infinite Antichain Density. SIAM Journal on Discrete Mathematics, |
| Start Year | 2021 |
| Description | Banff meeting on New Perspectives in Colouring and Structure |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | Organizer for a five-day workshop under the auspices of The Banff International Research Station and UBCO. This was held online, due to travel restrictions. |
| Year(s) Of Engagement Activity | 2021 |
| URL | http://www.birs.ca/events/2021/5-day-workshops/21w5513 |
| Description | Oberwolfach workshop on Graph Theory |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | Organizer for the Oberwolfach workshop 2201 Graph Theory in January 2022. The meeting ran hybride, as UK participants (among others) were not able to enter Germany at this point. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://www.mfo.de/occasion/2201/www_view |
| Description | Round the World Relay in Combinatorics |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | Alex Scott set up and ran an online "round-the world relay" in Combinatorics, with talks in consecutive hours from 21 different groups from Australia to Alaska. The aim was to reinforce international connections and a sense of community at a time when few people were able to travel. The event attracted more than 500 participants spread through the day, and the talks were recorded, edited and posted on youtube. |
| Year(s) Of Engagement Activity | 2021 |
| URL | http://people.maths.ox.ac.uk/scott/relay.htm |