## Archive for the ‘KAIST Discrete Math Seminar’ Category

### Sun Kim (김선), Two identities in Ramanujan’s Lost Notebook with Bessel function series

Monday, October 14th, 2019
Two identities in Ramanujan’s Lost Notebook with Bessel function series
Sun Kim (김선)
Mathematical Institute, University of Cologne, Cologne, Germany
2019/11/05 Tue 4:30PM-5:30PM (room 1401, E6-1, KAIST)
On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu.

### Joonkyung Lee (이준경), On some properties of graph norms

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

On some properties of graph norms
Joonkyung Lee (이준경)
Department of Mathematics, University of Hamburg, Germany
2019/10/22 Tue 4:30PM-5:30PM (Room B232, IBS)
For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm. We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that ‘twisted’ blow-ups of cycles, which include $K_{5,5}\setminus C_{10}$ and $C_6\square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. Secondly, we prove that $\|.\|_{r(H)}$ is not uniformly convex nor uniformly smooth, provided that $H$ is weakly norming. This answers another question of Hatami, who estimated the modulus of convexity and smoothness of $\|.\|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe, Jan Hladký, and Bjarne Schülke.

### Zi-Xia Song (宋梓霞), Ramsey numbers of cycles under Gallai colorings

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Ramsey numbers of cycles under Gallai colorings
Zi-Xia Song (宋梓霞)
University of Central Florida
2019/10/15 Tue 4:30PM-5:30PM (Room B232, IBS)
For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4$ vertices. For odd cycles, Bondy and Erd\H{o}s in 1973 conjectured that for all $k\ge1$ and $n\ge2$, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. Joint work with Dylan Bruce, Christian Bosse, Yaojun Chen and Fangfang Zhang.

### Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Reconstructing graphs from smaller subgraphs
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
2019/10/10 Thu 4:30PM-5:30PM
A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. We show that for each $n\ge7$ and every $n$-vertex graph $G$, the degree list and connectedness of $G$ are $3$-reconstructible, and the threshold $n\geq 7$ is sharp for both properties.‌ We also show that all $3$-regular graphs are $2$-reconstructible.

### Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs

Monday, October 14th, 2019

KAIST MathSci / IBS DIMAG Joint Colloquium

On Ramsey-type problems for paths and cycles in dense graphs
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
2019/10/08 Tue 4:30PM-5:30PM
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a monochromatic copy of $H$. In these terms, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. We consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. This is joint work with Jozsef Balogh, Mikhail Lavrov and Xujun Liu.