BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN CALSCALE:GREGORIAN METHOD:PUBLISH X-ORIGINAL-URL:https://dimag.ibs.re.kr X-WR-CALDESC:Events for Discrete Mathematics Group REFRESH-INTERVAL;VALUE=DURATION:PT1H X-Robots-Tag:noindex X-PUBLISHED-TTL:PT1H BEGIN:VTIMEZONE TZID:Asia/Seoul BEGIN:STANDARD TZOFFSETFROM:+0900 TZOFFSETTO:+0900 TZNAME:KST DTSTART:20200101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220825T100000 DTEND;TZID=Asia/Seoul:20220825T110000 DTSTAMP:20260417T232556 CREATED:20220825T010000Z LAST-MODIFIED:20240707T075527Z UID:6007-1661421600-1661425200@dimag.ibs.re.kr SUMMARY:Brett Leroux\, Expansion of random 0/1 polytopes DESCRIPTION:A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $\mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a random $0/1$ polytope in $\mathbb{R}^d$ is at least $\frac{1}{12d}$ with high probability. \nAfter discussing this result and the proof\, we will mention some possible extensions. To conclude\, we will discuss some related questions about the combinatorics of random polytopes\, including the diameter problem. \nThis is joint work with Luis Rademacher. URL:https://dimag.ibs.re.kr/event/2022-08-25/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220810T163000 DTEND;TZID=Asia/Seoul:20220810T173000 DTSTAMP:20260417T232556 CREATED:20220713T073000Z LAST-MODIFIED:20240705T171145Z UID:5849-1660149000-1660152600@dimag.ibs.re.kr SUMMARY:Akash Kumar\, Random walks and Forbidden Minors DESCRIPTION:Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk\, I will present how random walks helped make progress on algorithmic problems on planar graphs.\nIn particular\, I show how random walk based (i.e.\, spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stolman\, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman\, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called “efficient partition oracle” problem [K.-Seshadhri-Stolman\, FOCS 2021].\nThe talk will assume minimal background by presenting a stand-alone story that should be of interest to students/researchers in computer science. URL:https://dimag.ibs.re.kr/event/2022-08-10/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220803T163000 DTEND;TZID=Asia/Seoul:20220803T173000 DTSTAMP:20260417T232556 CREATED:20220720T073000Z LAST-MODIFIED:20240707T075557Z UID:5637-1659544200-1659547800@dimag.ibs.re.kr SUMMARY:Lars Jaffke\, Taming graphs with no large creatures and skinny ladders DESCRIPTION:We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor\, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin\, Todinca\, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set\, Feedback Vertex Set and many other problems\, when restricted to an input graph from $\mathcal{G}$. Furthermore\, as shown by Gartland and Lokshtanov\, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). \nJoint work with Jakub Gajarský\, Paloma T. Lima\, Jana Novotná\, Marcin Pilipczuk\, Paweł Rzążewski\, and Uéverton S. Souza. URL:https://dimag.ibs.re.kr/event/2022-08-03/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220727T163000 DTEND;TZID=Asia/Seoul:20220727T173000 DTSTAMP:20260417T232556 CREATED:20220727T073000Z LAST-MODIFIED:20240705T171144Z UID:5830-1658939400-1658943000@dimag.ibs.re.kr SUMMARY:Noam Lifshitz\, Product free sets in the alternating group DESCRIPTION:A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of $A_n$ be? \nIn the talk we will completely solve the problem by determining the largest product free subset of $A_n$. \nOur proof combines a representation theoretic argument due to Gowers\, with an analytic tool called hypercontractivity for global functions. We also make use of a dichotomy between structure and a pseudorandomness notion of functions over the symmetric group known as globalness. \nBased on a joint work with Peter Keevash and Dor Minzer. URL:https://dimag.ibs.re.kr/event/2022-07-27/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220707T100000 DTEND;TZID=Asia/Seoul:20220707T110000 DTSTAMP:20260417T232556 CREATED:20220707T010000Z LAST-MODIFIED:20240707T075642Z UID:5783-1657188000-1657191600@dimag.ibs.re.kr SUMMARY:Sepehr Hajebi\, Holes\, hubs and bounded treewidth DESCRIPTION:A hole in a graph $G$ is an induced cycle of length at least four\, and for every hole $H$ in $G$\, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions\,” that is\, a fixed complete graph\, a fixed complete bipartite graph (with parts of equal size)\, all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance\, where a wheel means a hole with a $3$-hub. In accordance\, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result\, and will also give an overview of related works.\nBased on joint work with Tara Abrishami\, Bogdan Alecu\, Maria Chudnovsky\, Sophie Spirkl and Kristina Vušković. URL:https://dimag.ibs.re.kr/event/2022-07-07/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220629T163000 DTEND;TZID=Asia/Seoul:20220629T173000 DTSTAMP:20260417T232556 CREATED:20220611T121204Z LAST-MODIFIED:20240705T171148Z UID:5827-1656520200-1656523800@dimag.ibs.re.kr SUMMARY:Xizhi Liu\, Hypergraph Turán problem: from 1 to ∞ DESCRIPTION:One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk\, we will look at some recent progress and approaches to constructing hypergraph families with at least two different extremal constructions.\nBased on some joint work with Dhruv Mubayi\, Christian Reiher\, Jianfeng Hou\, Heng Li\, and Yixiao Zhang. URL:https://dimag.ibs.re.kr/event/2022-06-29/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220622T163000 DTEND;TZID=Asia/Seoul:20220622T173000 DTSTAMP:20260417T232556 CREATED:20220622T073000Z LAST-MODIFIED:20240707T075717Z UID:5846-1655915400-1655919000@dimag.ibs.re.kr SUMMARY:Chengfei Xie\, On the packing densities of superballs in high dimensions DESCRIPTION:The sphere packing problem asks for the densest packing of nonoverlapping equal-sized balls in the space. This is an old and difficult problem in discrete geometry. In this talk\, we give a new proof for the result that for $ 11\, 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:20260417T232556 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:20220210T163000 DTEND;TZID=Asia/Seoul:20220210T173000 DTSTAMP:20260417T232556 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:20220127T163000 DTEND;TZID=Asia/Seoul:20220127T173000 DTSTAMP:20260417T232556 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:20220120T163000 DTEND;TZID=Asia/Seoul:20220120T173000 DTSTAMP:20260417T232556 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:20220113T163000 DTEND;TZID=Asia/Seoul:20220113T173000 DTSTAMP:20260417T232556 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:20211209T163000 DTEND;TZID=Asia/Seoul:20211209T173000 DTSTAMP:20260417T232556 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20211125T163000 DTEND;TZID=Asia/Seoul:20211125T173000 DTSTAMP:20260417T232556 CREATED:20211125T073000Z LAST-MODIFIED:20240705T181009Z 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:20260417T232556 CREATED:20211111T073000Z LAST-MODIFIED:20240705T181024Z 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20211105T163000 DTEND;TZID=Asia/Seoul:20211105T173000 DTSTAMP:20260417T232556 CREATED:20211105T073000Z LAST-MODIFIED:20240707T080839Z UID:4555-1636129800-1636133400@dimag.ibs.re.kr SUMMARY:Martin Milanič\, Tree Decompositions with Bounded Independence Number DESCRIPTION:The independence number of a tree decomposition $\mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $\mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number\, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation\, we consider six graph containment relations—the subgraph\, topological minor\, and minor relations\, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. Furthermore\, using a variety of tools including SPQR trees and potential maximal cliques\, we show how to obtain such tree decompositions efficiently. \nAs an immediate consequence\, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact\, our approach shows that the Maximum Weight Independent $\mathcal{H}$-Packing problem\, a common generalization of the MWIS and the Maximum Weight Induced Matching problems\, can be solved in polynomial time in these graph classes. \nThis is joint work with Clément Dallard and Kenny Štorgel. URL:https://dimag.ibs.re.kr/event/2021-11-05/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20211008T100000 DTEND;TZID=Asia/Seoul:20211008T110000 DTSTAMP:20260417T232556 CREATED:20211008T010000Z LAST-MODIFIED:20240707T080932Z UID:4450-1633687200-1633690800@dimag.ibs.re.kr SUMMARY:Paul Seymour\, Polynomial bounds for chromatic number DESCRIPTION:The Gyárfás-Sumner conjecture says that for every forest $H$\, there is a function $f$ such that the chromatic number $\chi(G)$ is at most $f(\omega(G))$ for every $H$-free graph $G$ (“$H$-free” means with no induced subgraph isomorphic to $H$\, and $\omega(G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a few types of forest. \nNevertheless\, there is a much stronger conjecture\, due to Esperet: that for every forest $H$\, there is a polynomial function $f$ as above. As one might expect\, this has been proved for even fewer types of forest; and the smallest tree $H$ for which Esperet’s conjecture is not known is the five-vertex path $P_5$. \nA third notorious conjecture is the Erdős-Hajnal conjecture\, that for every graph $H$\, there exists $c>0$ such that $\alpha(G)\omega(G)\ge |G|^c$ for every $H$-free graph $G$ (where $\alpha(G)$ is the size of the largest stable set of $G$). The smallest graph $H$ for which this is not known is also $P_5$\, which\, conveniently\, is a forest; and every forest that satisfies Esperet’s conjecture also satisfies the Erdős-Hajnal conjecture. So there is substantial interest in the chromatic numbers of $P_5$-free graphs. The best upper bound that was previously known\, due to Esperet\, Lemoine\, Maffray\, and Morel\, was that $\chi(G)\le (5/27)3^\omega(G)$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. In recent work with Alex Scott and Sophie Spirkl\, we have proved several results related to Esperet’s conjecture\, including proofs of its truth for some new types of forest $H$\, and a “near-polynomial” bound when $H = P_5$\, that $\chi(G) \le \omega(G)^{\log_2(\omega(G))}$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. We survey these results and give a proof of the new bound for $P_5$. URL:https://dimag.ibs.re.kr/event/2021-10-08/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210930T163000 DTEND;TZID=Asia/Seoul:20210930T173000 DTSTAMP:20260417T232556 CREATED:20210930T073000Z LAST-MODIFIED:20240707T080948Z UID:4460-1633019400-1633023000@dimag.ibs.re.kr SUMMARY:Péter Pál Pach\, The Alon-Jaeger-Tarsi conjecture via group ring identities DESCRIPTION:The Alon-Jaeger-Tarsi conjecture states that for any finite field $\mathbb{F}$ of size at least 4 and any nonsingular matrix $M$ over $\mathbb{F}$ there exists a vector $x$ such that neither $x$ nor $Mx$ has a 0 component. In joint work with János Nagy we proved this conjecture when the size of the field is sufficiently large\, namely\, when $61 URL:https://dimag.ibs.re.kr/event/2021-09-30/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210818T170000 DTEND;TZID=Asia/Seoul:20210818T180000 DTSTAMP:20260417T232556 CREATED:20210818T080000Z LAST-MODIFIED:20240705T182104Z UID:4353-1629306000-1629309600@dimag.ibs.re.kr SUMMARY:Petr Hliněný\, Twin-width is linear in the poset width DESCRIPTION:Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices\, and it extends also to other binary relational structures\, e.g. to digraphs and posets. It was introduced quite recently\, in 2020 by Bonnet\, Kim\, Thomassé\, and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result\, they also claimed that posets of bounded width have bounded twin-width\, thus capturing a prior result on FO model checking of posets of bounded width in FPT. However\, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. \nWe prove that posets of width d have twin-width at most 9d with a direct and elementary argument\, and show that this bound is tight up to a constant factor. Specifically\, for posets of width 2\, we prove that in the worst case their twin-width is also equal to 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset. \n(Joint work with my student Jakub Balaban who obtained the main ideas in his bachelor thesis.) URL:https://dimag.ibs.re.kr/event/2021-08-18/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210728T150000 DTEND;TZID=Asia/Seoul:20210728T160000 DTSTAMP:20260417T232556 CREATED:20210607T135955Z LAST-MODIFIED:20240705T184022Z UID:4228-1627484400-1627488000@dimag.ibs.re.kr SUMMARY:Maria Chudnovsky\, Induced subgraphs and tree decompositions DESCRIPTION:Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. \nTree decompositions are closely related to the existence of “laminar collections of separations” in a graph\, which roughly means that the separations in the collection “cooperate” with each other\, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors. \nIn the case of families where induced subgraphs are excluded\, while there are often natural separations\, they are usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree\, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results\, which we will survey in this talk. URL:https://dimag.ibs.re.kr/event/2021-07-28/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210714T170000 DTEND;TZID=Asia/Seoul:20210714T180000 DTSTAMP:20260417T232556 CREATED:20210615T091821Z LAST-MODIFIED:20240705T184018Z UID:4257-1626282000-1626285600@dimag.ibs.re.kr SUMMARY:Stefan Weltge\, Integer programs with bounded subdeterminants and two nonzeros per row DESCRIPTION:We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles\, where k is any constant. Previously\, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. \nWe observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time\, using a reduction to b-matching. \nThis is joint work with Samuel Fiorini\, Gwenaël Joret\, and Yelena Yuditsky. URL:https://dimag.ibs.re.kr/event/2021-07-14/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210630T170000 DTEND;TZID=Asia/Seoul:20210630T180000 DTSTAMP:20260417T232556 CREATED:20210617T062135Z LAST-MODIFIED:20240707T081259Z UID:4277-1625072400-1625076000@dimag.ibs.re.kr SUMMARY:Florian Gut and Attila Joó\, Large vertex-flames in uncountable digraphs DESCRIPTION:The local connectivity  $ \kappa_D(r\,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $r\rightarrow v $ paths in $ D $. A spanning subdigraph $ L $ of $ D $ with $  \kappa_L(r\,v)=\kappa_D(r\,v) $ for every $ v\in V-r $ must have at least $ \sum_{v\in V-r}\kappa_D(r\,v) $ edges. It was shown by Lovász that\, maybe surprisingly\, this lower bound is sharp for every finite digraph. The optimality of an $ L $ can be captured by the following characterization: For every $ v\in V-r $ there is a system $ \mathcal{P}_v $ of internally disjoint $ r\rightarrow v $ paths in $ L $ covering all the ingoing edges of $ v $ in $ L $ such that one can choose from  each $ P\in \mathcal{P}_v $ either an edge or an internal vertex in such a way that the resulting set meets every $ r\rightarrow v $ path of $ D $. We prove that every digraph of size at most $ \aleph_1 $  admits such a spanning subdigraph $ L $. The question if this remains true for larger digraphs remains open. URL:https://dimag.ibs.re.kr/event/2021-06-30/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20210616T170000 DTEND;TZID=Asia/Seoul:20210616T180000 DTSTAMP:20260417T232556 CREATED:20210428T010009Z LAST-MODIFIED:20240705T184215Z UID:4020-1623862800-1623866400@dimag.ibs.re.kr SUMMARY:Alan Lew\, Representability and boxicity of simplicial complexes DESCRIPTION:An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology\, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs. \nA natural higher-dimensional generalization of interval graphs is the class d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in $mathbb R^d$. We define the d-boxicity of a simplicial complex X to be the minimal k such that X can be written as the intersection of k d-representable complexes. \nA classical result of Roberts\, later rediscovered by Witsenhausen\, asserts that the boxicity of a graph with n vertices is at most n/2. Our main result is the following high dimensional extension of Roberts’ theorem: Let X be a simplicial complex on n vertices with minimal non-faces of dimension at most d. Then\, the d-boxicity of X is at most $frac{1}{d+1}binom{n}{d}$. \nExamples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas. URL:https://dimag.ibs.re.kr/event/2021-06-16/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT END:VCALENDAR