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:20230119T100000 DTEND;TZID=Asia/Seoul:20230119T110000 DTSTAMP:20260417T215620 CREATED:20230103T142421Z LAST-MODIFIED:20240705T170041Z UID:6619-1674122400-1674126000@dimag.ibs.re.kr SUMMARY:Pedro Montealegre\, A Meta-Theorem for Distributed Certification DESCRIPTION:Distributed certification\, whether it be proof-labeling schemes\, locally checkable proofs\, etc.\, deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle\, and the processes are in charge of verifying these certificates\, so that two properties are satisfied: completeness\, i.e.\, for every legal instance\, there is a certificate assignment leading all processes to accept\, and soundness\, i.e.\, for every illegal instance\, and for every certificate assignment\, at least one process rejects. The verification of the certificates must be fast\, and the certificates themselves must be small. \nA large quantity of results have been produced in this framework\, each aiming at designing a distributed certification mechanism for specific boolean predicates. In this talk\, I will present a “meta-theorem”\, applying to many boolean predicates at once. Specifically\, I will show that\, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs\, there exists a distributed certification mechanism using certificates on $O(log^2 n)$ bits in n-node graphs of bounded treewidth\, with a verification protocol involving a single round of communication between neighbors. URL:https://dimag.ibs.re.kr/event/2023-01-19/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221215T100000 DTEND;TZID=Asia/Seoul:20221215T110000 DTSTAMP:20260417T215620 CREATED:20221109T130647Z LAST-MODIFIED:20240707T074155Z UID:6454-1671098400-1671102000@dimag.ibs.re.kr SUMMARY:Maya Sankar\, Homotopy and the Homomorphism Threshold of Odd Cycles DESCRIPTION:Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs\, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently\, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically\, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht. \nOur proof relies on a graph-theoretic analogue of homotopy equivalence\, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex\, and opens many further interesting questions. URL:https://dimag.ibs.re.kr/event/2022-12-15/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221201T100000 DTEND;TZID=Asia/Seoul:20221201T110000 DTSTAMP:20260417T215620 CREATED:20221016T112526Z LAST-MODIFIED:20240707T074433Z UID:6354-1669888800-1669892400@dimag.ibs.re.kr SUMMARY:Cosmin Pohoata\, Convex polytopes from fewer points DESCRIPTION:Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position\, there exist $n$ points in convex position is one of the most classical problems in extremal combinatorics\, known as the Erdős-Szekeres problem. In 1935\, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds\, which was nearly settled by Suk in 2016\, who showed that $ES_2(n)≤2^{n+o(n)}$. We discuss a recent proof that $ES_d(n)=2^{o(n)}$ holds for all $d≥3$. Joint work with Dmitrii Zakharov. URL:https://dimag.ibs.re.kr/event/2022-12-01/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221117T100000 DTEND;TZID=Asia/Seoul:20221117T110000 DTSTAMP:20260417T215620 CREATED:20221109T131844Z LAST-MODIFIED:20240707T074503Z UID:6462-1668679200-1668682800@dimag.ibs.re.kr SUMMARY:Chong Shangguan (上官冲)\, On the sparse hypergraph problem of Brown\, Erdős and Sós DESCRIPTION:For fixed integers $r\ge 3\, e\ge 3$\, and $v\ge r+1$\, let $f_r(n\,v\,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973\, Brown\, Erdős and Sós initiated the study of the function $f_r(n\,v\,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n\,v\,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. We will survey the state-of-art results about the study of $f_r(n\,er-(e-1)k+1\,e)$ and $f_r(n\,er-(e-1)k\,e)$\, where $r>k\ge 2$ and $e\ge 3$. Although these two functions have been extensively studied\, many interesting questions remain open. URL:https://dimag.ibs.re.kr/event/2022-11-17/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221109T163000 DTEND;TZID=Asia/Seoul:20221109T173000 DTSTAMP:20260417T215620 CREATED:20221015T061909Z LAST-MODIFIED:20240705T171133Z UID:6342-1668011400-1668015000@dimag.ibs.re.kr SUMMARY:Hugo Jacob\, On the parameterized complexity of computing tree-partitions DESCRIPTION:Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender\, Cornelissen\, and van der Wegen\, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete\, which is likely to exclude FPT algorithms. However\, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore\, we adapt some simple structural results about the tree-partition-width of subdivisions\, and use them to compare tree-cut width and tree-partition-width. \nBased on joint work with Hans Bodlaender and Carla Groenland. URL:https://dimag.ibs.re.kr/event/2022-11-09/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221006T100000 DTEND;TZID=Asia/Seoul:20221006T110000 DTSTAMP:20260417T215620 CREATED:20221002T082503Z LAST-MODIFIED:20240705T171138Z UID:6236-1665050400-1665054000@dimag.ibs.re.kr SUMMARY:Konstantin Tikhomirov\, A remark on the Ramsey number of the hypercube DESCRIPTION:A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper\, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$\, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$\, due to Conlon\, Fox\, and Sudakov. URL:https://dimag.ibs.re.kr/event/2022-10-06/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220929T100000 DTEND;TZID=Asia/Seoul:20220929T110000 DTSTAMP:20260417T215620 CREATED:20220904T134540Z LAST-MODIFIED:20240707T074627Z UID:6134-1664445600-1664449200@dimag.ibs.re.kr SUMMARY:Santiago Guzmán-Pro\, Local expressions of graphs classes DESCRIPTION:A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes\, the set of minimal obstructions might be infinite\, or too complicated to describe. For instance\, for any $k\ge 3$\, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless\, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$ is $k$-colourable if and only if it admits an orientation with no directed walk on $k+1$ vertices. We say that a class of graphs $\mathcal{P}$ is expressible by forbidden orientations if there is a finite set $F$ of oriented graphs such that $\mathcal{P}$ is the class of graphs that admit an $F$-free orientation. We are interested in understanding which graph classes are expressible by forbidden orientations (and why). In this talk\, we present some limitations of this expression system. In particular\, we show that the class of even-hole free graphs is not expressible by forbidden orientations. \nThroughout the talk\, we also mention some other related expression systems. In particular\, each of these systems provides a certification method to the $\mathcal{P}$-decision problem; i.e.\, decide if an input graph belongs to the class $\mathcal{P}$. We conclude this talk by proposing a general framework to talk about these expression systems. This framework allows us to formalize the question\, what can be certified this way? \nBased on a joint work with César Hernández-Cruz. URL:https://dimag.ibs.re.kr/event/2022-09-29/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220921T163000 DTEND;TZID=Asia/Seoul:20220921T173000 DTSTAMP:20260417T215620 CREATED:20220818T013812Z LAST-MODIFIED:20240707T074721Z UID:6050-1663777800-1663781400@dimag.ibs.re.kr SUMMARY:Mehtaab Sawhney\, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture DESCRIPTION:An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e.\, if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs\, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay\, for which Erdős offered one of his notorious monetary prizes and the proof involves a wide range of different tools from Fourier analysis\, random matrix theory\, the theory of Boolean functions\, probabilistic combinatorics\, and low-rank approximation. \nJoint w. Matthew Kwan\, Ashwin Sah\, and Lisa Sauermann URL:https://dimag.ibs.re.kr/event/2022-09-21/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220907T163000 DTEND;TZID=Asia/Seoul:20220907T173000 DTSTAMP:20260417T215620 CREATED:20220614T112030Z LAST-MODIFIED:20240705T171148Z UID:5853-1662568200-1662571800@dimag.ibs.re.kr SUMMARY:Dömötör Pálvölgyi\, C-P3O: Orientation of convex sets and other good covers DESCRIPTION:We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular\, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems\, P3O (partial 3-order)\, are a natural generalization of posets\, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets\, p-P3O\, and P3O that emerge from convex sets\, C-P3O\, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O’s.\nBased on joint work with Agoston\, Damasdi\, and Keszegh:\nhttps://arxiv.org/abs/2206.01721\nhttps://arxiv.org/abs/2206.01723 URL:https://dimag.ibs.re.kr/event/2022-09-07/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220831T163000 DTEND;TZID=Asia/Seoul:20220831T173000 DTSTAMP:20260417T215620 CREATED:20220816T233139Z LAST-MODIFIED:20240707T075512Z UID:6033-1661963400-1661967000@dimag.ibs.re.kr SUMMARY:Raphael Steiner\, Congruence-constrained subdivisions in digraphs DESCRIPTION:I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e\,q_e)_{e\in A(F)}$ to its arcs\, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e \in  A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic. \n[1] https://arxiv.org/abs/2208.06358 \n[2] https://arxiv.org/abs/2206.13635 URL:https://dimag.ibs.re.kr/event/2022-08-31/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220825T100000 DTEND;TZID=Asia/Seoul:20220825T110000 DTSTAMP:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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:20260417T215620 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