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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210407T170000
DTEND;TZID=Asia/Seoul:20210407T180000
DTSTAMP:20260418T050919
CREATED:20210301T235812Z
LAST-MODIFIED:20240705T190042Z
UID:3701-1617814800-1617818400@dimag.ibs.re.kr
SUMMARY:Michał Pilipczuk\, Structural properties of powers of sparse graphs
DESCRIPTION:For a graph G and an integer d\, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent if and only if they are at distance at most d in G. Assuming that G is sparse\, what can we say about the structure in $G^d$? Certainly $G^d$ can be dense\, as the square of a star is a complete graph\, but $G^d$ still retains many properties that can be derived from the sparsity of G. We will present some recent results in this spirit\, in particular connected to colorings and to the Erdős-Hajnal property\, assuming that G is drawn from a fixed class of bounded expansion or from a fixed nowhere dense class. The talk will be based on the recent papers: “Clustering Powers of Sparse Graphs” (with J. Nešetřil\, P. Ossona de Mendez\, and X. Zhu) and “Erdős-Hajnal properties for powers of sparse graphs” (with M. Briański\, P. Micek\, and M. Seweryn).
URL:https://dimag.ibs.re.kr/event/2021-04-07/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210406T163000
DTEND;TZID=Asia/Seoul:20210406T173000
DTSTAMP:20260418T050919
CREATED:20210308T061306Z
LAST-MODIFIED:20240705T190041Z
UID:3731-1617726600-1617730200@dimag.ibs.re.kr
SUMMARY:Rutger Campbell\, Matroid orientability and representability
DESCRIPTION:In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
URL:https://dimag.ibs.re.kr/event/2021-04-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210401T100000
DTEND;TZID=Asia/Seoul:20210401T110000
DTSTAMP:20260418T050919
CREATED:20210218T001134Z
LAST-MODIFIED:20240705T191014Z
UID:3642-1617271200-1617274800@dimag.ibs.re.kr
SUMMARY:Sophie Spirkl\, Pure pairs in ordered graphs
DESCRIPTION:A pure pair in a graph G is a pair of subsets A\, B of the vertex set of G such that in G\, either all of the edges or none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture. \nIn this talk\, I will discuss the topic of pure pairs in ordered graphs\, that is\, graphs with a linear ordering on their vertex set. If we exclude a graph H as an ordered induced subgraph\, how large a pure pair can we guarantee? I will talk about how the answer differs from the case of unordered graphs and show some of the techniques used. \nBased on joint work with Maria Chudnovsky\, Jacob Fox\, Alex Scott\, and Paul Seymour.
URL:https://dimag.ibs.re.kr/event/2021-04-01/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210330T163000
DTEND;TZID=Asia/Seoul:20210330T173000
DTSTAMP:20260418T050919
CREATED:20210225T090612Z
LAST-MODIFIED:20240707T081638Z
UID:3676-1617121800-1617125400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, 3-uniform hypergraphs avoiding a cycle of length four
DESCRIPTION:We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze\, Győri\, Methuku\, Salia.
URL:https://dimag.ibs.re.kr/event/2021-03-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210324T170000
DTEND;TZID=Asia/Seoul:20210324T180000
DTSTAMP:20260418T050919
CREATED:20210219T024236Z
LAST-MODIFIED:20240705T191012Z
UID:3649-1616605200-1616608800@dimag.ibs.re.kr
SUMMARY:Édouard Bonnet\, Twin-width and ordered binary structures
DESCRIPTION:The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G)\, and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y.  Twin-width is closely tied to total orders on the vertices\, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures\, or if you prefer\, matrices on a finite alphabet. This turns out to be key in understanding combinatorial\, algorithmic\, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. \n\nEnumerative combinatorics: All the classes of 0\,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh\, Bollobás\, and Morris on the growth of hereditary classes of ordered graphs).\nAlgorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.\nFinite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.\n\nIn addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum\, which is still missing for unordered graphs. \nJoint work with Ugo Giocanti\, Patrice Ossona de Mendez\, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2021-03-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210322T163000
DTEND;TZID=Asia/Seoul:20210322T173000
DTSTAMP:20260418T050919
CREATED:20210307T042041Z
LAST-MODIFIED:20240705T190041Z
UID:3721-1616430600-1616434200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Nested cycles with no geometric crossing
DESCRIPTION:In 1975\, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$\, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. \nThis is joint work with Irene Gil Fernández\, Jaehoon Kim and Younjin Kim.
URL:https://dimag.ibs.re.kr/event/2021-03-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210317T170000
DTEND;TZID=Asia/Seoul:20210317T180000
DTSTAMP:20260418T050919
CREATED:20210228T115822Z
LAST-MODIFIED:20240705T190042Z
UID:3692-1616000400-1616004000@dimag.ibs.re.kr
SUMMARY:Yixin Cao (操宜新)\, Recognizing (unit) interval graphs by zigzag graph searches
DESCRIPTION:Corneil\, Olariu\, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu’s algorithm\, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs\, based on three sweeps of graph searches. Moreover\, we show that two sweeps are already sufficient. Toward the proofs of the main results\, we make several new structural observations that might be of independent interests.
URL:https://dimag.ibs.re.kr/event/2021-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210316T163000
DTEND;TZID=Asia/Seoul:20210316T173000
DTSTAMP:20260418T050919
CREATED:20210304T000046Z
LAST-MODIFIED:20240705T190041Z
UID:3717-1615912200-1615915800@dimag.ibs.re.kr
SUMMARY:Se-Young Yun (윤세영)\, Regret in Online Recommendation Systems
DESCRIPTION:We propose a theoretical analysis of recommendation systems in an online setting\, where items are sequentially recommended to users over time. In each round\, a user\, randomly picked from a population of m users\, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly\, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown. The performance of the recommendation algorithm is captured through its regret\, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each structure regret lower bounds\, and devise algorithms achieving these limits. Interestingly\, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user\, that due to learning the chances users like items\, and finally that arising when learning the underlying structure. \nThis is joint work with Kaito Ariu\, Narae Ryu\, and Alexandre Proutière.
URL:https://dimag.ibs.re.kr/event/2021-03-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210309T163000
DTEND;TZID=Asia/Seoul:20210309T173000
DTSTAMP:20260418T050919
CREATED:20210225T090525Z
LAST-MODIFIED:20240707T081706Z
UID:3674-1615307400-1615311000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Some classical problems in graph saturation
DESCRIPTION:Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$\, but the addition of any edge creates a copy of $F$. The function $\operatorname{sat}(n\,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph. \nIn the first half of the talk\, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964)\, which determined the value of $\operatorname{sat}(n\,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices\, confirming a conjecture of Kritschgau\, Methuku\, Tait\, and Timmons. We further establish a corresponding stability result. \nIn the second half\, we will focus on a central conjecture in graph saturation made by Tuza (1986)\, which states that for every graph $F$\, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n\,F)}{n}$ exists. We make progress in the negative direction of this conjecture. \nThis talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2021-03-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210302T163000
DTEND;TZID=Asia/Seoul:20210302T173000
DTSTAMP:20260418T050919
CREATED:20210217T044249Z
LAST-MODIFIED:20240707T081721Z
UID:3639-1614702600-1614706200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified half-integral 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. Such a duality does not hold if we restrict to odd cycles.  However\, in 1999\, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. \nA multitude of natural properties of cycles can be encoded in this setting\, for example cycles of length at least $\ell$\, cycles of length $p$ modulo $q$\, cycles intersecting a prescribed set of vertices at least $t$ times\, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. \nThis is joint work with J. Pascal Gollin\, Ken-ichi Kawarabayashi\, O-joung Kwon\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-03-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210223T163000
DTEND;TZID=Asia/Seoul:20210223T173000
DTSTAMP:20260418T050919
CREATED:20210217T043908Z
LAST-MODIFIED:20240707T081835Z
UID:3637-1614097800-1614101400@dimag.ibs.re.kr
SUMMARY:Minki Kim (김민기)\, Rainbow paths and rainbow matchings
DESCRIPTION:We prove that if $n \geq 3$\, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves on a previous result\, in which $3n-3$ is replaced by $3n-2$. We also prove a “cooperative” generalization: for $t > 0$ and $n \geq 3$\, any $3n-4+t$ sets of edges\, the union of every $t$ of which contains a matching of size $n$\, have rainbow matching of size $n$. This is joint work with Ron Aharoni\, Joseph Briggs\, and Jinha Kim.
URL:https://dimag.ibs.re.kr/event/2021-02-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210217T100000
DTEND;TZID=Asia/Seoul:20210217T110000
DTSTAMP:20260418T050919
CREATED:20201231T022333Z
LAST-MODIFIED:20240707T081843Z
UID:3423-1613556000-1613559600@dimag.ibs.re.kr
SUMMARY:David Wood\, Tree densities of sparse graph classes
DESCRIPTION:This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular\, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$\, for some integer $d$ that depends on $\mathcal{G}$. For example\, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s\,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).
URL:https://dimag.ibs.re.kr/event/2021-02-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210216T163000
DTEND;TZID=Asia/Seoul:20210216T173000
DTSTAMP:20260418T050919
CREATED:20210205T012237Z
LAST-MODIFIED:20240705T191023Z
UID:3594-1613493000-1613496600@dimag.ibs.re.kr
SUMMARY:Martin Ziegler\, Quantitative Coding and Complexity Theory of Continuous Data
DESCRIPTION:Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices\, characters as integers\, integers as bit strings\, and vice versa. For such discrete data\, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time\, say). \nBut concerning continuous data\, already real numbers naturally suggest various encodings with very different computational properties. \nWe recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces. \nJoint work with Donghyun Lim.
URL:https://dimag.ibs.re.kr/event/2021-02-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210210T163000
DTEND;TZID=Asia/Seoul:20210210T173000
DTSTAMP:20260418T050919
CREATED:20201231T073729Z
LAST-MODIFIED:20240705T191150Z
UID:3428-1612974600-1612978200@dimag.ibs.re.kr
SUMMARY:Jie Ma (马杰)\, Non-repeated cycle lengths and Sidon sequences
DESCRIPTION:We prove a conjecture of Boros\, Caro\, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths\, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros\, Caro\, Furedi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory. Joint work with Tianchi Yang.
URL:https://dimag.ibs.re.kr/event/2021-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210209T163000
DTEND;TZID=Asia/Seoul:20210209T173000
DTSTAMP:20260418T050919
CREATED:20210203T050722Z
LAST-MODIFIED:20240705T191023Z
UID:3581-1612888200-1612891800@dimag.ibs.re.kr
SUMMARY:Doowon Koh (고두원)\, On the cone restriction conjecture in four dimensions and applications in incidence geometry
DESCRIPTION:Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First\, we review the finite field restriction problem for cones and address new results on the conical restriction problems. In particular\, we establish the restriction conjecture for the cone in four dimensions. Second\, we study how to apply the conical restriction results to the point-sphere incidence bounds. As a consequence\, we obtain sharp point-sphere incidence bounds when sphere sets are not too big.
URL:https://dimag.ibs.re.kr/event/2021-02-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210203T163000
DTEND;TZID=Asia/Seoul:20210203T173000
DTSTAMP:20260418T050919
CREATED:20201106T054235Z
LAST-MODIFIED:20240705T193028Z
UID:3241-1612369800-1612373400@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, Colorful KKM and multiple cakes division
DESCRIPTION:In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0\,1] interval (“cake”) into n sub-intervals. Woodall\, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players\, in which every player gets a piece belonging to her list of preferred parts. In fact\, Gale proved a colorful version of the famous KKM theorem\, not realizing that this is the same problem\, but on the other hand\, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy\, when there is a general number of cakes\, and general number of players. \nJoint work with Eli Berger\, Joseph Briggs\, Erel Segal-Halevi and Shira Zerbib.
URL:https://dimag.ibs.re.kr/event/2021-02-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210127T100000
DTEND;TZID=Asia/Seoul:20210127T110000
DTSTAMP:20260418T050919
CREATED:20210114T124234Z
LAST-MODIFIED:20240705T191135Z
UID:3500-1611741600-1611745200@dimag.ibs.re.kr
SUMMARY:Dong Yeap Kang (강동엽)\, A proof of the Erdős-Faber-Lovász conjecture
DESCRIPTION:A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős\, Faber\, and Lovász in 1972\, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. \nIn this talk\, I will present the ideas to prove the conjecture for all large $n$. This is joint work with Tom Kelly\, Daniela Kühn\, Abhishek Methuku\, and Deryk Osthus.
URL:https://dimag.ibs.re.kr/event/2021-01-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210126T043000
DTEND;TZID=Asia/Seoul:20210126T173000
DTSTAMP:20260418T050919
CREATED:20210125T042312Z
LAST-MODIFIED:20240707T081932Z
UID:3545-1611635400-1611682200@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Minimum saturated families of sets
DESCRIPTION:A family $\mathcal F$ of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. More than 40 years ago\, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least $(1 – 2^{-(s-1)})2^n$. It is a simple exercise to show that every s-saturated family has size at least $2^{n-1}$\, but\, as was mentioned by Frankl and Tokushige\, even obtaining a slightly better bound of $(1/2 + \varepsilon)2^n$\, for some fixed $\varepsilon > 0$\, seems difficult. We prove such a result\, showing that every s-saturated family of subsets of [n] has size at least $(1 – 1/s)2^n$. In this talk\,  I will present two short proofs. This is joint work with M. Bucic\, S. Letzter and B. Sudakov.
URL:https://dimag.ibs.re.kr/event/2021-01-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210120T163000
DTEND;TZID=Asia/Seoul:20210120T173000
DTSTAMP:20260418T050919
CREATED:20201211T084524Z
LAST-MODIFIED:20240707T081951Z
UID:3358-1611160200-1611163800@dimag.ibs.re.kr
SUMMARY:Yusuke Kobayashi (小林 佑輔)\, An FPT Algorithm for Minimum Additive Spanner Problem
DESCRIPTION:For a positive integer t and a graph G\, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph\, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners\, Minimum Additive t-Spanner Problem is hard to handle\, and hence only few results are known for it. In this talk\, we study Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter\, and give a fixed-parameter algorithm for it. We also extend our result to (α\,β)-spanners.
URL:https://dimag.ibs.re.kr/event/2021-01-20/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210119T163000
DTEND;TZID=Asia/Seoul:20210119T173000
DTSTAMP:20260418T050919
CREATED:20210114T070412Z
LAST-MODIFIED:20240705T191136Z
UID:3498-1611073800-1611077400@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Perfect matchings and derangements on graphs
DESCRIPTION:We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph\, and in terms of derangements and permutations on graphs. We give several related results and open questions. This is joint work with Matija Bucic\, Pat Devlin\, Mo Hendon\, and Dru Horne.
URL:https://dimag.ibs.re.kr/event/2021-01-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210113T100000
DTEND;TZID=Asia/Seoul:20210113T110000
DTSTAMP:20260418T050919
CREATED:20201126T045239Z
LAST-MODIFIED:20240705T192124Z
UID:3318-1610532000-1610535600@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, Vertex-minors and flooding immersions
DESCRIPTION:An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover\, understanding such flooding immersions is a vital step towards understanding the structure of graphs with a forbidden vertex-minor. \nI will focus on explaining the connection to vertex-minors\, and on recent progress in this direction from ongoing joint work with Jim Geelen and Paul Wollan.
URL:https://dimag.ibs.re.kr/event/2021-01-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210112T163000
DTEND;TZID=Asia/Seoul:20210112T173000
DTSTAMP:20260418T050919
CREATED:20201231T074146Z
LAST-MODIFIED:20240705T191150Z
UID:3431-1610469000-1610472600@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Discrete geometry in convexity spaces
DESCRIPTION:The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years\, we have seen some progress on several open problems in the area\, and in this talk\, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p\,q) theorem.
URL:https://dimag.ibs.re.kr/event/2021-01-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20260418T050919
CREATED:20201126T024545Z
LAST-MODIFIED:20240707T082022Z
UID:3313-1609864200-1609867800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Directed tangles and applications
DESCRIPTION:The canonical tree-decomposition theorem\, proved by Robertson and Seymour in their seminal graph minors series\, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper\, we prove the analogous result for digraphs\, the directed tangle tree-decomposition theorem. More precisely\, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore\, for any integer $k$\, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$\, for any integer $k$. \nBy relaxing the bound slightly\, we can make the previous result algorithmic: for fixed $k$\, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$. \nWe provide two direct applications of this tangle tree-decomposition theorem. First\, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property\, that is\, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$\, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles\, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles\, shown by Reed [Mangoes and blueberries. Combinatorica 1999]. \nSecond\, for every fixed $k$ we show that there is a polynomial-time algorithm which\, on input $G$\, and source and sink vertices $(s_1\, t_1)\, \dots\, (s_k\, t_k)$\, either finds a family of paths $P_1\, \dots\, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths\, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”)\, and given known hardness results\, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths. \nThis is joint work with Archontia C. Giannopoulou\, Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Qiqin Xie.
URL:https://dimag.ibs.re.kr/event/2021-01-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201230T100000
DTEND;TZID=Asia/Seoul:20201230T110000
DTSTAMP:20260418T050919
CREATED:20201220T231608Z
LAST-MODIFIED:20240707T082035Z
UID:3389-1609322400-1609326000@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, The Erdős-Hajnal conjecture is true for excluding a five-cycle
DESCRIPTION:In an n-vertex graph\, there must be a clique or stable set of size at least $C\log n$\, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph\, the largest clique or stable set is bigger. \nErdős and Hajnal conjectured in 1977 that for every graph H\, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph\, and |G| means the number of vertices of G). This is still open\, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five. \nIt is true in that case. We will give a sketch of the proof\, which is via applying a lemma about bipartite graphs\, a variant of a theorem of I. Tomon. \nThis lemma has several other applications to the Erdős-Hajnal conjecture. For instance\, it implies that for every cycle C and forest T\, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.) \nJoint work with Maria Chudnovsky\, Alex Scott and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2020-12-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201222T163000
DTEND;TZID=Asia/Seoul:20201222T173000
DTSTAMP:20260418T050919
CREATED:20201208T060000Z
LAST-MODIFIED:20240705T192115Z
UID:3349-1608654600-1608658200@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, On a conjecture by Kalai and Meshulam - the Betti number of the independence complex of ternary graphs
DESCRIPTION:Given a graph G=(V\,E)\, the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers of I(G) is either 0 or 1. In this talk\, I will introduce a result by Zhang and Wu\, which proves the Kalai-Meshulam conjecture.
URL:https://dimag.ibs.re.kr/event/2020-12-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201217T100000
DTEND;TZID=Asia/Seoul:20201217T110000
DTSTAMP:20260418T050919
CREATED:20201028T010135Z
LAST-MODIFIED:20240707T082135Z
UID:3210-1608199200-1608202800@dimag.ibs.re.kr
SUMMARY:Jaiung Jun (전재웅)\, On the Hopf algebra of multi-complexes
DESCRIPTION:In combinatorics\, Hopf algebras appear naturally when studying various classes of combinatorial objects\, such as graphs\, matroids\, posets or symmetric functions. Given such a class of combinatorial objects\, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest. \nIn this talk\, I introduce a general class of combinatorial objects\, which we call multi-complexes\, which simultaneously generalizes graphs\, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then\, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives\, which is of combinatorial relevance. If time permits\, I will illustrate some potential applications. \nThis is joint work with Miodrag Iovanov.
URL:https://dimag.ibs.re.kr/event/2020-12-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201209T163000
DTEND;TZID=Asia/Seoul:20201209T173000
DTSTAMP:20260418T050919
CREATED:20201013T135938Z
LAST-MODIFIED:20240705T193042Z
UID:3125-1607531400-1607535000@dimag.ibs.re.kr
SUMMARY:Karl Heuer\, Even Circuits in Oriented Matroids
DESCRIPTION:In this talk I will state a generalisation of the even directed cycle problem\, which asks whether a given digraph contains a directed cycle of even length\, to orientations of regular matroids. Motivated by this problem\, I will define non-even oriented matroids generalising non-even digraphs\, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions: \nFirst we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. \nSecond and with the main focus for this talk\, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors\, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids\, which generalises butterfly minors for digraphs to oriented matroids. \nThe part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory. \nThis talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht. \n[1] K. Heuer\, R. Steiner and S. Wiederrecht\, Even Circuits in Oriented Matroids\, arxiv:2010.08988
URL:https://dimag.ibs.re.kr/event/2020-12-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201208T163000
DTEND;TZID=Asia/Seoul:20201208T173000
DTSTAMP:20260418T050919
CREATED:20201120T042705Z
LAST-MODIFIED:20240705T193010Z
UID:3287-1607445000-1607448600@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, A solution to Erdős and Hajnal's odd cycle problem
DESCRIPTION:I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number\, and discuss recent work with Richard Montgomery on this topic. In particular\, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and the appearance of cycle lengths in very sparse sequences (such as powers of 2). The methods developed in this work allows also us to embed equally divided clique subdivisions\, which was conjectured by Thomassen.
URL:https://dimag.ibs.re.kr/event/2020-12-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201203T163000
DTEND;TZID=Asia/Seoul:20201203T173000
DTSTAMP:20260418T050919
CREATED:20201013T135812Z
LAST-MODIFIED:20240705T194003Z
UID:3122-1607013000-1607016600@dimag.ibs.re.kr
SUMMARY:Deniz Sarikaya\, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs
DESCRIPTION:The study of Hamiltonian graphs\, i.e. finite graphs having a cycle that contains all vertices of the graph\, is a central theme of finite graph theory. For infinite graphs such a definition cannot work\, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2\,3]\, which allows to generalize several results about being a Hamiltonian graph to locally finite graphs\, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$  in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1]. \nWe examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs\, claw- and bull-free graphs\, the last also about further graph classes being structurally richer\, where we focus on paws as relevant subgraphs\, but relax the condition of forbidding them as induced subgraphs. \nThe goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details. \nThis is based on joint work [4\,5] with Karl Heuer. \nBibliography\n[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics\, vol 173. Springer\, Berlin\, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8 \n[2] R. Diestel and D. Kühn\, On infinite cycles I\, Combinatorica 24 (2004)\, pp. 69-89. \n[3] R. Diestel and D. Kühn\, On infinite cycles II\, Combinatorica 24 (2004)\, pp. 91-116. \n[4] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls\, arXiv:2006.09160 \n[5] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws\, arXiv:2006.09166
URL:https://dimag.ibs.re.kr/event/2020-12-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201202T170000
DTEND;TZID=Asia/Seoul:20201202T180000
DTSTAMP:20260418T050919
CREATED:20201126T022405Z
LAST-MODIFIED:20240705T192124Z
UID:3309-1606928400-1606932000@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On common graphs
DESCRIPTION:A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta\, extending a famous conjecture by Erdős\, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and by Sidorenko\, respectively\, in the late 1980s. \nDespite its importance\, the full classification of common graphs is still a wide open problem and has not seen much progress since the early 1990s. In this lecture\, I will present some old and new techniques to prove whether a graph is common or not.
URL:https://dimag.ibs.re.kr/event/2020-12-02/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR