### 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 |

## Abstracts

Eun-kyung Cho

Planar graphs with no $4$-cycles and $5$-cycles are $(3,4)$-colorable

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.

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

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

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.

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

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.

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

Abhishek Methuku

Bipartite Turán problems for ordered graphs

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.

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.