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:20220218T100000 DTEND;TZID=Asia/Seoul:20220218T110000 DTSTAMP:20221209T143119 CREATED:20220218T010000Z LAST-MODIFIED:20220214T001444Z 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:20220210T163000 DTEND;TZID=Asia/Seoul:20220210T173000 DTSTAMP:20221209T143119 CREATED:20220210T073000Z LAST-MODIFIED:20220203T141652Z 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:20220127T163000 DTEND;TZID=Asia/Seoul:20220127T173000 DTSTAMP:20221209T143119 CREATED:20211230T013247Z LAST-MODIFIED:20211230T013247Z 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:20220120T163000 DTEND;TZID=Asia/Seoul:20220120T173000 DTSTAMP:20221209T143119 CREATED:20220120T073000Z LAST-MODIFIED:20220112T135850Z 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:20220113T163000 DTEND;TZID=Asia/Seoul:20220113T173000 DTSTAMP:20221209T143119 CREATED:20220113T073000Z LAST-MODIFIED:20220107T022256Z 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:20211209T163000 DTEND;TZID=Asia/Seoul:20211209T173000 DTSTAMP:20221209T143119 CREATED:20211209T073000Z LAST-MODIFIED:20211206T130502Z 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20211125T163000 DTEND;TZID=Asia/Seoul:20211125T173000 DTSTAMP:20221209T143119 CREATED:20211125T073000Z LAST-MODIFIED:20211108T113354Z UID:4552-1637857800-1637861400@dimag.ibs.re.kr SUMMARY:Tuukka Korhonen\, Fast FPT-Approximation of Branchwidth DESCRIPTION:Branchwidth determines how graphs\, and more generally\, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. \n\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity\, which in turn\, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].\n\nThis is joint work with Fedor Fomin. URL:https://dimag.ibs.re.kr/event/2021-11-25/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20211111T163000 DTEND;TZID=Asia/Seoul:20211111T173000 DTSTAMP:20221209T143119 CREATED:20211111T073000Z LAST-MODIFIED:20211030T075554Z UID:4668-1636648200-1636651800@dimag.ibs.re.kr SUMMARY:Sebastian Wiederrecht\, Matching Minors in Bipartite Graphs DESCRIPTION:Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya’s Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk we consider the origin and motivation behind the study of matching minors\, the current state of the art\, and their relation to structural digraph theory. The main result is a generalisation of the structure theorem by Robertson et al. and McCuaig for $K_{3\,3}$-matching minor free bipartite graphs to bipartite graphs excluding $K_{t\,t}$ as a matching minor for general t. This generalisation can be seen as a matching theoretic version of the Flat Wall Theorem by Robertson and Seymour. URL:https://dimag.ibs.re.kr/event/2021-11-11/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT END:VCALENDAR