95th KPPY Combinatorics Workshop -- Dec 14, 2019

Date: Dec 14, 2019
Time: 11:00am-5:30pm
Location: Science Building 1, Room 417
Department of Mathematics, Yeungnam University

Schedule
11:00 - 11:50 Eun-kyung Cho
Hanguk University of Foreign Studies
Planar graphs with no $4$-cycles and $5$-cycles are $(3,4)$-colorable
12:00 Lunch  
1:30 -2:20 Hayoung Choi
SNU
Positive definite matrix completion
2:30 -3:20 Younghwan Son
Postech
Ergodic sum fluctuations in substitution dynamical systems
3:40 - 4:30 Kang-ju Lee
SNU
Simplicial effective resistance and enumeration of spanning trees
4:40 - 5:30 Abhishek Methuku
IBS
Bipartite Turán problems for ordered graphs
6:00 - 8:00 Banquet  
Program


Abstracts





Eun-kyung Cho
Planar graphs with no $4$-cycles and $5$-cycles are $(3,4)$-colorable
Let $\mathcal{F}_{4,5}$ be the class of planar graphs with no $4$-cycles and $5$-cycles. Given a positive integer $k$, and non-negative integers $d_1, \ldots, d_k$, a graph $G=(V(G),E(G))$ is said to be {\it $(d_1, \ldots, d_k)$-colorable} if we can partition $V(G)$ into $V_1, \ldots, V_k$ so that a subgraph of $G$ induced by $V_i$ has maximum degree at most $d_i$ for each $i \in \{1, \ldots, k\}$.

By the well-known ``Four color theorem'', we know that every planar graph is $(0,0,0,0)$-colorable. In 1976, there was a famous ``Steinberg's conjecture'' saying that $\mathcal{F}_{4,5}$ is $(0,0,0)$-colorable. This conjecture turned out to be false by Cohen-Addad et al. in 2017. However, the conjecture has inspired lots of mathematicians to study on the coloring of a planar graph, and as a result, Xu et al. proved that $\mathcal{F}_{4,5}$ is $(1,1,0)$-colorable in 2014, and Chen et al. proved that $\mathcal{F}_{4,5}$ is $(2,0,0)$-colorable in 2016. Later in 2018, Sittitrai and Nakprasit proved that $\mathcal{F}_{4,5}$ is not $(1,k)$-colorable for every positive integer $k$, but $(4,4)$-, $(3,5)$-, and $(2,9)$-colorable.

In this talk, we improve this result into saying that $\mathcal{F}_{4,5}$ is $(3,4)$-colorable. This talk is based on joint work with Ilkyoo Choi and Boram Park.









Hayoung Choi
Positive definite matrix completion
This talk will consider positive definite completion of partial Hermitian matrices (some entries are specified, some are missing). For example, does the following partial matrix have positive definite matrix completion? \begin{equation*} \begin{bmatrix} 4 & ? & 2 & -1 \\ ? & 3 & 1 & ? \\ 2 & 1 & 6 & 1 \\ -1 & ? & 1 & 3 \\ \end{bmatrix} \end{equation*} In 1984, R. Grone, at al. showed that if the undirected graph of the specified entries is chordal , a positive definite matrix completion necessarily exists. We will show several results and examples for a positive definite matrix completion. Moreover, results for Toeplitz matrix completion and Hamburger matrix completion will be presented. Lastly, we will talk about the recent results for special cases.









Younghwan Son
Ergodic sum fluctuations in substitution dynamical systems
A substituion is a map from the alphabet to the set of finite words. (We say that an alphabet is the set of finite letters and a word is a finite string of letters.) Iterating substituion produces an infinite sequence of letters, which is called a fixed point.

In this talk we will discuss deviation of ergodic sums for substitution dynamical systems with an incidence matrix having eigenvalues of modulus 1. Especially we will present central limit theorem for fixed points of substitution. This is a joint work with Elliot Paquette.









Kang-ju Lee
Simplicial effective resistance and enumeration of spanning trees
We present a new method for computing simplicial tree-numbers using electrical networks. For a current generator $\sigma$ in a simplicial resistor network, the simplicial effective resistance $R_\sigma$ is expressed as the ratio of the simplicial tree-numbers. We give the exact forms for the current and voltage vector in a simplicial electrical network generated by the current generator $\sigma$, which yields another expression for $R_\sigma$. Using two expressions for $R_\sigma$, we find formulas for tree-numbers of simplicial complexes which have recursive structures. Applying this method, we provide a new formula for simplicial tree-numbe rs of color-shifted complexes conjectured by Aalipour and Duval, and we recover the formula for simplicial tree-numbers of shifted complexes by Duval, Klivans, and Martin.

This is a joint work with Aalipour, Duval, Kook, and Martin.









Abhishek Methuku
Bipartite Turán problems for ordered graphs
A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$.

A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $ex(n,A)< n ^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $ex(n,A)< n^{2-\frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method.

Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $ex(n,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Istvan Tomon.