Session Time & Room : 4C (Aug.24, 13:20-15:00) @G302
Type : Proposal of Minisymposium
Abstract : Extremal graph theory is a fast emerging and growing area with many exciting developments in recent years. This mini-symposium will cover topics in Turan problem, sublinear expander and sparse pseudorandom graphs.
[02678] Spanning trees in sparse pseudorandom graphs
Format : Online Talk on Zoom
Author(s) :
Jie Han (Beijing Institute of Technology)
Donglei Yang (Shandong University)
Abstract : Let $\mathcal{T}(n, \Delta)$ be the class of trees with $n$ vertices and maximum degree at most $\Delta$. Confirming a conjecture of Kahn, Montgomery established for every fixed tree $T\in\mathcal{T}(n, \Delta)$, the smallest value of $p$ for which $G(n, p)$ a.a.s. contains a copy of $T$. There have been a wealth of results and open problems on embedding spanning trees in (pseudo)random graphs in the past few decades. In 2005, Alon, Krivelevich and Sudakov asked for determining the best possible spectral gap forcing an $(n, d, \lambda)$-graph to be $\mathcal{T}(n, \Delta)$-universal. In this talk, we introduce some recent works and open questions. Similar questions for expander graphs are also considered.
[03075] Extremal results on 4-cycles
Format : Talk at Waseda University
Author(s) :
Tianchi Yang (National University of Singapore)
Abstract : The study of 4-cycles has important implications for the progression of Turan type problems, particularly in their degenerate forms. In this presentation, novel upper bounds are derived for the maximum number of edges in n-vertex graphs without cycles of length four. These findings not only augment our comprehension of combinatorial structures but also disprove certain conjectures of Erdos.
[03224] Many Hamiltonian subsets in large graphs with given density
Format : Talk at Waseda University
Author(s) :
Stijn Cambie (Institute for Basic Science)
Jun Gao (Institute for Basic Science)
Hong Liu (Institute for Basic Science)
Abstract : A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh and Staden proved that among all graphs with minimum degree $d$, $K_{d+1}$ minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one ($\approx 2^{d+1}$). Among others, our bound implies that an $n$-vertex $C_4$-free graphs with minimum degree $d$ contains at least $n2^{d^{2-o(1)}}$ Hamiltonian subsets.
This is a joint work with Stijn Cambie and Hong Liu.
[03146] Balanced Subdivisions in Graphs
Format : Talk at Waseda University
Author(s) :
Donglei Yang (Shandong University)
Abstract : A balanced subdivision of a graph H is obtained from $H$ by equally subdividing every edge. In 1984, Thomassen conjectured that for each integer $k\ge 1$, high average degree forces a balanced subdivision of $K_k$, and this was recently resolved by Liu and Montgomery. We give an optimal estimate on the average degree condition forcing every balanced $H$-subdivision, resolving a question of Fern\'{a}ndez et al. Similar problems on clique immersions are also considered.
