Embeddings in Sparse Graphs
Welcome to the webpage of the UKRI Future Leaders Fellowship Project "Embeddings in Sparse Graphs" (EiSG), 1 May 2019 - 30 April 2023.
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 project 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 main objective is to design and construct versatile building blocks in sparse graphs with the aid of expansion properties. Such building blocks will then be used to embed subgraphs with various complex structure. 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.
- John Halsegrave (Research Fellow 1/5/2020 - present)
- Hong Liu (PI)
- Walner Mendonça (Research Fellow 1/10/2020 - present)
- J. Haslegrave, J. Kim, H. Liu, Extremal density for sparse minors and subdivisions , 33 pages. PDF
- D. Kang, J. Kim, H. Liu, On the rational Turán exponents conjecture , 18 pages. PDF
- H. Liu, P. Pach, Cs. Sándor, Polynomial Schur's theorem , 21 pages. PDF
- H. Liu, P. Pach, R. Palincza, The number of maximum primitive sets of integers , 11 pages. PDF
- H. Liu, M. Sharifzadeh, K. Staden, On the maximum number of integer colourings with forbidden monochromatic sums , 27 pages. PDF
- J. Kim, H. Liu, O. Pikhurko, M. Sharifzadeh, Asymptotic structure for the clique density theorem , Discrete Analysis , 26 pages. PDF
- H. Liu, M. Sharifzadeh, Groups with few maximal sum-free sets , Journal of Combinatorial Theory, Series A, 14 pages. PDF
- J. Kim, Y. Kim, H. Liu, Tree decompositions of graphs without large bipartite holes , Random Structures and Algorithms, 57 (1), (2020), 150--168. PDF
- H. Liu, S. Luo, P. Nelson, K. Nomoto, Stability and exact Turán numbers for matroids , Journal of Combinatorial Theory, Series B, 143, (2020), 29--41.PDF
- Y. Barhoumi-Andréani, C. Koch, H. Liu, Bivariate fluctuations for the number of arithmetic progressions in random sets , Electronic Journal of Probability, 24 (2019), paper 145, 32 pp. PDF
- J. Kim, H. Liu, M. Sharifzadeh, K. Staden, Proof of Komlós's conjecture on Hamiltonian subsets, Proceedings of the London Mathematical Society, 115 (5), (2017), 974--1013. PDF
- H. Liu, R. Montgomery, A proof of Mader’s conjecture on large clique subdivisions in C_4-free graphs, Journal of the London Mathematical Society, 95 (1), (2017), 203--222. PDF
- J. Balogh, H. Liu, M. Sharifzadeh, Subdivisions of a large clique in C_6-free graphs, Journal of Combinatorial Theory, Series B, 112, (2015), 18--35. PDF
WM, Seminários online de Grafos, Algoritmos e Combinatória Brazil, Aug 2020
HL, Summer Course @ Shandong University VIDEO China, Aug 2020
HL, Combinatorics Literature Seminar @ University of Illinois at Urbana Champaign USA, Jul 2020
HL, Lectures at SCMS Combinatorics Seminar @ Shanghai Center for Mathematical Sciences VIDEO China, May 2020
HL, Combinatorics Seminar @ Institute for Basic Science VIDEO South Korea, May 2020
HL, Combinatorics Seminar @ KAIST South Korea, Dec 2019
HL, Combinatorics Seminar @ Institute for Basic Science VIDEO South Korea, Aug 2019
HL, Summer Course @ Shandong University VIDEO China, Aug 2019
HL, Combinatorics Seminar @ Capital Normal University China, Jul 2019
HL, Combinatorics Seminar @ Konkuk University South Korea, Jul 2019
- Aug 2020: HL gave lecture series on sublinear expanders at the summer school at Shandong University, China.
- May 2020: HL gave lecture series on graph containers at SCMS Combinatorics Seminar at Shanghai Center for Mathematical Sciences, China.
- Aug 2019: HL gave lecture series on extremal combinatorics at the summer school at Shandong University, China.