Substructures in large graphs and hypergraphs
Lead Research Organisation:
London School of Economics and Political Science
Department Name: Mathematics
Abstract
In this project, we seek to understand the fundamental mathematical properties of discrete structures. In particular, we study graphs, which are collections of vertices, together with a set of unordered pairs of vertices called edges. Graphs are used to model transportation networks, social networks, large data sets, and more, and as such, a deeper understanding of their fundamental properties is beneficial to a wide variety of their applications.
This project falls within the area of Extremal Graph Theory, in which one major direction concerns the minima and maxima of graph parameters among graphs avoiding a certain substructure. This project considers this type of problems, where the substructure is a large set of edge-disjoint or vertex-disjoint copies of a prescribed small or sparse graph; these are known in the area as packing and tiling problems, respectively. For example, part of this project seeks to understand what is the maximum number of triangles which can be packed edge-disjointly in a graph with a given density of edges.
A second part of this project concerns a well-known conjecture of Jackson (c. 1980) on packing Hamilton cycles in bipartite oriented graphs. An oriented graph is obtained from a graph by specifying an orientation for each edge, and a Hamilton cycle is a cyclic ordering of the vertices such that every two consecutive vertices are connected by an edge. It was recently shown that every regular orientation of the complete graph can be decomposed into such Hamilton cycles. We seek to prove Jackson's conjecture, which is a natural bipartite analogue of this result, as well as investigate a related conjecture of Kuhn and Osthus on tripartite graphs.
Finally, a significant portion of this project is dedicated to investigating the maximum edge-density in a uniformly dense hypergraph which avoids a fixed subhypergraph. Hypegraphs are a natural generalisation of graphs, which allows for the modelling of relationships among more than two objects. In particular, their edge set consists of subsets of vertices whose size is not necessarily two. We seek to understand, in a certain family of pseudorandom hypegraphs, what edge density forces the emergence of a given subhypergraph.
This project falls within the area of Extremal Graph Theory, in which one major direction concerns the minima and maxima of graph parameters among graphs avoiding a certain substructure. This project considers this type of problems, where the substructure is a large set of edge-disjoint or vertex-disjoint copies of a prescribed small or sparse graph; these are known in the area as packing and tiling problems, respectively. For example, part of this project seeks to understand what is the maximum number of triangles which can be packed edge-disjointly in a graph with a given density of edges.
A second part of this project concerns a well-known conjecture of Jackson (c. 1980) on packing Hamilton cycles in bipartite oriented graphs. An oriented graph is obtained from a graph by specifying an orientation for each edge, and a Hamilton cycle is a cyclic ordering of the vertices such that every two consecutive vertices are connected by an edge. It was recently shown that every regular orientation of the complete graph can be decomposed into such Hamilton cycles. We seek to prove Jackson's conjecture, which is a natural bipartite analogue of this result, as well as investigate a related conjecture of Kuhn and Osthus on tripartite graphs.
Finally, a significant portion of this project is dedicated to investigating the maximum edge-density in a uniformly dense hypergraph which avoids a fixed subhypergraph. Hypegraphs are a natural generalisation of graphs, which allows for the modelling of relationships among more than two objects. In particular, their edge set consists of subsets of vertices whose size is not necessarily two. We seek to understand, in a certain family of pseudorandom hypegraphs, what edge density forces the emergence of a given subhypergraph.
Organisations
- London School of Economics and Political Science (Fellow, Lead Research Organisation)
- UNIVERSITY OF OXFORD (Collaboration)
- QUEEN MARY UNIVERSITY OF LONDON (Collaboration)
- Universidade de São Paulo (Collaboration)
- London School of Economics and Political Science (University of London) (Collaboration)
- Hamburg University of Technology (Collaboration)
- The Open University (Collaboration)
- ETH Zurich (Collaboration)
- University of Warwick (Collaboration)
Publications
Bowtell Candida
(2023)
Universality for transversal Hamilton cycles
in arXiv e-prints
Pehova Yanitsa
(2023)
Embedding loose spanning trees in 3-uniform hypergraphs
in arXiv e-prints
| Description | Research collaboration with Kalina Petrova (ETH Zurich) |
| Organisation | ETH Zurich |
| Department | Department of Computer Science |
| Country | Switzerland |
| Sector | Academic/University |
| PI Contribution | PI Y Pehova contributed to joint work on project "Minimum vertex degree conditions for loose spanning trees in 3-graphs". The collaboration was initiated during this visit. |
| Collaborator Contribution | K Petrova contributed to joint work on project "Minimum vertex degree conditions for loose spanning trees in 3-graphs". The collaboration was initiated during this visit. K Petrova also gave a seminar talk at LSE on a different topic from her research portfolio. |
| Impact | Pre-print of a paper titled "Minimum vertex degree conditions for loose spanning trees in 3-graphs" (published on arXiv https://arxiv.org/abs/2301.09630). The paper is undergoing final edits before publication. An extended abstract will be submitted and presented at one of the major conferences in the area, EuroComb, in August 2023. |
| Start Year | 2022 |
| Description | Research collaboration with Katherine Staden (Open University), Emil Powiersky (University of Oxford), Pranshu Gupta (Hamburg) |
| Organisation | Hamburg University of Technology |
| Country | Germany |
| Sector | Academic/University |
| PI Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Collaborator Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Impact | Research collaboration on the Erdos-Rotschild problem with forbidden bicoloured triangles. This joint work was started at a workshop Young Researchers in Combinatorics organised by PI Yani Pehova. This partnership is likely to lead to a journal publication. |
| Start Year | 2022 |
| Description | Research collaboration with Katherine Staden (Open University), Emil Powiersky (University of Oxford), Pranshu Gupta (Hamburg) |
| Organisation | Open University |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Collaborator Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Impact | Research collaboration on the Erdos-Rotschild problem with forbidden bicoloured triangles. This joint work was started at a workshop Young Researchers in Combinatorics organised by PI Yani Pehova. This partnership is likely to lead to a journal publication. |
| Start Year | 2022 |
| Description | Research collaboration with Katherine Staden (Open University), Emil Powiersky (University of Oxford), Pranshu Gupta (Hamburg) |
| Organisation | University of Oxford |
| Department | Mathematical Institute Oxford |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Collaborator Contribution | Joint work on the Erdos-Rotschild problem with forbidden bicoloured triangles |
| Impact | Research collaboration on the Erdos-Rotschild problem with forbidden bicoloured triangles. This joint work was started at a workshop Young Researchers in Combinatorics organised by PI Yani Pehova. This partnership is likely to lead to a journal publication. |
| Start Year | 2022 |
| Description | Research collaboration with Matias Pavez-Signe |
| Organisation | University of Warwick |
| Department | Warwick Mathematics Institute |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | PI Yani Pehova contributed to joint research project "Rainbow Hamilton cycles". The collaboration was initiated during the visit. |
| Collaborator Contribution | Dr M Pavez-Signe contributed to joint research project "Rainbow Hamilton cycles". The collaboration was initiated during the visit. Dr Pavez-Signe also gave a research talk at LSE on a different topic from his research portfolio. |
| Impact | We generated ideas for determining the threshold for the existence of rainbow Hamilton cycles in locally bounded colourings of the Erdos-Renyi random graph G(n,p). The collaboration will continue during a scheduled workshop at University of Warwick in summer 2023. |
| Start Year | 2022 |
| Description | Research collaboration with Viresh Patel (Queen Mary, University of London), Jozef Skokan, Francesco Di-Braccio, Joanna Lada (LSE) |
| Organisation | London School of Economics and Political Science (University of London) |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | PI Yani Pehova contributed to joint work on project "Hamilton decompositions of tripartite oriented graphs". The project topic was suggested by PI Y Pehova to Dr V Patel (QMUL) during a 2-day research workshop organised by QMUL in November 2022. The topic attracted other participants and a promising collaboration was formed between QMUL and LSE. |
| Collaborator Contribution | Dr Viresh Patel (QMUL), Prof Jozef Skokan (LSE), Francesco Di-Braccio (PhD student, LSE), Joanna Lada (PhD student, LSE) contributed to joint work on project "Hamilton decompositions of tripartite oriented graphs". The previous expertise on this topic of Dr Viresh Patel was central to resolving initial questions on the topic. |
| Impact | We generated promising ideas on existence of complete and partial Hamilton decompositions in tripartite oriented and directed graphs. We resolved initial questions on decompositions in directed graphs and showed the existence of approximate decompositions in the oriented setting. This is ongoing work. |
| Start Year | 2022 |
| Description | Research collaboration with Viresh Patel (Queen Mary, University of London), Jozef Skokan, Francesco Di-Braccio, Joanna Lada (LSE) |
| Organisation | Queen Mary University of London |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | PI Yani Pehova contributed to joint work on project "Hamilton decompositions of tripartite oriented graphs". The project topic was suggested by PI Y Pehova to Dr V Patel (QMUL) during a 2-day research workshop organised by QMUL in November 2022. The topic attracted other participants and a promising collaboration was formed between QMUL and LSE. |
| Collaborator Contribution | Dr Viresh Patel (QMUL), Prof Jozef Skokan (LSE), Francesco Di-Braccio (PhD student, LSE), Joanna Lada (PhD student, LSE) contributed to joint work on project "Hamilton decompositions of tripartite oriented graphs". The previous expertise on this topic of Dr Viresh Patel was central to resolving initial questions on the topic. |
| Impact | We generated promising ideas on existence of complete and partial Hamilton decompositions in tripartite oriented and directed graphs. We resolved initial questions on decompositions in directed graphs and showed the existence of approximate decompositions in the oriented setting. This is ongoing work. |
| Start Year | 2022 |
| Description | Research collaboration with Yoshiharu Kohayakawa and Guilherme Mota (University of Sao Paulo) |
| Organisation | Universidade de São Paulo |
| Country | Brazil |
| Sector | Academic/University |
| PI Contribution | PI Y Pehova contributed to joint work on project "Tight spanning trees in 3-uniform hypergraphs". She suggested this as the main topic of study during her 2-month research visit to USP. |
| Collaborator Contribution | Prof Y Kohayakawa and Dr G O Mota (both USP) contributed to joint work on project "Tight spanning trees in 3-uniform hypergraphs". |
| Impact | The research output from this collaboration is likely to result in a journal publication. |
| Start Year | 2023 |
| Description | LSE Winter Workshop in Combinatorics |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | Week-long research workshop took place in the week of 12-16 Dec 2022. About 25 participants took part in focus groups working on different problems in the field of combinatorics. PI Yani Pehova co-organised the workshop together with colleagues from LSE. The main outcome of the workshop is the foundation of new research collaborations, which are expected to continue as longer-term research projects. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://personal.lse.ac.uk/boettche/2022workshop/ |
| Description | Pernambuco Workshop on Extremal Combinatorics |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | The Pernambuco Workshop on Extremal Combinatorics (Workshop Pernambucano de Combinatória Extremal) was a small research-focused event including researchers from Brazil and abroad. There were a small amount of research talks and the participants worked mainly on open problems in the area of extremal combinatorics. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://sites.google.com/view/workshopernambucomb/home?authuser=1 |
| Description | QMUL Workshop in Extremal Combinatorics |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | Regional |
| Primary Audience | Postgraduate students |
| Results and Impact | On 9 and 11 November 2022 Dr Robert Johnson from Queen Mary, University of London organised a joint workshop in extremal combinatorics with invited participants from QMUL, LSE and UCL. Most participants were research students, the others being faculty and postdocs whose research interests fall within the area. PI Yani Pehova took part in the workshop by proposing a research problem and leading a focus group working on it. The main outcome of the workshop is a new research collaboration on Hamilton cycle decompositions of tripartite directed and oriented graphs, which is likely to lead to a journal publication. |
| Year(s) Of Engagement Activity | 2022 |
| Description | Seminar talk at Brunel University, London, UK |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | PI Yani Pehova gave a talk titled "Extremal questions about graphs" at Mathematics and Statistics Research Seminar on 19 Oct 2022 at Brunel University, London, UK. The talk was attended by a general audience of mathematics researchers. |
| Year(s) Of Engagement Activity | 2022 |
| Description | Seminar talk at LSE, London, UK |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | PI Yani Pehova gave a talk titled "Transversal factors and spanning trees" at Combinatorics, Games and Optimisation seminar on 17 Nov 2022 at the London School of Economics. This was a research seminar talk intended to disseminate outcomes of previous work to interested researchers at LSE. |
| Year(s) Of Engagement Activity | 2022 |
| Description | Seminar talk at University of Cardiff, UK |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | PI Yani Pehova gave a talk titled "Spanning trees in hypergraphs" at Discrete Mathematics & Data Science Seminar on 24 Jan 2023 at the University of Cardiff, UK. The talk was attended by researchers slightly outside the topic of the talk. A major outcome of the talk was popularising extremal combinatorics among researchers working in other fields of mathematics. |
| Year(s) Of Engagement Activity | 2022 |
| Description | Workshop Chileno-Paulista em/en Grafos |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | The fourth edition of the joint Workshop Chileno-Paulista em/en Grafos gathered researchers mainly from Chile and São Paulo that have been working in Combinatorics and Graph Theory. PI Yani Pehova attended the workshop during her 2-month visit to University of São Paulo, together with her collaborators. The workshop has no invited talks and is mainly focused on collaborative work on open problems from the area of extremal and structural combinatorics. |
| Year(s) Of Engagement Activity | 2023 |
| URL | http://professor.ufabc.edu.br/~carla.negri/chipagra/2023/ |