Abstract : Combinatorics studies discrete objects and their properties, which has striking applications in statistical physics, biology, computer science and so on. This minisymposium we propose will focus on Extremal Combinatorics and Probabilistic Combinatorics, which are two of the most central branches of modern combinatorial theory. We aim to attract the top researchers to the minisymposium, where they will present their recent results, discuss open problems, exchange research ideas, and initiate new collaborations. We expect the minisymposium will have a lasting impact in this area.
[03243] Turan problem for graphs from geometric shapes
Format : Talk at Waseda University
Author(s) :
Hong Liu (Institute for Basic Science)
Abstract : While Tur\'{a}n type problem is the most studied topic in extremal combinatorics, some of the most basic bipartite degenerate Tur\'{a}n problems remain elusive. In this talk, I will discuss some recent advancements on this topic and new results on bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature, including even prisms, planar hexagonal tiling and quadrangulations of plane, cylinder and torus. This is joint work with Jun Gao, Oliver Janzer, Zixiang Xu.
[03233] Robust linear algebra methods and some applications
Format : Talk at Waseda University
Author(s) :
Jun Gao (Institute for Basic Science)
Hong Liu (Institute for Basic Science)
Zixiang Xu (Institute for Basic Science)
Abstract : Given a set $L\subseteq [n]$, what can we say about the size or structure of a set system $\mathcal{F}\subseteq 2^{[n]}$ if $A\star B\in L$ for $A,B\in\mathcal{F}$, where $\star\in\{\cap,\cup,\setminus,\triangle\}$. Many important results have been produced around the above questions, and several far-reaching methods have been developed. In this talk, I will explain how to apply the linear algebra methods in the above problems, and introduce an algebraic proof of the stability result for Kleitman's theorem.
[03332] Optimal bisections of directed graphs
Format : Talk at Waseda University
Author(s) :
Guanwu Liu (University of Science and Technology of China)
Jie Ma (University of Science and Technology of China)
Chunlei Zu (Shanghai Jiaotong Univerisity)
Abstract : In this paper, motivated by a problem of Scott and a conjecture of Lee, Loh and Sudakov we consider bisections of directed graphs. We prove that every directed graph with $m$ arcs and minimum semidegree at least $d$ admits a bisection in which at least $\left(\frac{d}{2(2d+1)}+o(1)\right)m$ arcs cross in each direction. This provides an optimal bound as well as a positive answer to a question of Hou and Wu in a stronger form.
[03231] Hypergraphs with infinitely many extremal constructions
Format : Online Talk on Zoom
Author(s) :
JIANFENG HOU (Fuzhou University)
Abstract : We give the first exact and stability
results for a hypergraph Tur\'{a}n problem with infinitely many extremal constructions
that are far from each other in edit-distance.
This includes an example of triple systems with Tur\'{a}n density $2/9$,
thus answering some questions posed by the third and fourth authors and Reiher about the feasible region of hypergraphs. Our results also provide extremal constructions whose shadow density is a transcendental number.
Our novel approach is to construct certain multilinear polynomials that attain
their maximum (in the standard simplex) on a line segment and then to use these polynomials to define an operation on hypergraphs that gives extremal constructions.
Abstract : An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in “random like” hypergraphs. In precise, we will mention Turan problems in quasi-random hypergraphs.
[03333] Spectral extremal graphs for disjoint cliques
Format : Talk at Waseda University
Author(s) :
Liying Kang (Shanghai University)
Abstract : Let $kK_{r+1}$ be the graph consisting of $k$ vertex-disjoint copies of the complete graph $K_{r+1}$.
Moon [Canad. J. Math. 20 (1968) 95--102] and Simonovits [Theory of Graphs (Proc. colloq., Tihany, 1996)] independently showed that if $n$ is sufficiently large, then the join of a complete graph $K_{k-1}$ and an $r$-partite Tur\'{a}n graph $T_{n-k+1,r}$ is the unique extremal graph for $kK_{r+1}$. In this talk we consider the graph which has the maximum spectral radius among all graphs without $k$ disjoint cliques. We show that if $G$ attains the maximum spectral radius over all $n$-vertex $kK_{r+1}$-free graphs for sufficiently large $n$, then $G$ is isomorphic to the join of a complete graph $K_{k-1}$ and an $r$-partite Tur\'{a}n graph $T_{n-k+1,r}$. This is a joint work with Zhenyu Ni, Jing wang.
[03579] Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
Format : Talk at Waseda University
Author(s) :
Hongliang Lu (Xi'an Jiaotong University)
Yan Wang (Shanghai Jiao Tong University)
Xingxing Yu (Georgia Institute of Technology)
Abstract : Let $k$ and $n$ be two integers, with $k\geq 3$, $n\equiv 0\pmod k$, and $n$ sufficiently large. We determine the $(k-1)$-degree threshold for the existence of a rainbow perfect matchings in $n$-vertex $k$-uniform hypergraph. This implies the result of R\"odl, Ruci\'nski, and Szemer\'edi on the $(k-1)$-degree threshold for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs. In our proof, we identify the extremal configurations of closeness, and consider whether or not the hypergraph is close to the extremal configuration. In addition, we also develop a novel absorbing device and generalize the absorbing lemma of R\"odl, Ruci\'nski, and Szemer\'edi.
[03715] Recent progress on non-separating subgraphs in highly connected graphs
Format : Talk at Waseda University
Author(s) :
Shinya Fujita (Yokohama City University)
Abstract : Let $k$ be a positive integer. A connected graph $G$ is said to be $k$-connected, if for any vertex subset $S$ of $V(G)$ such that $|S|
[04621] Spanning trees with bounded number of leaves in $K_{1,p}$-free graphs
Format : Talk at Waseda University
Author(s) :
Kenta Ozeki (Yokohama National University)
Abstract : Matthews and Sumner proved that a connected $K_{1,3}$-free graph contains a Hamiltonian path if the graph satisfies a certain minimum degree condition.
Extending this result, it has been widely studied about the existence of a spanning $k$-ended tree in $K_{1,3}$-free or $K_{1,4}$-free graphs with $k \geq 2$, and in $K_{1,5}$-free graphs with $k=4,6$, where a $k$-ended tree is a tree with at most $k$ leaves.
With this situation in mind, in this talk, we pose a conjecture on a spanning $k$-ended tree in $K_{1,p}$-free graphs, and show two partial answers to the conjecture:
One solves the case $p=5$ completely, and the other proves the conjecture asymptotically for all $p \geq 6$.
This is a joint work with Masao Tsugaki (Tokyo University of Science) and partially with Masahiro Kimura (Yokohama National University).
[04636] Hadwiger’s conjecture for some graphs with independence number two
Format : Talk at Waseda University
Author(s) :
Guiying YAN (Academy of Mathematics and Systems Science’Chinese Academy of Sciences)
Qiang Zhou (Academy of Mathematics and Systems Science’Chinese Academy of Sciences)
Abstract : Hadwiger’s conjecture is difficult to prove even for graphs with independence number two. Recently, Daniel Carter
found the conjecture is true for H-free graphs if H is some particular graphs of 6, 7, 8 or 9 vertices with the help of
computers. In this talk, we will introduce this conjecture is true if H is one of four special graphs with 6 or 7 vertices
mathematically.
[05371] On Connectivities of Edge-Colored Graphs
Format : Talk at Waseda University
Author(s) :
Kiyoshi Yoshimoto (Nihon University)
Abstract : In this talk, we consider two kind of color-connectivities of edge-colored graphs which are generalizing strong connectivity of directed graphs and also the relation is given.
Furthremore we show structures of edge-colored complete graphs using the color-connectivities.
