BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//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
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20191031
DTEND;VALUE=DATE:20191105
DTSTAMP:20260424T030050
CREATED:20190514T145906Z
LAST-MODIFIED:20240707T090002Z
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\n1st floor  Diamond Hall \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<l<k$\, and $n$ large\, if $H$ is a $k$-uniform hypergraph on $n$ vertices and $\delta_{l}(H)>{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)})<t^4\binom{n}{2}$ and that for infinitely many $n$\, $ex(n\,K_{2\,t}^{(3)})\geq \frac{2t-1}{3} \binom{n}{2}$. These bounds together with a standard argument show that $g(t):=\lim_{n\to \infty} ex(n\,K_{2\,t}^{(3)})/\binom{n}{2}$ exists and that \[\frac{2t-1}{3}\leq g(t)\leq t^4.\] Addressing a 15 year old question of Mubayi and Verstraëte on the growth rate of $g(t)$\, we prove that as $t \to \infty$\, \[g(t) = \Theta(t^{1+o(1)}).\] Joint work with Beka Ergemlidze and Tao Jiang. \nAtsuhiro Nakamoto\, Geometric quadrangulations on the plane\nLet $P$ be a point set on the plane with $|P| \geq 4$ in a general position (i.e.\, no three points lie on the same straight line). A geometric quadrangulation $Q$ on $P$ is a geometric plane graph (i.e.\, every edge is a straight segment) such that the outer cycle of $Q$ coincides with the boundary of the convex hull ${\rm Conv}(P)$ of $P$ and that each finite face of $Q$ is quadrilateral. We say that $P$ is quadrangulatable if $P$ admits a geometric quadrangulation. It is easy to see that if $P$ has an even number of points on the boundary of ${\rm Conv}(P)$\, then $P$ is quadrangulatable. Suppose that $P$ is $k$-colored for $k \geq 2$\, and that no two consecutive points on the boundary of ${\rm Conv}(P)$ have the same color. Let us consider whether $P$ is quadrangulatable with no edge joining two points with the same color. Then we see that $P$ is not necessarily quadrangulatable. Hence\, introducing Steiner points $S$ for $P$\, which are ones put in the interior of ${\rm Conv}(P)$ as we like\, we consider whether $P \cup S$ is quadrangulatable. Intuitively\, for any $k$-colored $P$\, adding sufficiently large Steiner points $S$\, we wonder if $P \cup S$ is quadrangulatable. However\, we surprisingly see that it is impossible when $k=3$ (Alvarez et al.\, 2007). In my talk\, we summarize these researches on quadrangulatability of point sets with Steiner points\, and describe a relation with coloring of topological quadrangulations (Alvarez and Nakamoto\, 2012 and Kato et al.\, 2014). Moreover\, we describe a recent progress on a similar topic on quadrangulatability of a polygon with Steiner points. \nKenta Noguchi\, Extension of a quadrangulation to triangulations\, and spanning quadrangulations of a triangulation\nA triangulation (resp.\, a quadrangulation) on a surface $S$ is a map of a graph (possibly with multiple edges and loops) on $S$ with each face bounded by a closed walk of length $3$ (resp.\, $4$). In this talk\, we focus on the relationship between triangulations and quadrangulations on a surface. (I) An extension of a graph $G$ is the construction of a new graph by adding edges to some pairs of vertices in $G$. It is easy to see that every quadrangulation $G$ on any surface can be extended to a triangulation by adding a diagonal to each face of $G$. If we require the resulting triangulation to have more properties\, the problem might be difficult and interesting. Our two main results are as follows. Every quadrangulation on any surface can be extended to an even (i.e. Eulerian) triangulation. Furthermore\, we give the explicit formula for the number of distinct even triangulations extended from a given quadrangulation on a surface. These completely solves the problem raised by Zhang and He (2005). (II) It is easy to see that every loopless triangulation $G$ on any surface has a quadrangulation as a spanning subgraph of $G$. As well as (I)\, if we require the resulting quadrangulation to have more properties\, the problem might be difficult and interesting. Kündgen and Thomassen (2017) proved that every loopless even triangulation $G$ on the torus has a spanning nonbipartite quadrangulation\, and that if $G$ has sufficiently large face width\, then $G$ also has a bipartite one. We prove that a loopless even triangulation $G$ on the torus has a spanning bipartite quadrangulation if and only if $G$ does not have $K_7$ as a subgraph. This talk is based on the papers (2015\, 2019\, 2019). Joint work with Atsuhiro Nakamoto and Kenta Ozeki. \nKenta Ozeki\, An orientation of graphs with out-degree constraint\nAn orientation of an (undirected) graph $G$ is an assignment of directions to each edge of $G$. An orientation with certain properties has much attracted because of its applications\, such as a list-coloring\, and Tutte’s $3$-flow conjecture. In this talk\, we consider an orientation such that the out-degree of each vertex is contained in a given list. For an orientation $O$ of $G$ and a vertex $v$\, we denote by $d_O^+(v)$ the out-degree of $v$ in the digraph $G$ with respect to the orientation $O$. Recall that the number of outgoing edges is the out-degree. We denote by $\mathbb{N}$ the set of natural numbers (including $0$). For a graph $G$ and a mapping $L: V(G)\rightarrow 2^{\mathbb{N}}$\, an orientation $O$ of $G$ such that \[d_O^+(v) \in L(v)\] for each vertex $v$ is called an $L$-orientation. In this talk\, we pose the following conjecture. Conjecture. Let $G$ be a graph and let $L: V(G) \rightarrow 2^{\mathbb{N}}$ be a mapping. If \[|L(v)| \ \geq \ \frac{1}{2}\Big(d_G(v) +3\Big)\]for each vertex $v$\, then $G$ has an $L$-orientation. I will explain some results related to Conjecture; the best possibility if it is true\, and partial solutions for bipartite graphs. However\, it is open even for complete graphs. This talk is based on the paper https://doi.org/10.1002/jgt.22498. Joint work with S. Akbari\, M. Dalirrooyfard\, K.Ehsani\, and R. Sherkati. \nBoram Park\, 5-star coloring of some sparse graphs\nA star $k$-coloring of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$\, its star chromatic number\, denoted $\chi_s(G)$\, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research\, especially in terms of the maximum average degree $\mathrm{mad}(G)$ of a graph $G$. It is known that for a graph $G$\, if $\mathrm{mad}(G)<\frac{8}{3}$\, then $\chi_s(G)\leq 6$ (Kündgen and Timmons\, 2010)\, and if $\mathrm{mad}(G)< \frac{18}{7}$ and its girth is at least 6\, then $\chi_s(G)\le 5$ (Bu et al.\, 2009). We improve both results by showing that for a graph $G$ with $\mathrm{mad}(G)\le \frac{8}{3}$\, then $\chi_s(G)\le 5$. As an immediate corollary\, we obtain that a planar graph with girth at least 8 has a star 5-coloring\, improving the best known girth condition for a planar graph to have a star 5-coloring (Kündgen and Timmons\, 2010 and Timmons\, 2008). Joint work with Ilkyoo Choi. \nYuejian Peng\, Lagrangian densities of hypergraphs\nGiven a positive integer $n$ and an $r$-uniform hypergraph $H$\, the Turán number $ex(n\, H)$ is the maximum number of edges in an $H$-free $r$-uniform hypergraph on $n$ vertices. The Turán density of $H$ is defined as \[\pi(H)=\lim_{n\rightarrow\infty} { ex(n\,H) \over {n \choose r } }.\] The Lagrangian density of an $r$-uniform graph $H$ is \[\pi_{\lambda}(H)=\sup \{r! \lambda(G):G\;\text{is}\;H\text{-free}\}\,\] where $\lambda(G)$ is the Lagrangian of $G$. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently\, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. The Lagrangian density of an $r$-uniform hypergraph $H$ is the same as the Turán density of the extension of $H$. Therefore\, these two densities of $H$ equal if every pair of vertices of $H$ is contained in an edge. For example\, to determine the Lagrangian density of $K_4^{3}$ is equivalent to determine the Turán density of $K_4^{3}$. For an $r$-uniform graph $H$ on $t$ vertices\, it is clear that $\pi_{\lambda}(H)\ge r!\lambda{(K_{t-1}^r)}$\, where $K_{t-1}^r$ is the complete $r$-uniform graph on $t-1$ vertices. We say that an $r$-uniform hypergraph $H$ on $t$ vertices is $\lambda$-perfect if $\pi_{\lambda}(H)= r!\lambda{(K_{t-1}^r)}$. A result of Motzkin and Straus implies that all graphs are $\lambda$-perfect. It is interesting to explore what kind of hypergraphs are $\lambda$-perfect. We present some open problems and recent results. \nZi-Xia Song\, Ramsey numbers of cycles under Gallai colorings\nFor 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ő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 (2017). 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 Yaojun Chen and Fangfang Zhang. \nTomáš Kaiser\, Hamilton cycles in tough chordal graphs\nChvátal conjectured in 1973 that all graphs with sufficiently high toughness are Hamiltonian. The conjecture remains open\, but it is known to be true for various classes of graphs\, including chordal graphs\, claw-free graphs or planar graphs. We will discuss the case of chordal graphs and outline our proof that 10-tough chordal graphs are Hamiltonian\, relying on a hypergraph version of Hall’s Theorem as our main tool. This improves a previous result due to Chen et al. (1998) where the constant $10$ is replaced by $18$. Joint work with Adam Kabela. \nMaho Yokota\, Connectivity\, toughness and forbidden subgraph conditions\nLet $\textrm{conn}(G)$ and $\textrm{tough}(G)$ denote the connectivity and the toughness of $G$. We know that low connectivity implies low toughness; if $\textrm{conn}(G)\leq k$\, then $\textrm{tough}(G) \leq k/2$. On the other hand\, we also know the converse is not true. We can construct a graph with high connectivity and low toughness. About this\, we have next proposition. Proposition 1. Let $G$ be a graph\, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>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.
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 Kim (%EA%B9%80%EC%84%9D%EC%A7%84)":MAILTO:skim12@konkuk.ac.kr
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191108T120000
DTEND;TZID=Asia/Seoul:20191109T190000
DTSTAMP:20260424T030050
CREATED:20191004T060008Z
LAST-MODIFIED:20240707T084357Z
UID:1475-1573214400-1573326000@dimag.ibs.re.kr
SUMMARY:Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)
DESCRIPTION:Special Session @ 2019 KSIAM Annual Meeting\nA special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome \nDate\nNov 8\, 2019 – Nov 9\, 2019 Address: 61-13 Odongdo-ro\, Sujeong-dong\, Yeosu-si\, Jeollanam-do (전남 여수시 오동도로 61-13) \nVenue\nVenezia Hotel & Resort Yeosu\, Yeosu\, Korea (여수 베네치아 호텔)  Address: 61-13 Odongdo-ro\, Sujeong-dong\, Yeosu-si\, Jeollanam-do (전남 여수시 오동도로 61-13) \nSpeakers\n\nHyung-Chan An (안형찬)\, Yonsei University\nTony Huynh\, Monash University\nDong Yeap Kang (강동엽)\, KAIST / IBS Discrete Mathematics Group\nDabeen Lee (이다빈)\, IBS Discrete Mathematics Group\nKangbok Lee (이강복)\, POSTECH\nSang-il Oum (엄상일)\, IBS Discrete Mathematics Group / KAIST\nKedong Yan\, Nanjing University of Science and Technology\nSe-Young Yun (윤세영)\, KAIST\n\nSchedules\n\nCombinatorial and Discrete Optimization I: November 8\, 2019 Friday\, 14:20 – 15:40.\n\nKangbok Lee\nKedong Yan\nDabeen Lee\nSe-young Yun\n\n\nCombinatorial and Discrete Optimization II: November 9\, 2019 Saturday\, 10:00 – 11:20.\n\nHyung Chan An\nDong Yeap Kang\nTony Huynh\nSang-il Oum\n\n\n\nAbstracts\nKangbok Lee (이강복)\, Bi-criteria scheduling\n\n\nThe bi-criteria scheduling problems that minimize the two most popular scheduling objectives\, namely the makespan and the total completion time\, are considered. Given a schedule\, makespan\, denoted as $C_\max$\, is the latest completion time of the jobs and the total completion time\, denoted as $\sum C_j$\, is the sum of the completion times of the jobs. These two objectives have received a lot of attention in the literature because of their practical implications. Scheduling problems are somehow difficult to solve even for single criterion. On the other hand\, when it comes to a bi-criteria problem\, a balanced solution coordinating both objectives is indeed essential. In this paper\, we consider bi-criteria scheduling problems on $m$ identical parallel machines where $m$ is 2\, 3 and an arbitrary number\, denoted as $P2 || (C_\max\,\sum􏰂 C_j)$\, $P3 || (C_\max\,􏰂\sum C_j)$ and $P || (C_\max\,􏰂C_j)$\, respectively. For each problem\, we explore its inapproximability and develop an approximation algorithm with analysis of its worst performance.\n\n\nKedong Yan\, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation\n\n\nLogical Analysis of Data (LAD) is a combinatorial optimization-based machine learning method. A key stage of LAD is pattern generation\, where useful knowledge in a training dataset of two types of\, say\, + and − data under analysis is discovered. LAD pattern generation can be cast as a 0-1 multilinear program (MP) with a single 0-1 multilinear constraint: $$(PG): \max\limits_{x\in\{0\,1\}^{2n}}f(x):=\sum_{i\in S^+}\Pi_{j\in J_i}(1-x_j)~~\text{subject to}~~g(x):=\sum_{i\in S^-}\Pi_{j\in J_i}(1-x_j)=0$$\n\n\nThe unconstrained maximization of $f$ (without $g$) is straightforward\, thus the main difficulty of globally maximizing $(PG)$ arises primarily from the presence of g and the interaction between $f$ and $g$. We dealt with the task of linearizing $g$. Namely\, we employed a graph theoretic analysis of data to discover sufficient conditions among neighboring data and also neighboring groups of data for ‘compactly linearizing’ $g$ in terms of a small number of stronger valid inequalities\, as compared to those that can be obtained via 0-1 linearization techniques from the literature. In an earlier work\, we analyzed + and − data (that is\, terms of $f$ and $g$ together) on a graph to develop a polyhedral overestimation scheme for $f$. Extending this line of research\, this paper proposes a new graph representation of monomials in f in conjunction with terms in $g$ to more aggressively aggregate a set of terms/data through each maximal clique in the graph into yielding a stronger valid inequality. This is achieved by means of a new notion of ‘neighbors’ that allows us to join two data that are more than 1-Hamming distance away from each other by an edge in the graph. We show that new inequalities generalize and subsume those from the earlier paper. Furthermore\, with using six benchmark data mining datasets\, we demonstrate that new inequalities are superior to their predecessors in terms of a more efficient global maximization of $(PG)$; that is\, for a more efficient analysis and classification of real-life datasets.\n\n\nDabeen Lee (이다빈)\, Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens\nThe intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk\, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. \nSe-Young Yun (윤세영)\, Optimal sampling and clustering algorithms in the stochastic block model\n\n\nThis paper investigates the design of joint adaptive sampling and clustering algorithms in the Stochastic Block Model (SBM). To extract hidden clusters from the data\, such algorithms sample edges sequentially in an adaptive manner\, and after gathering edge samples\, return cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds reveal the optimal sequential edge sampling strategy\, and interestingly\, the latter does not depend on the sampling budget\, but only the parameters of the SBM. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters\, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process\, which confers the optimality of the algorithm.\n\n\nHyung-Chan An (안형찬)\, Constant-factor approximation algorithms for parity-constrained facility location problems\n\n\nFacility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest\, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of parity in the field of combinatorics. In this paper\, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients\, the opening cost of each facility\, and the parity requirement—$\mathsf{odd}$\, $\mathsf{even}$\, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances\, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap\, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality\, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse $T$-join. Finally\, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper\, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem\, the bottleneck optimization variant.\n\n\nDong Yeap Kang (강동엽)\, On minimal highly connected spanning subgraphs in dense digraphs\nIn 1985\, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges\, and the only extremal digraph is a complete bipartite digraph $DK_{k\,n−k}$. Nevertheless\, since the extremal graph is sparse\, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges\, which is an “almost $k$-regular” subgraph. \n\n\nRecently\, the question of Bang-Jensen was answered in the affirmative with $g(k) = O(k^2\log k)$\, which is best possible up to logarithmic factor. In this talk\, we discuss how to find minimal highly connected spanning subgraphs in dense digraphs as well as tournaments. In particular\, we show that every highly connected dense digraph contains a spanning highly connected subgraph that is almost $k$-regular\, which yields $g(k) = O(k^2)$ that is best possible for tournaments.\n\n\nTony Huynh\, Stable sets in graphs with bounded odd cycle packing number\n\n\nIt is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann\, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus\, there is a polynomial-time algorithm for each fixed $k$. Moreover\, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end\, we show that 2-sided odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed orientable surface Eventually\, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class\, which we prove to be efficiently solvable in our case.\n\n\nSang-il Oum\, Rank-width: Algorithmic and structural results\n\n\nRank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by ‘simple’ cuts. This talk aims to survey known algorithmic and structural results on rank-width of graphs. This talk is based on a survey paper with further remarks on the recent developments.
URL:https://dimag.ibs.re.kr/event/2019-11-08/
LOCATION:Venezia Hotel & Resort Yeosu\, Yeosu\, Korea (여수 베네치아 호텔) 
CATEGORIES:Workshops and Conferences
END:VEVENT
END:VCALENDAR