# KPPY 89

Jack Koolen, Yun Jeong Kim, Jineon Baek, Patrick Ali, Semin Oh

Sept 29, 2018. 11:00am-6:00pm at PNU

Schedule | ||

11:00am - 11:50 |
Jack Koolen USTC | TBA |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Yun Jeong Kim PNU | TBA |

2:30 - 3:20 |
Jineon Baek NIMS | On the off-diagonal Erdős-Szekeres convex polygon problem |

3:30 - 4:20 |
Patrick Ali University of Malawi, Chancellor College | Identities for the minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights |

4:30 - 5:20 |
Semin Oh PNU | Optimal Solution For Producing Products Without Loss |

## Abstracts

Jack Koolen

TBA

TBA

TBA

Yun Jeong Kim

TBA

TBA

TBA

Jineon Baek

On the off-diagonal Erdős-Szekeres convex polygon problem

On the off-diagonal Erdős-Szekeres convex polygon problem

The infamous Erdős-Szekeres conjecture, posed in 1935, states that the minimum number $ES(n)$ of points on a plane in general position (that is, no three colinear points) that guarantees a subset of $n$ points in convex position is equal to $2^{n-2} + 1$. Despite many years of effort, the upper bound of $ES(n)$ had not been better than $O(4^{n - o(n)})$ until Suk proved the groundbreaking result $ES(n) \leq 2^{n + o(n)}$ in 2016.

In this talk, we focus on a variant of this problem by Erdős, Tuza and Valtr regarding the number $ETV(a, b, n)$ of points needed to force either an $a$ -cup, $b$-cap or a convex $n$-gon for varying $a, b$ and $n$. They showed $ETV(a, b, n) > \sum_{i=n-b}^{a-2} \binom{n}{i-2}$ by supplying a set of points with no $a$-cup, $b$-cap nor a $n$-gon of that many number, and conjectured that the inequality cannot be improved. Due to their construction, the conjecture is in fact equivalent to the Erdos-Szekeres conjecture. However, even the simplest equality $ETV(4, n, n) = \binom{n+1}{2} + 1$, which must be true if the Erdos-Szekeres conjecture is, has not been verified yet. To the best of our knowledge, the bound $ETV(4, n, n) \leq \binom{n + 2}{2} - 1$, mentioned by Balko and Valtr in 2015, is currently the best bound known in literature.

The talk is divided into two parts. First, we introduce the mentioned works on the Erdős-Szekeres conjecture and propose a conjectured upper bound of $ETV(a, n, n)$. Then we show the bound $ETV(4, n, n) \leq \binom{n+2}{2} - C \sqrt{n}$ for a fixed constant $C>0$, improving the previously known best bound of Balko and Valtr.

In this talk, we focus on a variant of this problem by Erdős, Tuza and Valtr regarding the number $ETV(a, b, n)$ of points needed to force either an $a$ -cup, $b$-cap or a convex $n$-gon for varying $a, b$ and $n$. They showed $ETV(a, b, n) > \sum_{i=n-b}^{a-2} \binom{n}{i-2}$ by supplying a set of points with no $a$-cup, $b$-cap nor a $n$-gon of that many number, and conjectured that the inequality cannot be improved. Due to their construction, the conjecture is in fact equivalent to the Erdos-Szekeres conjecture. However, even the simplest equality $ETV(4, n, n) = \binom{n+1}{2} + 1$, which must be true if the Erdos-Szekeres conjecture is, has not been verified yet. To the best of our knowledge, the bound $ETV(4, n, n) \leq \binom{n + 2}{2} - 1$, mentioned by Balko and Valtr in 2015, is currently the best bound known in literature.

The talk is divided into two parts. First, we introduce the mentioned works on the Erdős-Szekeres conjecture and propose a conjectured upper bound of $ETV(a, n, n)$. Then we show the bound $ETV(4, n, n) \leq \binom{n+2}{2} - C \sqrt{n}$ for a fixed constant $C>0$, improving the previously known best bound of Balko and Valtr.

Patrick Ali

Identities for the minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights

Identities for the minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights

The resisistance matrix of a simple connected graph $G$ is denoted by $R_{G}$ and is defined by $R_{G}=(r_{ij})$, where $r_{ij}$ is the resistance distance between the vertices $i$ and $j$ in $G$. In this talk, we consider the resistance matrix of a weighted tree and the resisitance matrix of any weighted graph, where the weights are nonzero scalars. We obtain the minors of the Laplacian, resistance and the distance matrices, which are independent of the nonsingularity of resistance and distance matrices.

(Joint work with Fouzul Atik and R. B. Bapat).

(Joint work with Fouzul Atik and R. B. Bapat).

Semin Oh

Optimal Solution For Producing Products Without Loss

Optimal Solution For Producing Products Without Loss

We assume that the following situation: 1) we have to produce $n$ kinds products, 2) we produce $d$ products at a time,
3) we will produce $\sum_{i=1}^n p_i$ products where $p_i$ is the number of the $i$-th product.
Under the assumptions, our goal is to find the minimal number of arrangements to produce $d$ products at a time without loss.
At first, we consider real situations satisfying the assumptions, and then, theoretically, we show that which conditions guarantee the existence of such a solution.
Especially, one of Coxeter groups, the shortest vector problem (SVP) and the closest vector problem (CVP) of the lattice theory play important roles in this talk.