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.

•   SC:   Stijn Cambie (Research Fellow Nov 2021 -)
•   IG:   Irene Gil Fernández (PhD student Oct 2020 - present)
•   JH:   John Haslegrave (Research Fellow, May 2020 - present)
•   JHy:   Joseph Hyde (Research Fellow Aug 2021 - present)
•   SI:   Seonghyuk Im (PhD student Sep 2021 - present)
•   HL:   Hong Liu (Principal Investigator)
•   ZW:   Zhuo Wu (PhD student Oct 2021 -)

•   Jan 2022: Stijn Cambie will join our group as a research fellow. Welcome Stijn!
•   Aug 2021: Joseph Hyde will join our group as a research fellow. Welcome Joseph!
•   Jun 2021: HL is invited to give a talk at Extremal Combinatorics minisymposium at the 8th European Congress of Mathematics.
•   May 2021: HL is invited to give a colloquium talk at KAIST on sublinear expander and its applications.
•   Apr 2021: HL is invited to give a talk at Korean Mathematical Society 2021 Spring meeting.
•   Nov 2020: Gil Kalai wrote a blog post about HL and R. Montgomery's recent resolution of the Erdős and Hajnal’s problem on odd cycles! HL was invited to give talks about this work at Institute for Basic Science, Daejeon, South Korea at Dec 2020 and also at Shanghai Center for Mathematical Sciences, China at Jan 2021.
•   Oct 2020: HL gave online lecture series on cycles and trees in (pseudo)random graphs at KAIST, South Korea.
•   Aug 2020: HL gave online lecture series on sublinear expanders at the summer school at Shandong University, China.
•   May 2020: HL gave online lecture series on graph containers at SCMS Combinatorics Seminar at Shanghai Center for Mathematical Sciences, China.
•   May 2020: John Haslegrave joined our group as a research fellow. Welcome John!
•   Aug 2019: HL gave lecture series on extremal combinatorics at the summer school at Shandong University, China.

•   J. Haslegrave,   Determining triangulations and quadrangulations by boundary distances , 18 pages. arXiv:2111.13556.
  
• New lower bounds on kissing numbers and spherical codes in high dimensions, with I. Gil Fernández, J. Kim, O. Pikhurko, 20 pages. PDF
• Well-mixing vertices and almost expanders, D. Chakraborti, J. Kim, J. Kim, M. Kim, H. Liu, 13 pages. PDF
• Fractional Helly theorem for Cartesian products of convex sets, D. Chakraborti, J. Kim, J. Kim, M. Kim, H. Liu, 16 pages. PDF
• Shape of the asymptotic maximum sum-free sets in integer lattice grids, H. Liu, G. Wang, L. Wilkies, D. Yang, 17 pages. PDF
•   S. Cambie,  J. Haslegrave,   On the relationship between variable Wiener index and variable Szeged index , 11 pages. arXiv:2108.04157.
  
•   J. Haslegrave,  J. Hu,  J. Kim,  H. Liu,  B. Luan,  G. Wang, Crux and long cycles in graphs, 13 pages. PDF
  
•   I. Benjamini,   J. Haslegrave,   Degrees in link graphs of regular graphs , 5 pages. arXiv:2106.15464.
  
•   J. Haslegrave,   The number and average size of connected sets in graphs with degree constraints , 11 pages. arXiv:2105.13332.
  
•   J. Haslegrave,   Sum index, difference index and exclusive sum number of graphs , 10 pages. arXiv:2104.06959.
  
•   I. Gil Fernández,   J. Kim,  Y. Kim,  H. Liu,  Nested cycles with no geometric crossings, 8 pages. PDF
  
•   J. Haslegrave,   The path minimises the average size of a connected set , 7 pages. arXiv:2103.16491.
  
•   H. Liu,  C. Reiher,  M. Sharifzadeh,  K. Staden,   Geometric constructions for Ramsey-Turán theory , 27 pages. PDF
  
•   H. Liu,  O. Pikhurko,  M. Sharifzadeh,  K. Staden,   Stability from graph symmetrisation arguments with applications to inducibility , 38 pages. PDF
  
•   H. Liu,  R. Montgomery,   A solution to Erdős and Hajnal’s odd cycle problem , 42 pages. PDF
  
•   H. Liu,  G. Wang,  D. Yang,   Clique immersion in graphs without fixed bipartite graph , 12 pages. PDF
  
•   H. Liu,  P. Pach,  Cs. Sándor,  Polynomial Schur's theorem , 21 pages. PDF
  

•   A. Georgakopoulos,  J. Haslegrave,   A time-invariant random graph with splitting events ,   Electronic Communications in Probability , 15 pages. arXiv:1911.09630.
  
•   J. Haslegrave,  T. Sauerwald,   J. Sylvester  Time Dependent Biased Random Walks ,   The 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of LIPIcs, pages 76:1-76:19, ACM Transactions on Algorithms , 32 pages. arXiv:2006.02475.
  
•   J. Haslegrave,  V. Sidoravicius,   L. Tournier  Three-speed ballistic annihilation: phase transition and universality ,   Selecta Mathematica , 39 pages. arXiv:1811.08709.
  
•   J. Haslegrave,  J. Kim,  H. Liu,   Extremal density for sparse minors and subdivisions ,   International Mathematics Research Notices , 33 pages. PDF
  
•   D. Kang,  J. Kim,  H. Liu,   On the rational Turán exponents conjecture ,   Journal of Combinatorial Theory, Series B , 148, (2021), 149--172. PDF
  
•   H. Liu,  M. Sharifzadeh,  K. Staden,   On the maximum number of integer colourings with forbidden monochromatic sums ,   Electronic Journal of Combinatorics, 28 (1), (2021), P1-59, 35 pages. PDF
  
•   A. Georgakopoulos,  J. Haslegrave,  T. Sauerwald,   J. Sylvester  The power of two choices for random walks ,   Combinatorics, Probability and Computing , 30 pages. arXiv:1911.05170.
  
•   J. Haslegrave,  Countable graphs are majority 3-choosable ,   Discussiones Mathematicae Graph Theory , 6 pages. arXiv:2003.10408.
  
•   H. Liu,  P. Pach,  R. Palincza,  The number of maximum primitive sets of integers ,   Combinatorics, Probability and Computing , 11 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