BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.0.5//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211005T163000
DTEND;TZID=Asia/Seoul:20211005T173000
DTSTAMP:20221209T143610
CREATED:20211005T073000Z
LAST-MODIFIED:20210921T231534Z
UID:4503-1633451400-1633455000@dimag.ibs.re.kr
SUMMARY:Eunjin Oh (오은진)\, Feedback Vertex Set on Geometric Intersection Graphs
DESCRIPTION:I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k\, if it exists\, which runs in time $2^{O(\sqrt{k})}(n + m)$\, where $n$ and $m$ denote the numbers of vertices and edges\, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].
URL:https://dimag.ibs.re.kr/event/2021-10-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211012T163000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20221209T143610
CREATED:20211012T073000Z
LAST-MODIFIED:20210920T020221Z
UID:4374-1634056200-1634059800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, Majority dynamics on sparse random graphs
DESCRIPTION:Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini\, Chan\, O’Donnell\, Tamuz and Tan conjectured that\, in the Erdős-Rényi random graph $G(n\,p)$\, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. \nThis conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis\, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin\, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n\,p)$\, where $\lambda’ n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda’>0$. \nJoint work with Debsoumya Chakraborti\, Jeong Han Kim and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-10-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20221209T143610
CREATED:20211026T073000Z
LAST-MODIFIED:20211013T232013Z
UID:4709-1635265800-1635269400@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, 𝝘-graphic delta-matroids and their applications
DESCRIPTION:Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$\, which generalizes a graphic delta-matroid. \nFor an abelian group $\Gamma$\, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid\, which we call a $\Gamma$-graphic delta-matroid\, and provide a polynomial-time algorithm to solve the separation problem\, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$\, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$\, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$. \nThis is joint work with Duksang Lee and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-10-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211102T163000
DTEND;TZID=Asia/Seoul:20211102T173000
DTSTAMP:20221209T143610
CREATED:20211109T073000Z
LAST-MODIFIED:20211027T072258Z
UID:4780-1635870600-1635874200@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Maximal 3-wise intersecting families
DESCRIPTION:A family $\mathcal F$ of subsets of {1\,2\,…\,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. In 1974\, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family\, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. \nThis is joint work with Kevin Hendrey\, Casey Tompkins\, and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-11-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211109T163000
DTEND;TZID=Asia/Seoul:20211109T173000
DTSTAMP:20221209T143610
CREATED:20211109T073000Z
LAST-MODIFIED:20211027T072336Z
UID:4588-1636475400-1636479000@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, 2-complexes with unique embeddings in 3-space
DESCRIPTION:A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere\, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
URL:https://dimag.ibs.re.kr/event/2021-11-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211123T163000
DTEND;TZID=Asia/Seoul:20211123T173000
DTSTAMP:20221209T143610
CREATED:20211123T073000Z
LAST-MODIFIED:20211115T023536Z
UID:4798-1637685000-1637688600@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Ramsey numbers of Boolean lattices
DESCRIPTION:The poset Ramsey number $R(Q_{m}\,Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2}\,Q_{n})\le2n+2$. Recently\, Lu and Thompson\nimproved the upper bound to $\frac{5}{3}n+2$. In this paper\, we solve this problem asymptotically by showing that $R(Q_{2}\,Q_{n})=n+O(n/\log n)$.\nJoint work with Dániel Grósz and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2021-11-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20221209T143610
CREATED:20211130T073000Z
LAST-MODIFIED:20211204T005349Z
UID:4852-1638289800-1638293400@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, Large clique subdivisions in graphs without small dense subgraphs
DESCRIPTION:What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d\,d}$. However\, this example contains a much smaller subgraph with the almost same average degree\, for example\, one copy of $K_{d\,d}$. \nIn 2017\, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact\, they conjectured that for small enough $\varepsilon>0$\, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d\, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6\,(\log \log c_{\varepsilon}(G))^6\}$-term. \nAs a corollary\, for every graph $F$\, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term. \nThis is joint work with Jaehoon Kim\, Youngjin Kim\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-11-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211207T163000
DTEND;TZID=Asia/Seoul:20211207T173000
DTSTAMP:20221209T143610
CREATED:20211207T073000Z
LAST-MODIFIED:20211204T004721Z
UID:4804-1638894600-1638898200@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION:The independent domination number of a graph $G$\, denoted $i(G)$\, is the minimum size of an independent dominating set of $G$. In this talk\, we prove a series of results regarding independent domination of graphs with bounded maximum degree. \nLet $G$ be a graph with maximum degree at most $k$ where $k \ge 1$. We prove that if $k = 4$\, then $i(G) \le \frac{5}{9}|V(G)|$\, which is tight. Generalizing this result and a result by Akbari et al.\, we suggest a conjecture on the upper bound of $i(G)$ for $k \ge 1$\, which is tight if true. \nLet $G’$ be a connected $k$-regular graph that is not $K_{k\, k}$ where $k\geq 3$. We prove that $i(G’)\le \frac{k-1}{2k-1}|V(G’)|$\, which is tight for $k \in \{3\, 4\}$\, generalizing a result by Lam\, Shiu\, and Sun. This result also answers a question by Goddard et al. in the affirmative. \nIn addition\, we show that $\frac{i(G’)}{\gamma(G’)} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$\, strengthening upon a result of Knor\, Škrekovski\, and Tepeh\, where $\gamma(G’)$ is the domination number of $G’$. \nMoreover\, if we restrict $G’$ to be a cubic graph without $4$-cycles\, then we prove that $i(G’) \le \frac{4}{11}|V(G’)|$\, which improves a result by Abrishami and Henning. \nThis talk is based on joint work with Ilkyoo Choi\, Hyemin Kwon\, and Boram Park.
URL:https://dimag.ibs.re.kr/event/2021-12-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211214T163000
DTEND;TZID=Asia/Seoul:20211214T173000
DTSTAMP:20221209T143610
CREATED:20211214T073000Z
LAST-MODIFIED:20211201T235610Z
UID:4913-1639499400-1639503000@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Exponential decay of intersection volume with applications on list-decodability and sphere-covering bounds
DESCRIPTION:We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking\, this happens when the metric space is (i) expanding and (ii) well-spread\, and (iii) certain random variable on the boundary of a ball has a small tail. As applications\, we show that the volume of intersection of balls in Hamming space and symmetric groups decays exponentially as their centers drift apart. To verify condition (iii)\, we prove some deviation inequalities `on the slice’ for functions with Lipschitz conditions. \nWe then use these estimates on intersection volumes to \n\nobtain a sharp lower bound on list-decodability of random q-ary codes\, confirming a conjecture of Li and Wootters [IEEE Trans. Inf. Theory 2021]; and\nimprove sphere-covering bound from the 70s on constant weight codes by a factor linear in dimension\, resolving a problem raised by Jiang and Vardy [IEEE Trans. Inf. Theory 2004].\n\nOur probabilistic point of view also offers a unified framework to obtain improvements on other sphere-covering bounds\, giving conceptually simple and calculation-free proofs for q-ary codes\, permutation codes\, and spherical codes. \nThis is joint work with Jaehoon Kim and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-12-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220104T163000
DTEND;TZID=Asia/Seoul:20220104T173000
DTSTAMP:20221209T143610
CREATED:20211210T230406Z
LAST-MODIFIED:20211210T230406Z
UID:5000-1641313800-1641317400@dimag.ibs.re.kr
SUMMARY:Seunghun Lee (이승훈)\, Transversals and colorings of simplicial spheres
DESCRIPTION:Motivated from the surrounding property of a point set in $\mathbb{R}^d$ introduced by Holmsen\, Pach and Tverberg\, we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial $d$-spheres\, we provide two infinite constructions. The first construction gives infinitely many $(d+1)$-dimensional simplicial polytopes with the transversal ratio exactly $\frac{2}{d+2}$ for every $d\geq 2$. In the case of $d=2$\, this meets the previously well-known upper bound $1/2$ tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than $1/2$. This was unexpected from what was previously known about the surrounding property. Moreover\, we show that\, for $d\geq 3$\, the facet hypergraph $\mathcal{F}(\mathbf{P})$ of a $(d+1)$-dimensional simplicial polytope $\mathbf{P}$ has the chromatic number $\chi(\mathcal{F}(\mathbf{P})) \in O(n^{\frac{\lceil d/2\rceil-1}{d}})$\, where $n$ is the number of vertices of $\mathbf{P}$. This slightly improves the upper bound previously obtained by Heise\, Panagiotou\, Pikhurko\, and Taraz. This is a joint work with Joseph Briggs and Michael Gene Dobbins.
URL:https://dimag.ibs.re.kr/event/2022-01-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220111T163000
DTEND;TZID=Asia/Seoul:20220111T173000
DTSTAMP:20221209T143610
CREATED:20220111T073000Z
LAST-MODIFIED:20211231T123601Z
UID:5083-1641918600-1641922200@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Some recent results on geometric transversals
DESCRIPTION:A geometric transversal to a family of convex sets in $\mathbb R^d$ is an affine flat that intersects the members of the family. While there exists a far-reaching theory concerning 0-dimensional transversals (intersection patterns of convex sets)\, much less is known when it comes to higher-dimensional transversals. In this talk\, I will present some new and old results and problems regarding geometric transversals\, based on joint work with Otfried Cheong and Xavier Goaoc.
URL:https://dimag.ibs.re.kr/event/2022-01-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220118T163000
DTEND;TZID=Asia/Seoul:20220118T173000
DTSTAMP:20221209T143610
CREATED:20220118T073000Z
LAST-MODIFIED:20220109T234836Z
UID:5105-1642523400-1642527000@dimag.ibs.re.kr
SUMMARY:Jaehyeon Seo (서재현)\, A rainbow Turán problem for color-critical graphs
DESCRIPTION:For given $k$ graphs $G_1\,\dots\, G_k$ over a common vertex set of size $n$\, what conditions on $G_i$ ensures a ‘colorful’ copy of $H$\, i.e. a copy of $H$ containing at most one edge from each $G_i$? \nKeevash\, Saks\, Sudakov\, and Verstraëte defined $\operatorname{ex}_k(n\,H)$ to be the maximum total number of edges of the graphs $G_1\,\dots\, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n\,K_r)$ for large $n$ by showing that\, depending on the value of $k$\, one of the two natural constructions is always the extremal construction. Moreover\, they conjectured the same holds for every color-critical graphs and proved it for $3$-color-critical graphs. \nWe prove their conjecture for $4$-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover\, we show that for every non-color-critical non-bipartite graphs\, none of the two natural constructions is extremal for certain values of $k$. This is a joint work with Debsoumya Chakraborti\, Jaehoon Kim\, Hyunwoo Lee\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2022-01-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220125T163000
DTEND;TZID=Asia/Seoul:20220125T173000
DTSTAMP:20221209T143610
CREATED:20220125T073000Z
LAST-MODIFIED:20220114T044711Z
UID:5129-1643128200-1643131800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
DESCRIPTION:In a reduction sequence of a graph\, vertices are successively identified until the graph has one vertex. At each step\, when identifying $u$ and $v$\, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet\, Kim\, Thomassé\, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$\, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth\, which implies and is stronger than bounded twin-width (reduced-maximum-degree). \nWe show that every proper minor-closed class has bounded reduced-bandwidth\, which is qualitatively stronger than a result of Bonnet et al. for bounded twin-width. In many instances\, we also make quantitative improvements. For example\, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$; moreover\, the witnessing reduction sequence can be constructed in polynomial time. We show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices). \nThis is joint work with Édouard bonnet and David Wood.
URL:https://dimag.ibs.re.kr/event/2022-01-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220208T163000
DTEND;TZID=Asia/Seoul:20220208T173000
DTSTAMP:20221209T143610
CREATED:20220208T073000Z
LAST-MODIFIED:20220126T085511Z
UID:5159-1644337800-1644341400@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION:Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However\, while odd cycles do not satisfy the Erdős-Pósa property\, Reed proved in 1999 an analogue by relaxing packing to half-integral packing\, where each vertex is allowed to be contained in at most two such cycles. Moreover\, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails. \nWe prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property\, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property. \nA multitude of natural properties of cycles can be encoded in this setting. For example\, we show that the cycles of length $\ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property\, and we characterise for which values of $\ell$ and $m$ these cycles satisfy the Erdős-Pósa property. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2022-02-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220215T163000
DTEND;TZID=Asia/Seoul:20220215T173000
DTSTAMP:20221209T143610
CREATED:20220215T073000Z
LAST-MODIFIED:20220213T013932Z
UID:5212-1644942600-1644946200@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION:An independent dominating set of a graph\, also known as a maximal independent set\, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$\, every connected $n$-vertex graph of maximum degree at most $\Delta$ has an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })(n-1)+1$. In addition\, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })n$.\nThis is joint work with Eun-Kyung Cho\, Minki Kim\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2022-02-15/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220221T163000
DTEND;TZID=Asia/Seoul:20220221T173000
DTSTAMP:20221209T143610
CREATED:20220221T073000Z
LAST-MODIFIED:20220214T065551Z
UID:5216-1645461000-1645464600@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, A stronger version of Tutte's wheel theorem for vertex-minors
DESCRIPTION:Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected\, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless it is isomorphic to a wheel. Moreover\, they proved that every simple $3$-connected graph has at least $3$ non-essential edges if and only if it is isomorphic to neither a twisted wheel nor a $k$-dimensional wheel with $k\geq2$. \nWe prove analogous results for graphs with vertex-minors. For a vertex $v$ of a graph $G$\, let $G*v$ be the graph obtained from $G$ by deleting all edges joining two neighbors of $v$ and adding edges joining non-adjacent pairs of two neighbors of $v$. This operation is called the local complementation at $v$\, and we say two graphs are locally equivalent if one can be obtained from the other by applying a sequence of local complementations. A graph $H$ is a vertex-minor of a graph $G$ if $H$ is an induced subgraph of a graph locally equivalent to $G$. A split of a graph is a partition $(A\,B)$ of its vertex set such that $|A|\,|B| \geq 2$ and for some $A’\subseteq A$ and $B’\subseteq B$\, two vertices $x\in A$ and $y\in B$ are adjacent if and only if $x\in A’$ and $y\in B’$. A graph is prime if it has no split. \nA vertex $v$ of a graph is non-essential if at least two of three kinds of vertex-minor reductions at $v$ result in prime graphs. We prove that every prime graph with at least $5$ vertices has at least two non-essential vertices unless it is locally equivalent to a cycle. It is stronger than a theorem proved by Allys (1994)\, which states that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle. As a corollary of our result\, one can obtain the first result of Oxley and Wu. Furthermore\, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor. \nThis is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2022-02-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220228T163000
DTEND;TZID=Asia/Seoul:20220228T173000
DTSTAMP:20221209T143610
CREATED:20220228T073000Z
LAST-MODIFIED:20220227T104738Z
UID:5298-1646065800-1646069400@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
DESCRIPTION:Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors\, but unlike graphs\, this list could be infinite in general. However\, for each fixed finite field $\mathbb F$\, the list contains only finitely many $\mathbb F$-representable matroids\, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen\, A. M. H. Gerards\, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general. \nWe consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$\, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most~$k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute\, for any integer $k$ and a fixed finite field $\mathbb F$\, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$\, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices\, which also results in a similar algorithmic consequence for linear rank-width of graphs. \nThis is joint work with Mamadou M. Kanté\, Eun Jung Kim\, and O-joung Kwon.
URL:https://dimag.ibs.re.kr/event/2022-02-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220307T163000
DTEND;TZID=Asia/Seoul:20220307T173000
DTSTAMP:20221209T143610
CREATED:20220307T073000Z
LAST-MODIFIED:20220302T101458Z
UID:5315-1646670600-1646674200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)
DESCRIPTION:This talk follows on from the recent talk of Pascal Gollin in this seminar series\, but will aim to be accessible for newcomers. \nErdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’\, Reed obtained an analogous result for odd cycles\, and gave a structural characterisation of when the (integral) packing version fails. \nWe prove some far-reaching generalisations of these theorems. First\, we show that if the edges of a graph are labelled by finitely many abelian groups\, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed\, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles. \nWe will look at applications of these results to graphs embedded on surfaces\, and also discuss some possibilities and obstacles for extending these results. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2022-03-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220314T163000
DTEND;TZID=Asia/Seoul:20220314T173000
DTSTAMP:20221209T143610
CREATED:20220314T073000Z
LAST-MODIFIED:20220221T120247Z
UID:5218-1647275400-1647279000@dimag.ibs.re.kr
SUMMARY:Tuan Anh Do\, Rank- and tree-width of supercritical random graphs
DESCRIPTION:It is known that the rank- and tree-width of the random graph $G(n\,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$\, the rank- and tree-width are bounded above by a constant\, for supercritical $p$\, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of Benjamini\, Kozma\, and Wormald on the expansion of supercritical random graphs. We give a new\, short\, and direct proof of these results\, leading to more explicit bounds on these parameters\, and also consider the rank- and tree-width of supercritical random graphs closer to the critical point\, showing that this phase transition is smooth. \nThis is joint work with Joshua Erde and Mihyun Kang.
URL:https://dimag.ibs.re.kr/event/2022-03-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220321T163000
DTEND;TZID=Asia/Seoul:20220321T173000
DTSTAMP:20221209T143610
CREATED:20220321T073000Z
LAST-MODIFIED:20220310T234607Z
UID:5277-1647880200-1647883800@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, Ramsey numbers of cycles versus general graphs
DESCRIPTION:The Ramsey number $R(F\,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$\, provided $n$ is sufficiently large\, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n\,H)=(n-1)(\chi(H)-1)+\sigma(H)$\, where $\sigma(H)$ is the minimum possible size of a colour class in a $\chi(H)$-colouring of $H$. Allen\, Brightwell and Skokan conjectured that the same should be true already when $n\geq |H|\chi(H)$. \nWe improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C|H|\log^4\chi(H)$\, which is optimal up to the logarithmic factor. In particular\, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number. \nThis is joint work with John Haslegrave\, Joseph Hyde and Hong Liu
URL:https://dimag.ibs.re.kr/event/2022-03-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220328T163000
DTEND;TZID=Asia/Seoul:20220328T173000
DTSTAMP:20221209T143610
CREATED:20220314T051725Z
LAST-MODIFIED:20220314T051725Z
UID:5383-1648485000-1648488600@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Thresholds for incidence properties in finite vector spaces
DESCRIPTION:Suppose that $E$ is a subset of $\mathbb{F}_q^n$\, so that each point is contained in $E$ with probability $\theta$\, independently of all other points. Then\, what is the probability that there is an $m$-dimensional affine subspace that contains at least $\ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? We give Erdős-Renyi threshold functions for these properties\, in some cases sharp thresholds. Our results improve previous work of Chen and Greenhill. This is joint work with Jeong Han Kim\, Thang Pham\, and Semin Yoo.
URL:https://dimag.ibs.re.kr/event/2022-03-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220411T163000
DTEND;TZID=Asia/Seoul:20220411T173000
DTSTAMP:20221209T143610
CREATED:20220401T073000Z
LAST-MODIFIED:20220410T120744Z
UID:5326-1649694600-1649698200@dimag.ibs.re.kr
SUMMARY:Younjin Kim (김연진)\, On the extremal problems related to Szemerédi's theorem
DESCRIPTION:In 1975\, Szemerédi proved that for every real number $\delta > 0 $ and every positive integer $k$\, there exists a positive integer $N$ such that every subset $A$ of the set $\{1\, 2\, \cdots\, N \}$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemerédi’s theorem in many areas of mathematics. In 1990\, Cameron and Erdős proposed a conjecture about counting the number of subsets of the set $\{1\,2\, \dots\, N\}$ which do not contain an arithmetic progression of length $k$. In the talk\, we study a natural higher dimensional version of this conjecture\, and also introduce recent extremal problems related to Szemerédi’s theorem.
URL:https://dimag.ibs.re.kr/event/2022-04-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220425T163000
DTEND;TZID=Asia/Seoul:20220425T173000
DTSTAMP:20221209T143610
CREATED:20220425T073000Z
LAST-MODIFIED:20220410T130608Z
UID:5322-1650904200-1650907800@dimag.ibs.re.kr
SUMMARY:Boram Park (박보람)\, Odd coloring of sparse graphs
DESCRIPTION:We introduce an odd coloring of a graph\, which was introduced very recently\, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of times in the neighborhood of $x$. The recent work on this topic will be presented\, and the work is based on Eun-Kyung Cho\, Ilkyoo Choi\, and Hyemin Kown.
URL:https://dimag.ibs.re.kr/event/2022-04-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220502T163000
DTEND;TZID=Asia/Seoul:20220502T173000
DTSTAMP:20221209T143610
CREATED:20220502T073000Z
LAST-MODIFIED:20220426T130131Z
UID:5511-1651509000-1651512600@dimag.ibs.re.kr
SUMMARY:Cheolwon Heo (허철원)\, The complexity of the matroid-homomorphism problems
DESCRIPTION:In this talk\, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$\, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length\, and is otherwise $\rm{NP}$-complete. We also get dichotomies for the list\, extension\, and retraction versions of the problem.\nThis is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University.
URL:https://dimag.ibs.re.kr/event/2022-05-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220509T163000
DTEND;TZID=Asia/Seoul:20220509T173000
DTSTAMP:20221209T143610
CREATED:20220509T073000Z
LAST-MODIFIED:20220425T071741Z
UID:5524-1652113800-1652117400@dimag.ibs.re.kr
SUMMARY:Kyeongsik Nam (남경식)\, Large deviations for subgraph counts in random graphs
DESCRIPTION:The upper tail problem for subgraph counts in the Erdos-Renyi graph\, introduced by Janson-Ruciński\, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts\, called exponential random graph model (ERGM). Despite its importance\, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk\, I will talk about a brief overview on the upper tail problem and the concentration of measure results for the ERGM. Joint work with Shirshendu Ganguly and Ella Hiesmayr.
URL:https://dimag.ibs.re.kr/event/2022-05-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220516T163000
DTEND;TZID=Asia/Seoul:20220516T173000
DTSTAMP:20221209T143610
CREATED:20220516T073000Z
LAST-MODIFIED:20220502T220811Z
UID:5553-1652718600-1652722200@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, A colorful version of the Goodman-Pollack-Wenger transversal theorem
DESCRIPTION:Hadwiger’s transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently generalized to hyperplane transversals in $\mathbb{R}^d$ by Goodman\, Pollack\, and Wenger. Here we establish a colorful extension of their theorem\, which proves a conjecture of Arocha\, Bracho\, and Montejano. The proof uses topological methods\, in particular the Borsuk-Ulam theorem. The same methods also allow us to generalize some colorful transversal theorems of Montejano and Karasev.
URL:https://dimag.ibs.re.kr/event/2022-05-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220523T163000
DTEND;TZID=Asia/Seoul:20220523T173000
DTSTAMP:20221209T143610
CREATED:20220523T073000Z
LAST-MODIFIED:20220516T214605Z
UID:5451-1653323400-1653327000@dimag.ibs.re.kr
SUMMARY:Stijn Cambie\, The precise diameter of reconfiguration graphs
DESCRIPTION:Reconfiguration is about changing instances in small steps. For example\, one can perform certain moves on a Rubik’s cube\, each of them changing its configuration a bit. In this case\, in at most 20 steps\, one can end up with the preferred result. One could construct a graph with as nodes the possible configurations of the Rubik’s cube (up to some isomorphism) and connect two nodes if one can be obtained by applying only one move to the other. Finding an optimal solution\, i.e. a minimum number of moves to solve a Rubik’s cube is now equivalent to finding the distance in the graph. \nWe will wonder about similar problems in reconfiguration\, but applied to list- and DP-colouring. In this case\, the small step consists of recolouring precisely one vertex. Now we will be interested in the diameter of the reconfiguration graph and show that sometimes we can determine the precise diameters of these. \nAs such\, during this talk\, we present some main ideas of [arXiv:2204.07928].
URL:https://dimag.ibs.re.kr/event/2022-05-23/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220530T163000
DTEND;TZID=Asia/Seoul:20220530T173000
DTSTAMP:20221209T143610
CREATED:20220530T073000Z
LAST-MODIFIED:20220523T020807Z
UID:5495-1653928200-1653931800@dimag.ibs.re.kr
SUMMARY:Hongseok Yang (양홍석)\, Learning Symmetric Rules with SATNet
DESCRIPTION:SATNet is a differentiable constraint solver with a custom backpropagation algorithm\, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep learning and logical reasoning. In fact\, SATNet has been successfully applied to learn\, among others\, the rules of a complex logical puzzle\, such as Sudoku\, just from input and output pairs where inputs are given as images. In this paper\, we show how to improve the learning of SATNet by exploiting symmetries in the target rules of a given but unknown logical puzzle or more generally a logical formula. We present SymSATNet\, a variant of SATNet that translates the given symmetries of the target rules to a condition on the parameters of SATNet and requires that the parameters should have a particular parametric form that guarantees the condition. The requirement dramatically reduces the number of parameters to learn for the rules with enough symmetries\, and makes the parameter learning of SymSATNet much easier than that of SATNet. We also describe a technique for automatically discovering symmetries of the target rules from examples. Our experiments with Sudoku and Rubik’s cube show the substantial improvement of SymSATNet over the baseline SATNet. \nThis is joint work with Sangho Lim and Eungyeol Oh.
URL:https://dimag.ibs.re.kr/event/2022-05-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220613T163000
DTEND;TZID=Asia/Seoul:20220613T173000
DTSTAMP:20221209T143610
CREATED:20220613T073000Z
LAST-MODIFIED:20220605T122500Z
UID:5578-1655137800-1655141400@dimag.ibs.re.kr
SUMMARY:Amadeus Reinald\, Twin-width and forbidden subdivisions
DESCRIPTION:Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width\, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse\, notably including bounded rank-width\, $\Omega ( \log (n) )$-subdivisions of graphs of size $n$\, and proper minor closed classes. In this talk\, we look at developing a structural understanding of twin-width in terms of induced subdivisions. \nStructural characterizations of graph parameters have mostly looked at graph minors\, for instance\, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that\, for sparse graphs\, large treewidth implies the existence of an induced subdivision of a large wall. However\, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2\,3}$). Abrishami\, Chudnovsky\, Hajebi and Spirkl have recently shown that such (theta\, triangle)-free classes have nevertheless logarithmic treewidth. \nAfter an introduction to twin-width and its ties to vertex orderings\, we show that theta-free graphs of girth at least 5 have bounded twin-width. \nJoint work with Édouard Bonnet\, Eun Jung Kim\, Stéphan Thomassé and Rémi Watrigant.
URL:https://dimag.ibs.re.kr/event/2022-06-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220627T163000
DTEND;TZID=Asia/Seoul:20220627T173000
DTSTAMP:20221209T143610
CREATED:20220627T073000Z
LAST-MODIFIED:20220627T115421Z
UID:5733-1656347400-1656351000@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Radial projections in finite space
DESCRIPTION:Given a set $E$ and a point $y$ in a vector space over a finite field\, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that through $y$ and points of $E$. Clearly\, $|\pi_y(E)|$ is at most the minimum of the number of lines through $y$ and $|E|$. I will discuss several results on the general question: For how many points $y$ can $|\pi_y(E)|$ be much smaller than this maximum? \nThis is motivated by an analogous question in fractal geometry. The Hausdorff dimension of a radial projection of a set $E$ in $n$ dimensional real space will typically be the minimum of $n-1$ and the Hausdorff dimension of $E$. Several recent papers by authors including Matilla\, Orponen\, Liu\, Shmerikin\, and Wang consider the question: How large can the set of points with small radial projections be? This body of work has several important applications\, including recent progress on the Falconer distance conjecture. \nThis is joint with Thang Pham and Vu Thi Huong Thu.
URL:https://dimag.ibs.re.kr/event/2022-06-27/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR