Embeddings in Sparse Graphs
Lead Research Organisation:
University of Warwick
Department Name: Mathematics
Abstract
Extremal combinatorics has witnessed a rapid growth in the past few decades. An archetype problem in this field is to study the structure of subgraphs appearing in different classes of graphs. Such problems are much better understand when the host graphs are dense thanks to a variety of tools applicable to dense graphs. This proposal will focus on such problems for sparse host graphs. In practice, almost all the graphs used to model real-life networks, such as facebook graphs, (artificial) neural networks, are sparse.
The goal is to develop a theory of certain sublinear expanders that can be used to construct subgraphs with various properties in graphs with (sufficiently large) constant average degree. This project will connect sublinear expanders with two other central notions in combinatorics: cycles and topological minors. The theory developed will make decisive progress on central problems concerning embedding sparse subgraphs with additional arithmetic properties. Some of such problems have remained wide open since the 60s despite active attempts from various researchers. Further links will be sought via considering analogous problems in other areas such as number theory.
The goal is to develop a theory of certain sublinear expanders that can be used to construct subgraphs with various properties in graphs with (sufficiently large) constant average degree. This project will connect sublinear expanders with two other central notions in combinatorics: cycles and topological minors. The theory developed will make decisive progress on central problems concerning embedding sparse subgraphs with additional arithmetic properties. Some of such problems have remained wide open since the 60s despite active attempts from various researchers. Further links will be sought via considering analogous problems in other areas such as number theory.
Planned Impact
The research area of the proposed program is extremal combinatorics in mathematical science. In particular, the primary mathematical object under study in this proposal is graphs, which is used to model various real-life networks such as facebook graphs, (artificial) neural networks. Research proposed here will greatly advance our understanding of sparse graphs by studying the substructures contained within. The theory developed will provide a modern approach to many central embedding problems in graph theory. Furthermore, the research outcomes promise novel connections between different fields of mathematics and foster new line of intradisciplinary research. In long term, the complex substructures found through this program would provide guidance for ongoing research in other disciplines such as Information and Communication Technologies and Deep Learning.
The UK has been a leader in research on combinatorics, and its applications to other fields. In particular, extremal combinatorics is identified by EPSRC as one of the key UK strengths. This is constantly challenged by other parts of the world. The results from this program will ensure the UK stays at the forefront of the related research topics and maintains its leadership of this fast developing area.
Two workshops (Year 2 and Year 4) will be organised during the project to bring together international researchers from both mathemtics and theoretic computer science, fostering excellence and collaboration on the global stage. Students will be strongly encouraged to participate these workshop, attracting young talents to the UK.
The UK has been a leader in research on combinatorics, and its applications to other fields. In particular, extremal combinatorics is identified by EPSRC as one of the key UK strengths. This is constantly challenged by other parts of the world. The results from this program will ensure the UK stays at the forefront of the related research topics and maintains its leadership of this fast developing area.
Two workshops (Year 2 and Year 4) will be organised during the project to bring together international researchers from both mathemtics and theoretic computer science, fostering excellence and collaboration on the global stage. Students will be strongly encouraged to participate these workshop, attracting young talents to the UK.
People |
ORCID iD |
Hong Liu (Principal Investigator / Fellow) |
Publications
Barhoumi-Andréani Y
(2019)
Bivariate fluctuations for the number of arithmetic progressions in random sets
in Electronic Journal of Probability
Haslegrave J
(2020)
Countable graphs are majority 3-choosable
in Discussiones Mathematicae Graph Theory
Kim J
(2020)
Tree decompositions of graphs without large bipartite holes
in Random Structures & Algorithms
Liu H
(2020)
Stability and exact Turán numbers for matroids
in Journal of Combinatorial Theory, Series B
Liu H
(2021)
The number of maximum primitive sets of integers
in Combinatorics, Probability and Computing
Kang D
(2021)
On the rational Turán exponents conjecture
in Journal of Combinatorial Theory, Series B
Liu H
(2021)
Groups with few maximal sum-free sets
in Journal of Combinatorial Theory, Series A
Description | This program is to study and develop the theory of sublinear expander, which falls in Mathematical Science. One of the original motivations of this program was to resolve a major open problem in sparse graph embedding raised by Erdos and Hajnal back in the 60s. We have recently submitted a preprint, in which we reach a milestone in this program. As a result, we have fully settled the aforementioned Erdos-Hajnal problem. |
Exploitation Route | The theory we developed in recent articles is expected to bring us closer to many other theoretical problems. In particular, it is hoped to grow into a standard tool in the research area of extremal and probabilistic combinatorics. |
Sectors | Other |