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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220228T163000
DTEND;TZID=Asia/Seoul:20220228T173000
DTSTAMP:20260506T162633
CREATED:20220228T073000Z
LAST-MODIFIED:20240707T080351Z
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:20220221T163000
DTEND;TZID=Asia/Seoul:20220221T173000
DTSTAMP:20260506T162633
CREATED:20220221T073000Z
LAST-MODIFIED:20240707T080414Z
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:20220215T163000
DTEND;TZID=Asia/Seoul:20220215T173000
DTSTAMP:20260506T162633
CREATED:20220215T073000Z
LAST-MODIFIED:20240707T080430Z
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:20220208T163000
DTEND;TZID=Asia/Seoul:20220208T173000
DTSTAMP:20260506T162633
CREATED:20220208T073000Z
LAST-MODIFIED:20240707T080447Z
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:20220125T163000
DTEND;TZID=Asia/Seoul:20220125T173000
DTSTAMP:20260506T162633
CREATED:20220125T073000Z
LAST-MODIFIED:20240705T175100Z
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:20220118T163000
DTEND;TZID=Asia/Seoul:20220118T173000
DTSTAMP:20260506T162633
CREATED:20220118T073000Z
LAST-MODIFIED:20240707T080518Z
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:20220111T163000
DTEND;TZID=Asia/Seoul:20220111T173000
DTSTAMP:20260506T162633
CREATED:20220111T073000Z
LAST-MODIFIED:20240707T080542Z
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:20220104T163000
DTEND;TZID=Asia/Seoul:20220104T173000
DTSTAMP:20260506T162633
CREATED:20211210T230406Z
LAST-MODIFIED:20240707T080549Z
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:20211214T163000
DTEND;TZID=Asia/Seoul:20211214T173000
DTSTAMP:20260506T162633
CREATED:20211214T073000Z
LAST-MODIFIED:20240705T180035Z
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:20211207T163000
DTEND;TZID=Asia/Seoul:20211207T173000
DTSTAMP:20260506T162633
CREATED:20211207T073000Z
LAST-MODIFIED:20240707T080616Z
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:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20260506T162633
CREATED:20211130T073000Z
LAST-MODIFIED:20240707T080630Z
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:20211123T163000
DTEND;TZID=Asia/Seoul:20211123T173000
DTSTAMP:20260506T162633
CREATED:20211123T073000Z
LAST-MODIFIED:20240707T080759Z
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:20211109T163000
DTEND;TZID=Asia/Seoul:20211109T173000
DTSTAMP:20260506T162633
CREATED:20211109T073000Z
LAST-MODIFIED:20240705T181024Z
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:20211102T163000
DTEND;TZID=Asia/Seoul:20211102T173000
DTSTAMP:20260506T162633
CREATED:20211109T073000Z
LAST-MODIFIED:20240707T080853Z
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:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20260506T162633
CREATED:20211026T073000Z
LAST-MODIFIED:20240707T080901Z
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:20211012T163000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20260506T162633
CREATED:20211012T073000Z
LAST-MODIFIED:20240707T080915Z
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:20211005T163000
DTEND;TZID=Asia/Seoul:20211005T173000
DTSTAMP:20260506T162633
CREATED:20211005T073000Z
LAST-MODIFIED:20240707T080940Z
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:20210928T163000
DTEND;TZID=Asia/Seoul:20210928T173000
DTSTAMP:20260506T162633
CREATED:20210928T073000Z
LAST-MODIFIED:20240707T080955Z
UID:4452-1632846600-1632850200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Extremal functions for sparse minors
DESCRIPTION:The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor\, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005)\, Norin\, Reed\, Thomason and Wood (2020)\, and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$\, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results\, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example\, we prove that for every planar graph $H$\, \[c(H) = (1+o(1))\max (v(H)/2\, v(H)-\alpha(H))\,\] extending recent results of Haslegrave\, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.
URL:https://dimag.ibs.re.kr/event/2021-09-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210907T163000
DTEND;TZID=Asia/Seoul:20210907T173000
DTSTAMP:20260506T162633
CREATED:20210907T073000Z
LAST-MODIFIED:20240705T182054Z
UID:4495-1631032200-1631035800@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Mixing sets\, submodularity\, and chance-constrained optimization
DESCRIPTION:A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk\, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular\, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then\, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. 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. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.
URL:https://dimag.ibs.re.kr/event/2021-09-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210831T163000
DTEND;TZID=Asia/Seoul:20210831T173000
DTSTAMP:20260506T162633
CREATED:20210831T073000Z
LAST-MODIFIED:20240707T081024Z
UID:4341-1630427400-1630431000@dimag.ibs.re.kr
SUMMARY:Cheolwon Heo (허철원)\, Representations of even-cycle matroids
DESCRIPTION:A signed graph is a pair $(G\,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. A cycle $C$ of $G$ is a subset of edges of $G$ such that every vertex of the subgraph of $G$ induced by $C$ has an even degree. We say that $C$ is even in $(G\,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise\, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G\,\Sigma)$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G\,\Sigma)$. For even-cycle matroids\, two fundamental questions arise:\n(1) what is the relationship between two signed graphs representing the same even-cycle matroids?\n(2) how many signed graphs can an even-cycle matroid have?\nFor (a)\, we characterize two signed graphs $(G_1\,\Sigma_1)$ and $(G_2\,\Sigma_2)$ where $G_1$ and $G_2$ are $4$-connected that represent the same even-cycle matroids.\nFor (b)\, we introduce pinch-graphic matroids\, which can generate exponentially many representations even when the matroid is $3$-connected. An even-cycle matroid is a pinch-graphic matroid if there exists a signed graph with a pair of vertices such that every odd cycle intersects with at least one of them. We prove that there exists a constant $c$ such that if a matroid is even-cycle matroid that is not pinch-graphic\, then the number of representations is bounded by $c$. This is joint work with Bertrand Guenin and Irene Pivotto.
URL:https://dimag.ibs.re.kr/event/2021-08-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210824T163000
DTEND;TZID=Asia/Seoul:20210824T173000
DTSTAMP:20260506T162633
CREATED:20210810T073000Z
LAST-MODIFIED:20240707T081032Z
UID:4212-1629822600-1629826200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, A Constant-factor Approximation for Weighted Bond Cover
DESCRIPTION:The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks\, given a weighted graph $G$\, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal F$-Vertex Deletion. Only three cases of minor-closed $\mathcal F$ are known to admit constant-factor approximations\, namely Vertex Cover\, Feedback Vertex Set and Diamond Hitting Set. \nWe study the problem for the class $\mathcal F$ of $\theta_c$-minor-free graphs\, under the equivalent setting of the Weighted c-Bond Cover\, and present a constant-factor approximation algorithm using the primal-dual method. For this\, we leverage a structure theorem implicit in [Joret et al.\, SIDMA’14] which states the following: any graph $G$ containing a $\theta_c$-minor-model either contains a large two-terminal protrusion\, or contains a constant-size $\theta_c$-minor-model\, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case\, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case\, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal F$-Vertex Deletion\, our result may be useful as a template for algorithms for other minor-closed families. \nThis is joint work with Euiwoong Lee and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2021-08-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210817T163000
DTEND;TZID=Asia/Seoul:20210817T173000
DTSTAMP:20260506T162633
CREATED:20210817T073000Z
LAST-MODIFIED:20240707T081153Z
UID:4242-1629217800-1629221400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Two results on graphs with holes of restricted lengths
DESCRIPTION:We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006\, Chudnovksy\, Seymour\, Robertson\, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield\, Myriam Preissmann\, Paul Seymour\, Ni Luh Dewi Sintiari\, Cléophée Robin\, Nicolas Trotignon\, and Kristina Vuškovíc. \nAnalysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991\, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex $v \in V(G)$. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003\, Chudnovsky\, Kawarabayashi\, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019\, Chudnovsky\, Scott\, Seymour\, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year\, Chudnovsky\, Scott\, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least $\ell$ for any fixed integer $\ell \geq 5$. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.
URL:https://dimag.ibs.re.kr/event/2021-08-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210810T163000
DTEND;TZID=Asia/Seoul:20210810T173000
DTSTAMP:20260506T162633
CREATED:20210817T073000Z
LAST-MODIFIED:20240705T183002Z
UID:4408-1628613000-1628616600@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Intertwining connectivities for vertex-minors and pivot-minors
DESCRIPTION:We show that for pairs (Q\,R) and (S\,T) of disjoint subsets of vertices of a graph G\, if G is sufficiently large\, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids. Joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-08-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210727T150000
DTEND;TZID=Asia/Seoul:20210727T160000
DTSTAMP:20260506T162633
CREATED:20210623T055635Z
LAST-MODIFIED:20240707T081214Z
UID:4288-1627398000-1627401600@dimag.ibs.re.kr
SUMMARY:Euiwoong Lee (이의웅)\, The Karger-Stein algorithm is optimal for k-cut
DESCRIPTION:In the k-cut problem\, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of $O(n^{2k-2})$. Using tree packings\, Thorup gave a deterministic algorithm that has the same running time. \nIn this work\, we show that for any fixed $k\ge 2$\, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least $\Omega(n^{-k})$. This also gives an extremal bound of $O(n^k)$ on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta)OPT/k$\, using the Sunflower lemma. \nJoint work with Anupam Gupta\, David G. Harris\, and Jason Li.
URL:https://dimag.ibs.re.kr/event/2021-07-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210720T163000
DTEND;TZID=Asia/Seoul:20210720T173000
DTSTAMP:20260506T162633
CREATED:20210601T234138Z
LAST-MODIFIED:20240707T081226Z
UID:4190-1626798600-1626802200@dimag.ibs.re.kr
SUMMARY:Semin Yoo (유세민)\, Combinatorics of Euclidean spaces over finite fields
DESCRIPTION:$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$\, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients\, denoted by $\binom{n}{k}_{q}$\, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$\, this reverts to the binomial coefficients which measure the number of $k$-sets in $\left [ n \right ]$. \nIn this talk\, we add one more structure in $\mathbb{F}_{q}^{n}$\, which is the Euclidean quadratic form: $\text{dot}_{n}:=x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}$. It turns out that the number of quadratic subspaces of Euclidean type in $(\mathbb{F}_{q}^{n}\,\text{dot}_{n})$ can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to define the dot-analogues of the binomial coefficients and to study related combinatorics. No prior knowledge about the theory of quadratic form is required.
URL:https://dimag.ibs.re.kr/event/2021-07-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210713T163000
DTEND;TZID=Asia/Seoul:20210713T173000
DTSTAMP:20260506T162633
CREATED:20210519T133727Z
LAST-MODIFIED:20240707T081244Z
UID:4110-1626193800-1626197400@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, $K_{r+1}$-saturated graphs with small spectral radius
DESCRIPTION:For a graph $H$\, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$\, $G+e$ contains $H$. In this note\, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to \infty$.
URL:https://dimag.ibs.re.kr/event/2021-07-13/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210706T163000
DTEND;TZID=Asia/Seoul:20210706T173000
DTSTAMP:20260506T162633
CREATED:20210518T100610Z
LAST-MODIFIED:20240707T081252Z
UID:4101-1625589000-1625592600@dimag.ibs.re.kr
SUMMARY:Suil O (오수일)\, Eigenvalues and [a\, b]-factors in regular graphs
DESCRIPTION:For positive integers\, $r \ge 3\, h \ge 1\,$ and $k \ge 1$\, Bollobás\, Saito\, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third-largest eigenvalue in a connected $r$-regular graph to have a $k$-factor in 2010. Gu found an upper bound for certain eigenvalues in an $h$-edge-connected $r$-regular graph to have a $k$-factor in 2014. For positive integers $a \le b$\, an even (or odd) $[a\, b]$-factor of a graph $G$ is a spanning subgraph $H$ such that for each vertex $v \in V (G)$\, $d_H(v)$ is even (or odd) and $a \le d_H(v) \le b$. In this talk\, we provide best upper bounds (in terms of $a\, b$\, and $r$) for certain eigenvalues (in terms of $a\, b\, r$\, and $h$) in an $h$-edge-connected $r$-regular graph $G$ to guarantee the existence of an even $[a\, b]$-factor or an odd $[a\, b]$-factor. This result extends the one of Bollobás\, Saito\, and Wormald\, the one of Lu\, and the one of Gu.
URL:https://dimag.ibs.re.kr/event/2021-07-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210629T163000
DTEND;TZID=Asia/Seoul:20210629T173000
DTSTAMP:20260506T162633
CREATED:20210614T232723Z
LAST-MODIFIED:20240707T081306Z
UID:4251-1624984200-1624987800@dimag.ibs.re.kr
SUMMARY:Jeong Ok Choi (최정옥)\, Invertibility of circulant matrices of arbitrary size
DESCRIPTION:In this talk\, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the entries in the first row with integer coefficients. Using these conditions we show the invertibility of some family of circulant matrices with particular forms of integers generated by a primitive element in $\mathbb{Z}_p$. Also\, the invertibility of circulant 0\, 1-matrices can be argued combinatorially by applying sufficient conditions. This is joint work with Youngmi Hur.
URL:https://dimag.ibs.re.kr/event/2021-06-29/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210622T163000
DTEND;TZID=Asia/Seoul:20210622T173000
DTSTAMP:20260506T162633
CREATED:20210430T062352Z
LAST-MODIFIED:20240705T184213Z
UID:4028-1624379400-1624383000@dimag.ibs.re.kr
SUMMARY:Hongseok Yang (양홍석)\, DAG-symmetries and Symmetry-Preserving Neural Networks
DESCRIPTION:The preservation of symmetry is one of the key tools for designing data-efficient neural networks. A representative example is convolutional neural networks (CNNs); they preserve translation symmetries\, and this symmetry preservation is often attributed to their success in real-world applications. In the machine-learning community\, there is a growing body of work that explores a new type of symmetries\, both discrete and continuous\, and studies neural networks that preserve those symmetries. \nIn this talk\, I will explain what I call DAG-symmetries and our preliminary results on the shape of neural networks that preserve these symmetries. DAG-symmetries are finite variants of DAG-exchangeability developed by Jung\, Lee\, Staton\, and Yang (2020) in the context of probabilistic symmetries. Using these symmetries\, we can express that when a neural network works on\, for instance\, sets of bipartite graphs whose edges are labelled with reals\, the network depends on neither the order of elements in the set nor the identities of vertices of the graphs. I will explain how a group of specific DAG-symmetries is constructed by applying a form of wreath product over a given finite DAG. Then\, I will explain what linear layers of neural networks preserving these symmetries should look like. \nThis is joint work with Dongwoo Oh.
URL:https://dimag.ibs.re.kr/event/2021-06-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210608T150000
DTEND;TZID=Asia/Seoul:20210608T160000
DTSTAMP:20260506T162633
CREATED:20210514T092018Z
LAST-MODIFIED:20240707T081316Z
UID:4080-1623164400-1623168000@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Classes of intersection digraphs with good algorithmic properties
DESCRIPTION:An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v\, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs\, not many algorithmic applications on intersection digraphs have been developed. \nMotivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width\, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular\, we show that as a natural extension of $H$-graphs\, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$\, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020] \nFor applications\, we introduce a novel framework of directed versions of locally checkable problems\, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width\, when a branch decomposition is given. Locally checkable problems include Kernel\, Dominating Set\, and Directed $H$-Homomorphism. \nThis seminar is a part of the\n“Round the World Relay in Combinatorics”\non June 8\, 2021.\nhttp://people.maths.ox.ac.uk/scott/relay.htm \n\n2:00 UTC\, 11:00 KST Melbourne (Australia) Monash University\nDavid Wood (Monash University)\, Universality in Minor-Closed Graph Classes\n3:00 UTC\, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences\nBaogang Xu (Nanjing Normal University\, China)\, On coloring of graphs of girth 2l+1 without longer odd holes\n4:00 UTC\, 13:00 KST Auckland (New Zealand) The University of Auckland\nJeroen Schillewaert (University of Auckland)\, Constructing highly regular expanders from hyperbolic Coxeter groups\n5:00 UTC\, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia\nGordon Royle (University of Western Australia (UWA))\, Real chromatic roots of planar graphs\n6:00 UTC\, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group\nO-joung Kwon (Incheon National University and IBS Discrete Mathematics Group)\, Classes of intersection digraphs with good algorithmic properties\n7:00 UTC\, 16:00 KST Krakow (Poland) Jagiellonian University\nBartosz Walczak (Jagiellonian)\, Coloring polygon visibility graphs and their generalizations\n8:00 UTC\, 17:00 KST Glasgow (UK) University of Glasgow\nHeng Guo (University of Edinburgh)\, A Markov chain approach towards the sampling Lovász local lemma\n9:00 UTC\, 18:00 KST London (UK) London School of Economics\nAnnika Heckel (LMU)\, How does the chromatic number of a random graph vary?\n10:00 UTC\, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology\nNoga Alon (Princeton and Tel Aviv)\n11:00 UTC\, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University\nLászló Lovász (Eotvos University\, Budapest)\n12:00 UTC\, 21:00 KST Bordeaux (France) LaBRI\nCarla Groenland (Utrecht University)\, Universal Graphs and Labelling Schemes\n13:00 UTC\, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University\nDeepak Bal (Montclair State University)\n14:00 UTC\, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics\nDhruv Mubayi (University of Illinois at Chicago)\, The feasible region of hypergraphs\n15:00 UTC\, 00:00 KST Brno (Czech) Masaryk University\nJames Davies (University of Waterloo)\, Colouring circle graphs and their generalisations\n16:00 UTC\, 01:00 KST Oxford (UK) University of Oxford\nJacob Fox (Stanford University)\, Removal lemmas\n17:00 UTC\, 02:00 KST Columbus (USA) Ohio State University\nAllan Sly (Princeton University)\n18:00 UTC\, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada\nMarcelo Campos (IMPA)\, The singularity probability of a random symmetric matrix is exponentially small\n19:00 UTC\, 04:00 KST Atlanta (USA) Georgia Institute of Technology\nJim Geelen (University of Waterloo)\, Homomorphisms and colouring for graphs and binary matroids\n20:00 UTC\, 05:00 KST Santiago (Chile) Universidad de Chile\nDavid Conlon (Caltech)\n21:00 UTC\, 06:00 KST Burnaby (Canada) Simon Fraser University\nFan Chung (UCSD)\, Trees and forests in Green’s functions of a graph\n22:00 UTC\, 07:00 KST Victoria (Canada) University of Victoria\nAndrew Suk (UCSD)\, Turán-type problems for point-line incidences\n23:00 UTC\, 08:00 KST Fairbanks (USA) University of Alaska\nRon Gould (Emory)\, Chorded cycles\n\n 
URL:https://dimag.ibs.re.kr/event/2021-06-08/
LOCATION:Zoom ID: 875 9395 3555 (relay) [CLOSED]
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR