KPPY 89

TBA

TBA

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.

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).

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.