Seminars in October 2019

  • Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs

    IBS/KAIST Joint Discrete Math Seminar

    A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
    Pascal Gollin
    IBS Discrete Mathematics Group
    2019/10/29 Tue 4:30PM-5:30PM Room B232, IBS (기초과학연구원)
    Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.</p>

    We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning trees. In this talk, we concentrate on the case of $\lambda$ being an infinite cardinal. Moreover, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $\lambda$-packing, as well as for a theorem of Erdős and Hajnal characterising the existence of a $\lambda$-covering.

    Joint work with Joshua Erde, Attila Joó, Paul Knappe and Max Pitz.

    Tags:

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

    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.
    Tags:

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

    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.
    Tags:

  • Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

    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.
    Tags:

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

    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.
    Tags:

  • Casey Tompkins, Extremal problems for Berge hypergraphs

    IBS/KAIST Joint Discrete Math Seminar

    Extremal problems for Berge hypergraphs
    Casey Tompkins
    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.
    Tags:

Monthly Archives