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:20210101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230517T160000 DTEND;TZID=Asia/Seoul:20230517T170000 DTSTAMP:20260417T221344 CREATED:20230220T090319Z LAST-MODIFIED:20240705T165050Z UID:6807-1684339200-1684342800@dimag.ibs.re.kr SUMMARY:Szymon Toruńczyk\, Flip-width: Cops and Robber on dense graphs DESCRIPTION:We define new graph parameters\, called flip-width\, that generalize treewidth\, degeneracy\, and generalized coloring numbers for sparse graphs\, and clique-width and twin-width for dense graphs. The flip-width parameters are defined using variants of the Cops and Robber game\, in which the robber has speed bounded by a fixed constant r∈N∪{∞}\, and the cops perform flips (or perturbations) of the considered graph. We then propose a new notion of tameness of a graph class\, called bounded flip-width\, which is a dense counterpart of classes of bounded expansion of Nešetril and Ossona de Mendez\, and includes classes of bounded twin-width of Bonnet\, Kim\, Thomassé\, and Watrigant. This unifies Sparsity Theory and Twin-width Theory\, providing a common language for studying the central notions of the two theories\, such as weak coloring numbers and twin-width — corresponding to winning strategies of one player — or dense shallow minors\, rich divisions\, or well-linked sets\, corresponding to winning strategies of the other player. We prove that boundedness of flip-width is preserved by first-order interpretations\, or transductions\, generalizing previous results concerning classes of bounded expansion and bounded twin-width. We provide an algorithm approximating the flip-width of a given graph\, which runs in slicewise polynomial time (XP) in the size of the graph. Finally\, we propose a more general notion of tameness\, called almost bounded flip-width\, which is a dense counterpart of nowhere dense classes. We conjecture\, and provide evidence\, that classes with almost bounded flip-width coincide with monadically dependent (or monadically NIP) classes\, introduced by Shelah in model theory. We also provide evidence that classes of almost bounded flip-width characterise the hereditary graph classes for which the model-checking problem is fixed-parameter tractable. URL:https://dimag.ibs.re.kr/event/2023-05-17/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230419T163000 DTEND;TZID=Asia/Seoul:20230419T173000 DTSTAMP:20260417T221344 CREATED:20230301T064147Z LAST-MODIFIED:20240705T165047Z UID:6852-1681921800-1681925400@dimag.ibs.re.kr SUMMARY:Shin-ichiro Seki\, On the extension of the Green-Tao theorem to number fields DESCRIPTION:In 2006\, Tao established the Gaussian counterpart of the celebrated Green-Tao theorem on arithmetic progressions of primes. In this talk\, I will explain the extension of Tao’s theorem and the Green-Tao theorem to the case of general number fields. Our combinatorial tool is the relative hypergraph removal lemma by Conlon-Fox-Zhao. I will discuss the difficulties that arise in the case of general number fields and an application of our results to prime representations by binary quadratic forms. This is based on joint work with Wataru Kai\, Masato Mimura\, Akihiro Munemasa\, and Kiyoto Yoshino. URL:https://dimag.ibs.re.kr/event/2023-04-19/ LOCATION:Zoom ID: 897 6822 0619 (ibsecopro) [04/19 only] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230406T100000 DTEND;TZID=Asia/Seoul:20230406T110000 DTSTAMP:20260417T221344 CREATED:20230118T233830Z LAST-MODIFIED:20240707T073746Z UID:6691-1680775200-1680778800@dimag.ibs.re.kr SUMMARY:Jie Han\, Spanning trees in expanders DESCRIPTION:We consider the spanning tree embedding problem in dense graphs without bipartite holes and sparse graphs. In 2005\, Alon\, Krivelevich and Sudakov asked for determining the best possible spectral gap forcing an $(n\,d\,\lambda)$-graph to be $T(n\, \Delta)$-universal. In this talk\, we introduce our recent work on this conjecture. URL:https://dimag.ibs.re.kr/event/2023-04-06/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230322T163000 DTEND;TZID=Asia/Seoul:20230322T173000 DTSTAMP:20260417T221344 CREATED:20230118T233720Z LAST-MODIFIED:20240707T092054Z UID:6688-1679502600-1679506200@dimag.ibs.re.kr SUMMARY:Qizhong Lin\, Two classical Ramsey-Turán numbers involving triangles DESCRIPTION:In 1993\, Erdős\, Hajnal\, Simonovits\, Sós and Szemerédi proposed to determine the value of Ramsey-Turán density $\rho(3\,q)$ for $q\ge3$. Erdős et al. (1993) and Kim\, Kim and Liu (2019) proposed two corresponding conjectures. However\, we only know four values of this Ramsey-Turán density by Erdős et al. (1993). There is no progress on this classical Ramsey-Turán density since then. In this talk\, I will introduce two new values of this classical Ramsey-Turán density. Moreover\, the corresponding asymptotically extremal structures are weakly stable\, which answers a problem of Erdős et al. (1993) for the two cases. Joint work with Xinyu Hu. URL:https://dimag.ibs.re.kr/event/2023-03-22/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230316T100000 DTEND;TZID=Asia/Seoul:20230316T110000 DTSTAMP:20260417T221344 CREATED:20230213T121859Z LAST-MODIFIED:20240707T073949Z UID:6788-1678960800-1678964400@dimag.ibs.re.kr SUMMARY:Paul Seymour\, A loglog step towards the Erdős-Hajnal conjecture DESCRIPTION:In 1977\, Erdős and Hajnal made the conjecture that\, for every graph $H$\, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. \nThere has no improvement on this result (for general $H$) until now\, but now we have an improvement: that for every graph $H$\, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ This talk will outline the proof. \nJoint work with Matija Bucić\, Tung Nguyen and Alex Scott. URL:https://dimag.ibs.re.kr/event/2023-03-16/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230309T100000 DTEND;TZID=Asia/Seoul:20230309T110000 DTSTAMP:20260417T221344 CREATED:20230118T233622Z LAST-MODIFIED:20240707T074003Z UID:6685-1678356000-1678359600@dimag.ibs.re.kr SUMMARY:Marcelo Sales\, On Pisier type problems DESCRIPTION:A subset $A\subseteq \mathbb Z$ of integers is free if for every two distinct subsets $B\, B’\subseteq A$ we have \[ \sum_{b\in B}b\neq \sum_{b’\in B’} b’.\]Pisier asked if for every subset $A\subseteq \mathbb Z$ of integers the following two statement are equivalent: \n(i) $A$ is a union of finitely many free sets.\n(ii) There exists $\epsilon>0$ such that every finite subset $B\subseteq A$ contains a free subset $C\subseteq B$ with $|C|\geq \epsilon |B|$. \nIn a more general framework\, the Pisier question can be seen as the problem of determining if statements (i) and (ii) are equivalent for subsets of a given structure with prescribed property. We study the problem for several structures including $B_h$-sets\, arithmetic progressions\, independent sets in hypergraphs and configurations in the euclidean space. This is joint work with Jaroslav Nešetřil and Vojtech Rödl. URL:https://dimag.ibs.re.kr/event/2023-03-09/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230222T170000 DTEND;TZID=Asia/Seoul:20230222T180000 DTSTAMP:20260417T221344 CREATED:20221115T011207Z LAST-MODIFIED:20240707T074027Z UID:6483-1677085200-1677088800@dimag.ibs.re.kr SUMMARY:Daniel Altman\, On an arithmetic Sidorenko conjecture\, and a question of Alon DESCRIPTION:Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density\, random subsets minimise the number of solutions to $\Psi$? This is an arithmetic analogue of a well-known conjecture of Sidorenko in graph theory\, which has remained open and of great interest since the 1980s. We will discuss some recent results along these lines\, with particular focus on some of the ideas behind a negative answer to a related question of Alon. URL:https://dimag.ibs.re.kr/event/2023-02-22/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230215T163000 DTEND;TZID=Asia/Seoul:20230215T173000 DTSTAMP:20260417T221344 CREATED:20230103T235641Z LAST-MODIFIED:20240705T170041Z UID:6623-1676478600-1676482200@dimag.ibs.re.kr SUMMARY:Robert Hickingbotham\, Treewidth\, Circle Graphs and Circular Drawings DESCRIPTION:A circle graph is an intersection graph of a set of chords of a circle. In this talk\, I will describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects’. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs\, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. I will also discuss applications of our results to the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting\, our results show that if the crossing graph is $K_t$-minor-free\, then $G$ has treewidth at most $12t-23$ and has no $K_{2\,4t}$-topological minor. On the other hand\, I’ll present a construction of graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate. This is joint work with Freddie Illingworth\, Bojan Mohar\, and David R. Wood URL:https://dimag.ibs.re.kr/event/2023-02-15/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230201T163000 DTEND;TZID=Asia/Seoul:20230201T173000 DTSTAMP:20260417T221344 CREATED:20230115T151551Z LAST-MODIFIED:20240705T170041Z UID:6664-1675269000-1675272600@dimag.ibs.re.kr SUMMARY:Benjamin Bergougnoux\, Tight Lower Bounds for Problems Parameterized by Rank-width DESCRIPTION:We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$\, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan\, Telle\, and Vatshelle [Discret. Appl. Math.\, 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math.\, 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set\, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs. \nThis is a joint work with Tuukka Korhonen and Jesper Nederlof.\nAccepted to STACS 2023 and available on arXiv https://arxiv.org/abs/2210.02117 URL:https://dimag.ibs.re.kr/event/2023-02-01/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230125T163000 DTEND;TZID=Asia/Seoul:20230125T173000 DTSTAMP:20260417T221344 CREATED:20221109T131052Z LAST-MODIFIED:20240705T171112Z UID:6458-1674664200-1674667800@dimag.ibs.re.kr SUMMARY:Jan Hladký\, Invitation to graphons DESCRIPTION:The first course in graph theory usually covers concepts such as matchings\, independent sets\, colourings\, and forbidden subgraphs. Around 2004\, Borgs\, Chayes\, Lovász\, Sós\, Szegedy\, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory\, so-called graphons\, are suitable measurable counterparts to graphs. In the talk\, I will outline the syllabus of a hypothetical first course in graphon theory\, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal\, Hu\, Máthé\, Piguet\, Rocha. URL:https://dimag.ibs.re.kr/event/2023-01-25/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230119T100000 DTEND;TZID=Asia/Seoul:20230119T110000 DTSTAMP:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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:20260417T221344 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 $ 1