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:20220509T163000
DTEND;TZID=Asia/Seoul:20220509T173000
DTSTAMP:20260418T000627
CREATED:20220509T073000Z
LAST-MODIFIED:20240705T173026Z
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:20220502T163000
DTEND;TZID=Asia/Seoul:20220502T173000
DTSTAMP:20260418T000627
CREATED:20220502T073000Z
LAST-MODIFIED:20240707T080029Z
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:20220427T163000
DTEND;TZID=Asia/Seoul:20220427T173000
DTSTAMP:20260418T000627
CREATED:20220427T073000Z
LAST-MODIFIED:20240705T173041Z
UID:5399-1651077000-1651080600@dimag.ibs.re.kr
SUMMARY:Michael Savery\, Induced subgraphs of induced subgraphs of large chromatic number
DESCRIPTION:We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy of F.) This generalises recent theorems of Briański\, Davies and Walczak\, and of Carbonero\, Hompe\, Moore and Spirkl. We further show an analogous statement where clique number is replaced by odd girth. This is joint work with Antonio Girão\, Freddie Illingworth\, Emil Powierski\, Alex Scott\, Youri Tamitegama and Jane Tan.
URL:https://dimag.ibs.re.kr/event/2022-04-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220425T163000
DTEND;TZID=Asia/Seoul:20220425T173000
DTSTAMP:20260418T000627
CREATED:20220425T073000Z
LAST-MODIFIED:20240707T080049Z
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:20220413T163000
DTEND;TZID=Asia/Seoul:20220413T173000
DTSTAMP:20260418T000627
CREATED:20220413T073000Z
LAST-MODIFIED:20240707T080102Z
UID:5378-1649867400-1649871000@dimag.ibs.re.kr
SUMMARY:Jakub Gajarský\, Model Checking on Interpretations of Classes of Bounded Local Clique-Width
DESCRIPTION:The first-order model checking problem for finite graphs asks\, given a graph G and a first-order sentence $\phi$ as input\, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems\, such as independent set\, distance-r dominating set\, and many others. \nWhile the first-order model-checking problem is likely not efficiently solvable in general\, efficient algorithms exist for various restricted graph classes\, such as graphs of bounded degree\, planar graphs etc. After the existence of an efficient model checking algorithm was shown for nowhere dense classes of graphs (which include most of commonly studied classes of sparse graphs)\, the attention turned to the more general setting of graph classes which can be obtained from sparse graphs using graph transformations called interpretations/transductions. However\, despite efforts of several groups of researchers\, no positive algorithmic result has been achieved since 2016\, when the existence of an efficient algorithm was shown for graph classes interpretable in graphs of bounded degree. \nWe present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local clique-width. Notably\, this includes interpretations of planar graphs (and more generally\, of locally bounded treewidth) and vastly generalizes the result for interpretations of graphs of bounded degree. To obtain this result we developed a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future. \nThis is joint work with Édouard Bonnet\, Jan Dreier\, Stephan Kreutzer\, Nikolas Mählmann\, Pierre Simon\, Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2022-04-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220411T163000
DTEND;TZID=Asia/Seoul:20220411T173000
DTSTAMP:20260418T000627
CREATED:20220401T073000Z
LAST-MODIFIED:20240707T080114Z
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;VALUE=DATE:20220404
DTEND;VALUE=DATE:20220407
DTSTAMP:20260418T000627
CREATED:20220311T230000Z
LAST-MODIFIED:20240707T080124Z
UID:5370-1649030400-1649289599@dimag.ibs.re.kr
SUMMARY:IBS ECOPRO Opening conference
DESCRIPTION:To celebrate the opening of the IBS ECOPRO (Extremal Combinatorics and Probability) Group\, we will organize a 3-day online conference from April 4 to April 6. \nOfficial Website: https://www.ibs.re.kr/ecopro/event/opening/ \nInvited Speakers\n\n\n\n\n\nNoga Alon\nPrinceton University \n\n\n\n\n\nJózsef Balogh\nUniversity of Illinois at Urbana-Champaign \n\n\n\n\n\nJeff Kahn\nRutgers University \n\n\n\n\n\n\n\nMihyun Kang\nGraz University of Technology \n\n\n\n\n\nJeong Han Kim\nKIAS \n\n\n\n\n\nNati Linial\nHebrew University of Jerusalem \n\n\n\n\n\n\n\nOleg Pikhurko\nUniversity of Warwick \n\n\n\n\n\nBenny Sudakov\nETH Zürich \n\n\n\n\n\nTibor Szabó\nFreie Universität Berlin \n\n\n\n\n\n\n\nVan Vu\nYale \n\n\n\n\n\n\n\n\nProgram\n\n\n\n\nTime in Korea\nMonday\nTuesday\nWednesday\n\n\n\n\n7:15 PM\nKim\n\n\n\n\n8:00 PM\nPikhurko\nKang\nVu\n\n\n8:45 PM\nKahn\nBalogh\nSzabó\n\n\n9:30 PM\nAlon\nSudakov\nLinial\n\n\n\n\n\nOrganizers\n\nJaehoon Kim\, KAIST\nHong Liu\, IBS Extremal Combinatorics and Probability Group\nSang-il Oum\, IBS Discrete Mathematics Group / KAIST\nTuan Tran\, IBS Discrete Mathematics Group
URL:https://dimag.ibs.re.kr/event/ibs-ecopro-opening-conference/
LOCATION:Zoom ID: 878 0445 3986 (ibsecopro) [CLOSED]
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220330T163000
DTEND;TZID=Asia/Seoul:20220330T173000
DTSTAMP:20260418T000627
CREATED:20220330T073000Z
LAST-MODIFIED:20240707T080136Z
UID:5270-1648657800-1648661400@dimag.ibs.re.kr
SUMMARY:Jean-Florent Raymond\, Long induced paths in minor-closed graph classes and beyond
DESCRIPTION:In 1982 Galvin\, Rival\, and Sands proved that in $K_{t\,t}$-subgraph free graphs (t being fixed)\, the existence of a path of order n guarantees the existence of an induced path of order f(n)\, for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs. \nIn this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be used to prove the two following generalizations: \n\nevery graph of treewidth less than k that has a path of order n contains an induced path of order $Ω((\log n)^{1/k})$;\nfor every non-trivial graph class that is closed under topological minors there is a constant d∈(0\,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((\log n)^d)$.\n\nJoint work with Claire Hilaire.
URL:https://dimag.ibs.re.kr/event/2022-03-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220328T163000
DTEND;TZID=Asia/Seoul:20220328T173000
DTSTAMP:20260418T000627
CREATED:20220314T051725Z
LAST-MODIFIED:20240707T080143Z
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:20220321T163000
DTEND;TZID=Asia/Seoul:20220321T173000
DTSTAMP:20260418T000627
CREATED:20220321T073000Z
LAST-MODIFIED:20240707T080150Z
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;VALUE=DATE:20220320
DTEND;VALUE=DATE:20220328
DTSTAMP:20260418T000627
CREATED:20220131T150000Z
LAST-MODIFIED:20240705T175059Z
UID:3527-1647734400-1648425599@dimag.ibs.re.kr
SUMMARY:MATRIX-IBS Workshop: Structural Graph Theory Downunder II
DESCRIPTION:This program consists of a short intensive workshop\, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors\, graph colouring\, Hadwiger’s Conjecture\, bounded expansion classes\, graph product structure theory\, generalised colouring numbers\, VC dimension\, induced subgraphs\, Erdős-Hajnal conjecture\, Gyárfás-Sumner conjecture\, twin-width\, asymptotic dimension. The majority of the time will be allocated to collaborative research (with only a few talks). The goal is to create an environment where mathematicians at all career stages work side-by-side. We anticipate that open problems will be solved\, and lasting collaborations will be initiated. \nURL: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-ll/ \nRegistration is by invitation only. If you are interested to participate in this research program\, please contact one of the organisers with your CV and research background. \n 
URL:https://dimag.ibs.re.kr/event/2022-03-20/
LOCATION:MATRIX\, Australia
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220314T163000
DTEND;TZID=Asia/Seoul:20220314T173000
DTSTAMP:20260418T000627
CREATED:20220314T073000Z
LAST-MODIFIED:20240705T174136Z
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:20220310T163000
DTEND;TZID=Asia/Seoul:20220310T173000
DTSTAMP:20260418T000627
CREATED:20220310T073000Z
LAST-MODIFIED:20240705T174146Z
UID:5176-1646929800-1646933400@dimag.ibs.re.kr
SUMMARY:Fedor Fomin\, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms
DESCRIPTION:We examine algorithmic extensions of two classic results of extremal combinatorics. First\, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1\, is either Hamiltonian or contains a cycle of length at least 2d. Second\, the theorem of Erdős-Gallai from 1959\, states that a 2-connected graph G with the average vertex degree D>1\, contains a cycle of length at least D. \nWe discuss the recent progress in parameterized complexity of computing long cycles “above” the guarantees established by these classical theorems: cycles of lengths at least 2d+k and D+k. \nThe talk is based on the joint works with Petr Golovach\, Danil Sagunov\, and Kirill Simonov.
URL:https://dimag.ibs.re.kr/event/2022-03-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220307T163000
DTEND;TZID=Asia/Seoul:20220307T173000
DTSTAMP:20260418T000627
CREATED:20220307T073000Z
LAST-MODIFIED:20240705T174154Z
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:20220228T163000
DTEND;TZID=Asia/Seoul:20220228T173000
DTSTAMP:20260418T000627
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:20260418T000627
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:20220218T100000
DTEND;TZID=Asia/Seoul:20220218T110000
DTSTAMP:20260418T000627
CREATED:20220218T010000Z
LAST-MODIFIED:20240705T174212Z
UID:5154-1645178400-1645182000@dimag.ibs.re.kr
SUMMARY:Manuel Lafond\, Recognizing k-leaf powers in polynomial time\, for constant k
DESCRIPTION:A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G)\, and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology\, but recognizing them has remained a challenging algorithmic problem for the past two decades. In a recent paper presented at SODA22\, it was shown that k-leaf powers can be recognized in polynomial time if k is fixed. \nIn this seminar\, I will present the algorithm that decides whether a graph G is a k-leaf power in time $O(n^{f(k)})$ for some function f that depends only on k (but has the growth rate of a power tower function). More specifically\, I will discuss how the difficult k-leaf power instances contain many cutsets that have the same neighborhood layering. I will then show that these similar cutsets are redundant and that removing one of them does not lose any information\, which can be exploited for algorithmic purposes.
URL:https://dimag.ibs.re.kr/event/2022-02-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220215T163000
DTEND;TZID=Asia/Seoul:20220215T173000
DTSTAMP:20260418T000627
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:20220210T163000
DTEND;TZID=Asia/Seoul:20220210T173000
DTSTAMP:20260418T000627
CREATED:20220210T073000Z
LAST-MODIFIED:20240707T080439Z
UID:5183-1644510600-1644514200@dimag.ibs.re.kr
SUMMARY:James Davies\, Separating polynomial $\chi$-boundedness from $\chi$-boundedness
DESCRIPTION:We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$\, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$\, the maximum chromatic number of a graph in $\mathcal{G}$ with clique number $\omega$ is equal to $g(\omega)$. This extends a recent breakthrough of Carbonero\, Hompe\, Moore\, and Spirk. In particular\, this proves that there are hereditary classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. \nJoint work with Marcin Briański and Bartosz Walczak.
URL:https://dimag.ibs.re.kr/event/2022-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220208T163000
DTEND;TZID=Asia/Seoul:20220208T173000
DTSTAMP:20260418T000627
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:20220127T163000
DTEND;TZID=Asia/Seoul:20220127T173000
DTSTAMP:20260418T000627
CREATED:20211230T013247Z
LAST-MODIFIED:20240705T180010Z
UID:5080-1643301000-1643304600@dimag.ibs.re.kr
SUMMARY:Bo Ning (宁博)\, Substructures and eigenvalues of graphs: Triangles and quadrilaterals
DESCRIPTION:Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a conjecture of Bollobás and Nikiforov and a classical result of Nosal on triangles. In particular\, we shall present counting results for previous spectral theorems on triangles and quadrilaterals. If time allows\, we will give a sketch for the proof of one new counting result on triangles.
URL:https://dimag.ibs.re.kr/event/2022-01-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220125T163000
DTEND;TZID=Asia/Seoul:20220125T173000
DTSTAMP:20260418T000627
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:20220120T163000
DTEND;TZID=Asia/Seoul:20220120T173000
DTSTAMP:20260418T000627
CREATED:20220120T073000Z
LAST-MODIFIED:20240705T175100Z
UID:4564-1642696200-1642699800@dimag.ibs.re.kr
SUMMARY:Ken-ichi Kawarabayashi (河原林 健一)\, Toward Directed Graph Minor Theory
DESCRIPTION:Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. It also gives many exciting algorithmic consequences. \nIn this work\, I would like to talk about our attempt to extend Graph minor project to directed graphs. Topics include \n1. The directed grid theorem\n2. The directed flat wall theorem\n3. Tangle tree decomposition\n4. Variant of the directed disjoint paths problems\n5. Toward the structure (and decomposition) theorem for H-minor-free digraphs. \nJoint work with Stephan Kreutzer\, O-joung Kwon\, Archontia Giannopoulou.
URL:https://dimag.ibs.re.kr/event/2022-01-20/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220118T163000
DTEND;TZID=Asia/Seoul:20220118T173000
DTSTAMP:20260418T000627
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:20220113T163000
DTEND;TZID=Asia/Seoul:20220113T173000
DTSTAMP:20260418T000627
CREATED:20220113T073000Z
LAST-MODIFIED:20240707T080528Z
UID:5009-1642091400-1642095000@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, A strong version of the Caccetta-Haggkvist conjecture
DESCRIPTION:The Caccetta-Haggkvist conjecture\, one of the best known in graph theory\, is that in a digraph with $n$ vertices in which all outdegrees are at least $n/k$ there is a directed cycle of length at most $k$. This is known for  large values of $k$\, relatively to n\, and asymptotically for n large. A few years ago I offered a generalization: given sets $F_1$\, $\ldots$\, $F_n$ of sets of undirected edges\, each of size at least $n/k$\, there exists a rainbow undirected cycle of length  at most $k$. The directed version is obtained by taking as $F_i$ the set of edges going out of the vertex $v_i$ ($i \le n$)\, with the directions removed. I will tell about recent results on this conjecture\, obtained together with He Guo\, with Beger\, Chudnovsky and Zerbib\, and with DeVos and Holzman.
URL:https://dimag.ibs.re.kr/event/2022-01-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220111T163000
DTEND;TZID=Asia/Seoul:20220111T173000
DTSTAMP:20260418T000627
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:20260418T000627
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;VALUE=DATE:20211220
DTEND;VALUE=DATE:20211223
DTSTAMP:20260418T000627
CREATED:20211219T150000Z
LAST-MODIFIED:20240707T080557Z
UID:4146-1639958400-1640217599@dimag.ibs.re.kr
SUMMARY:2021 Combinatorics Workshop (2021 조합론 학술대회)
DESCRIPTION:The Combinatorics Workshop (조합론 학술대회) is an annual conference of combinatorialists in Korea that started in 2004 by the Yonsei University BK21 Research Group. Since 2013\, this workshop has been advised by the committee of discrete mathematics of the Korean Mathematical Society. This year it will take place at The Bloomvista in Yangpyeong on December 20-22\, 2021. \nThe aim of this workshop is to bring together active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas. \nWe plan to limit the number of participants. Registration (without a fee) will be required. General participants will be required to pay for their own accommodation. \n\nTitle: 2021 Combinatorics Workshop (2021 조합론 학술대회)\nDate: December 20 – 22 (Mon-Wed)\, 2021\nVenue: The Bloomvista\, Yangpyeong\nWebsite: https://cw2021.combinatorics.kr\n\nPlan\n\nStarting in the afternoon of Thursday and ending in the morning of Wednesday.\nThere will be 5 invited talks for 50 minutes each.\nThere will be contributed talks for 25 minutes each.\n\nUsing English is recommended if there are non-Korean participants in the audience.\nThe call for contributed talks will be announced later.\n\n\nIt will be an offline meeting.\n\nInvited Speakers\n\nDongsu Kim\, KAIST\nJoonkyung Lee\, Hanyang University\nHong Liu\, University of Warwick\, UK\nSuil O\, SUNY Korea\nSeonjeong Park\, Jeonju University\n\nCall for Abstracts\nWe are looking for contributed talks! If you are interested in giving a contributed talk\, then please submit your abstract until November 15\, 2021. \nRegistration\n\nPlease fill out the registration form by November 21\, 2021.\n\nThe registration is free.\nThe organizers will announce the price for the accommodation soon.\n\n\nDue to the government COVID-19 policy\, the organizers may reject some registration\, even if the registration was made before November 21.\n\nOrganizing Committee\n\nJeong-Ok Choi\, GIST\nSang-il Oum\, IBS Discrete Mathematics Group and KAIST\nHeesung Shin\, Inha University\n\nAdvisory Committee\nCommittee of Discrete Mathematics\, The Korean Mathematical Society (Chair: Soojin Cho\, Ajou University) \nHost and Sponsors\nIBS Discrete Mathematics Group
URL:https://dimag.ibs.re.kr/event/2021-combinatorics-workshop/
LOCATION:The Bloomvista
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211214T163000
DTEND;TZID=Asia/Seoul:20211214T173000
DTSTAMP:20260418T000627
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:20211209T163000
DTEND;TZID=Asia/Seoul:20211209T173000
DTSTAMP:20260418T000627
CREATED:20211209T073000Z
LAST-MODIFIED:20240705T180040Z
UID:4671-1639067400-1639071000@dimag.ibs.re.kr
SUMMARY:David Munhá Correia\, Rainbow matchings
DESCRIPTION:I will discuss various results for rainbow matching problems. In particular\, I will introduce a ‘sampling trick’ which can be used to obtain short proofs of old results as well as to solve asymptotically some well known conjectures. This is joint work with Alexey Pokrovskiy and Benny Sudakov.
URL:https://dimag.ibs.re.kr/event/2021-12-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR