BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv4.9.9//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20191031
DTEND;VALUE=DATE:20191105
DTSTAMP:20191020T195552
CREATED:20190514T145906Z
LAST-MODIFIED:20191012T010930Z
UID:863-1572480000-1572911999@dimag.ibs.re.kr
SUMMARY:The 2nd East Asia Workshop on Extremal and Structural Graph Theory
DESCRIPTION:The 2nd East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory\, especially in the East Asia such as China\, Japan\, and Korea. \nDate\nOct 31\, 2019 (Arrival Day) – Nov 4\, 2019 (Departure Day) \nVenue and Date\nUTOP UBLESS Hotel\, Jeju\, Korea (유탑유블레스호텔제주) Address: 502 Johamhaean-ro\, Jocheon-eup\, Jeju\, Korea (제주특별자치도 제주시 조천읍 조함해안로 502) We plan to support the accommodation for invited participants. \nThe UTOP UBLESS Hotel is located at the beautiful Hamdeok Beach of the Jeju Island.\nInvited Speakers\n\nPing Hu\, Sun Yat-Sen University\, China\nJaehoon Kim\, KAIST\, Korea\nO-joung Kwon\, Incheon National University and IBS Discrete Mathematics Group\, Korea\nJoonkyung Lee\, University of Hamburg\, Germany\nBinlong Li\, Northwestern Polytechnical University\, China\nHongliang Lu\, Xi’an Jiaotong University\, China\nAbhishek Methuku\, IBS Discrete Mathematics Group\, Korea\nAtsuhiro Nakamoto\, Yokohama National University\, Japan\nKenta Noguchi\, Tokyo University of Science\, Japan\nKenta Ozeki\, Yokohama National University\, Japan\nBoram Park\, Ajou University\, Korea\nYuejian Peng\, Hunan University\, China\nZi-Xia Song\, University of Central Florida\, U.S.A.\nTomáš Kaiser\, University of West Bohemia\, Czech Republic.\nMaho Yokota\, Tokyo University of Science\, Japan.\nXuding Zhu\, Zhejiang Normal University\, China\n\nMore speakers to be announced as soon as confirmed. Last update: September 10. \nProgram\nDay 0 (Oct. 31 Thursday)\n\n4:00PM-6:00Pm Registration and Discussions\n\nDay 1 (Nov. 1 Friday)\n\n9:00AM-9:20AM Opening address\n9:20AM-9:50AM Jaehoon Kim\, A quantitative result on the polynomial Schur’s theorem\n10:00AM-10:30AM Yuejian Peng\, Lagrangian densities of hypergraphs\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Atsuhiro Nakamoto\, Geometric quadrangulations on the plane\n11:30AM-12:00PM Ping Hu\, The inducibility of oriented stars\n2:00PM-2:30PM Boram Park\, 5-star coloring of some sparse graphs\n2:40PM-3:10PM Kenta Ozeki\, An orientation of graphs with out-degree constraint\n3:10PM-3:30PM Coffee Break\n3:30PM-5:30PM Problem session\n\nDay 2 (Nov. 2 Saturday)\n\n9:20AM-9:50AM Xuding Zhu\, List colouring and Alon-Tarsi number of planar graphs\n10:00AM-10:30AM O-joung Kwon\, A survey of recent progress on Erdős-Pósa type problems\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Kenta Noguchi\, Extension of a quadrangulation to triangulations\, and spanning quadrangulations of a triangulation\n11:30AM-12:00PM Zi-Xia Song\, Ramsey numbers of cycles under Gallai colorings\n2:00PM-2:30PM Binlong Li\, Cycles through all finite vertex sets in infinite graphs\n2:40PM-3:10PM Tomáš Kaiser\, Hamilton cycles in tough chordal graphs\n3:20PM-3:50PM Abhishek Methuku\, On a hypergraph bipartite Turán problem\n3:50PM-4:10PM Coffee Break\n4:10PM-6:00PM Problem session and discussion\n\nDay 3 (Nov. 3 Sunday)\n\n9:20AM-9:50AM Joonkyung Lee\, Odd cycles in subgraphs of sparse pseudorandom graphs\n10:00AM-10:30AM Maho Yokota\, Connectivity\, toughness and forbidden subgraph conditions\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Hongliang Lu\, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs\n11:30AM-12:00PM Contributed Talks\n2:00PM-6:00PM Problem session / Discussions / Hike\n\nDay 4 (Nov. 4 Monday)\n\n9:00AM-10:30AM Discussions\n\nHistory\n\n1st East Asia Workshop on Extremal and Structural Graph Theory\n\nNov. 30-Dec. 2\, 2018.\nHeld at and sponsored by Shanghai Center for Mathematical Sciences in China\, under the name “2018 SCMS Workshop on Extremal and Structural Graph Theory”.\nOrganizers: Ping Hu\, Seog-Jin Kim\, Kenta Ozeki\, Hehui Wu.\n\n\n\nOrganizers\n\nSeog-Jin Kim\, Konkuk University\, Korea.\nSang-il Oum\, IBS Discrete Mathematics Group\, Korea and KAIST\, Korea.\nKenta Ozeki\, Yokohama National University\, Japan.\nHehui Wu\, Shanghai Center for Mathematical Sciences\, China.\n\nSponsor\nIBS Discrete Mathematics Group\, Korea. \nAbstracts\nPing Hu\, The inducibility of oriented stars\nLet $S_{k\,\ell}$ denote the oriented star with $k+\ell$ edges\, where the center has out-degree $k$ and in-degree $\ell$. For all $k\,\ell$ with $k+\ell$ large\, we determine n-vertex digraphs $G$ which maximize the number of induced $S_{k\,\ell}$. This extends a result of Huang (2014) for all $S_{k\,0}$\, and a result of Hladký\, Král’ and Norin for $S_{1\,1}$. Joint work with Jie Ma\, Sergey Norin\, and Hehui Wu. \nJaehoon Kim\, A quantitative result on the polynomial Schur’s theorem\nRecently\, Liu\, Pach\, and Sándor [arXiv:1811.05200] proved that for a polynomial $p(z)\in \mathbb{Z}[z]$\, any $2$-coloring of $\mathbb{N}$ has infinitely many monochromatic solutions of the equatoin $x+y=p(z)$ if and only if $2\mid p(0)p(1)$. We improve their result in a quantitative way. We prove that if $p(z)$ has degree $d \neq 3$ and $2\mid p(0)p(1)$\, then any $2$-coloring of $[n]=\{1\,\dots\, n\}$ contains at least $n^{2/d^2 -o(1)}$ monochromatic solutions. This is sharp as there exists a coloring of $[n]$ with $O(n^{2/d^2})$ monochromatic solutions. Our method also gives some bound for the case when $d=3$\, but it is not sharp. We also prove that if $2\mid p(0)p(1)$\, then the interval $[n\, p(\lceil \frac{p(n)}{2} \rceil)]$ contains at least one monochromatic solution of $x+y=p(z)$. This is sharp up to multiplicative constant at most two as one can color $[n\, \frac{1}{2}p(\lceil \frac{p(n)}{2} \rceil)-1]$ with no monochromatic solutions. Joint work with Hong Liu and Péter Pál Pach. \nO-joung Kwon\, A survey of recent progress on Erdős-Pósa type problems\nA graph family $\mathcal{F}$ is said to have the Erdős-Pósa property if there is a function $f$ such that for every graph $G$ and an integer $k$\, either $G$ contains $k$ disjoint copies of graphs in $\mathcal{F}$\, or it has a vertex set of size at most $f(k)$ that hits all copies of graphs in $\mathcal{F}$. This name is motivated from the Erdős-Pósa theorem (1965) which says that the set of cycles has the Erdős-Pósa property. In this talk\, we survey on progress of finding various graph families that have the Erdős-Pósa property\, and would like to pose interesting open problems. \nJoonkyung Lee\, Odd cycles in subgraphs of sparse pseudorandom graphs\n We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $\Gamma$ be an $(n\,d\,\lambda)$-graph\, i.e.\, $n$-vertex\, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-\lambda\,\lambda]$. Krivelevich\, Lee\, and Sudakov conjectured that\, whenever $\lambda^{2k-1}\ll d^{2k}/n$\, every subgraph $G$ of $\Gamma$ with $(1/2+o(1))e(\Gamma)$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev\, Hàn\, and the third author proved a weaker statment by allowing an extra polylogarithmic factor in the assumption $\lambda^{2k-1}\ll d^{2k}/n$\, but we completely remove it and hence settle the conjecture. This also generalises Sudakov\, Szabo\, and Vu’s Turán-type theorem for triangles. Secondly\, we obtain a Ramsey multiplicity result for odd cycles. Namely\, in the same range of parameters\, we prove that every 2-edge-colouring of $\Gamma$ contains at least $(1-o(1))2^{-2k}d^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale’s construction of $C_{2k+1}$-free pseudorandom graphs. Joint work with Sören Berger\, Mathias Schacht. \nBinlong Li\, Cycles through all finite vertex sets in infinite graphs\nA closed curve in the Freudenthal compactification $|G|$ of an infinite locally finite graph $G$ is called a Hamiltonian curve if it meets every vertex of $G$ exactly once (and hence it meets every end at least once). We prove that $|G|$ has a Hamiltonian curve if and only if every finite vertex set of $G$ is contained in a cycle of $G$. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example\, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However\, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve. Joint work with André Kündgen and Carsten Thomassen. \nHongliang Lu\, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs\nWe study degree conditions for the existence of large matchings and fractional perfect matching in uniform hypergraphs. Firstly\, we give some sufficient conditions for $k$-graphs to have fractional perfect matching in terms of minimum degree. Secondly\, we prove that for integers $k\,l\,n$ with $k\ge 3$\, $k/2{n-l\choose k-l}-{(n-l)-(\lceil n/k \rceil-2)\choose 2}$\, then $H$ has a matching covering all but a constant number of vertices. When $l=k-2$ and $k\ge 5$\, such a matching is near perfect and our bound on $\delta_l(H)$ is best possible. When $k=3$\, with the help of an absorbing lemma of Hàn\, Person\, and Schacht\, our proof also implies that $H$ has a perfect matching\, a result proved by Kühn\, Osthus\, and Treglown and\, independently\, of Kahn. Joint work with Xingxing Yu and Xiaofan Yuan. \nAbhishek Methuku\, On a hypergraph bipartite Turán problem\nLet $t$ be an integer such that $t\geq 2$. Let $K_{2\,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a\,x_i\,y_i\}$\, $\{b\,x_i\,y_i\}$ for $ 1 \le i \le t$\, where the elements $a\, b\, x_1\, x_2\, \ldots\, x_t\,$ $y_1\, y_2\, \ldots\, y_t$ are all distinct. Let $ex(n\,K_{2\,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2\,t}^{(3)}$. This function was studied by Mubayi and Verstraëte\, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n\,K_{2\,t}^{(3)})1$. If $G$ is $k$-connected and $K_{1\,\lfloor r \rfloor +1}$-free\, then $\textrm{tough}(G)\geq k/r$. It means high connectivity implies high toughness under the star-free condition. Our purpose is to prove assertions which can be regarded as a converse of this statement; that is say\, we ask what we can say about $\mathcal H$ if high connectivity implies high toughness in the family of $\mathcal H$-free graphs. About this question\, Ota and Sueiro (2013) proved the following theorem. Theorem 1 (Ota and Sueiro). Let $H$ be a connected graph and $\tau$ be a real number with $0<\tau\leq 1/2$. Almost all $H$-free connected graphs $G$ satisfy $\textrm{tough}(G)\geq \tau$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Our main result is high connectivity versions of this theorem. We proved the following theorems. Theorem 2. Let $H$ be a connected graph\, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Theorem 3. Let $\mathcal H=\{H_1\,H_2\}$ be a family of connected graphs\, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $\mathcal H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains one of $H$ as an induced subgraph. \nXuding Zhu\, List colouring and Alon-Tarsi number of planar graphs\nA $d$-defective colouring of a graph $G$ is a colouring of the vertices of $G$ such that each vertex $v$ has at most $d$ neighbours coloured the same colour as $v$. We say $G$ is $d$-defective $k$-choosable if for any $k$-assignment $L$ of $G$\, there exists a $d$-defective $L$-colouring\, i.e.\, a $d$-defective colouring $f$ with $f(v) \in L(v)$ for each vertex $v$. It was proved by Eaton and Hull (1999) and Škrekovski (1999) that every planar graph is $2$-defective $3$-choosable\, and proved by Cushing and Kierstead (2010) that every planar graph is $1$-defective $4$-choosable. In other words\, for a planar graph $G$\, for any $3$-assigment $L$ of $G$\, there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $L$-colourable; and for any $4$-list assignment $L$ of $G$\, there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $L$-colourable. An interesting problem is whether there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $3$-choosable\, and whether there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $4$-choosable. It turns out that the answer to the first question is negative and the answer to the second question is positive. Kim\, Kim and I proved that there is a planar graph $G$ such that for any subgraph $H$ with $\Delta(H)=3$\, $G-E(H)$ is not $3$-choosable. Grytczuk and I proved that every planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most $4$\, and hence is $4$-choosable. The late result also implies that every planar graph is $1$-defective $4$-paintable. For a subset $X$ of $V(G)$\, let $f_X$ be the function defined as $f_X(v)=4$ for $v \in X$ and $f_X(v)=5$ for $v \in V(G)-X$. Our proof also shows that every planar graph $G$ has a subset $X$ of size $|X| \ge |V(G)|/2$ such that $G$ is $f_X$-AT\, which implies that $G$ is $f_X$-choosable and also $f_X$-paintable. In this talk\, we shall present the proof and discuss possible strengthening of this result. \n
URL:https://dimag.ibs.re.kr/event/2019-east-asia-graph-theory/
LOCATION:UTOP UBLESS Hotel\, Jeju\, Korea (유탑유블레스호텔제주)
CATEGORIES:Workshops and Conferences
ORGANIZER;CN="Seog-Jin%20Kim":MAILTO:skim12@konkuk.ac.kr
END:VEVENT
END:VCALENDAR