IBS/KAIST Joint Discrete Math Seminar

Department of Mathematics, University of Hamburg, Germany

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

IBS/KAIST Joint Discrete Math Seminar

On some properties of graph norms

Joonkyung Lee (이준경)

Department of Mathematics, University of Hamburg, Germany

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.

IBS/KAIST Joint Discrete Math Seminar

Ramsey numbers of cycles under Gallai colorings

Zi-Xia Song (宋梓霞)

University of Central Florida

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.

IBS/KAIST Joint Discrete Math Seminar

Reconstructing graphs from smaller subgraphs

Alexandr V. Kostochka

University of Illinois at Urbana-Champaign

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.

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

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.

IBS/KAIST Joint Discrete Math Seminar

Extremal problems for Berge hypergraphs

Casey Tompkins

IBS Discrete Mathematics Group

IBS Discrete Mathematics Group

2019/10/01 Tue 4:30PM-5:30PM

Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku, and the second part with Győri, Salia and Zamora.