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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230802T163000
DTEND;TZID=Asia/Seoul:20230802T173000
DTSTAMP:20260420T002629
CREATED:20230506T225557Z
LAST-MODIFIED:20240705T163040Z
UID:7156-1690993800-1690997400@dimag.ibs.re.kr
SUMMARY:Daniel Kráľ\, High chromatic common graphs
DESCRIPTION:Ramsey’s Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. As probabilistic constructions often provide good bounds on quantities in extremal combinatorics\, we say that a graph H is common if the random 2-edge-coloring asymptotically minimizes the number of monochromatic copies of H. This notion goes back to the work of Erdős in the 1960s\, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s\, however\, a classification of common graphs remains one of the most intriguing problems in extremal combinatorics. \nSidorenko’s Conjecture (if true) would imply that every bipartite graph is common\, and in fact\, no bipartite common graph unsettled for Sidorenko’s Conjecture is known. Until Hatami et al. showed that a 5-wheel is common about a decade ago\, all graphs known to be common had chromatic number at most three. The existence of a common graph with chromatic number five or more has remained open for three decades. \nWe will present a construction of (connected) common graphs with arbitrarily large chromatic number. At the end of the talk\, we will also briefly discuss the extension of the notion to more colors and particularly its relation to Sidorenko’s Conjecture. \nThe main result presented in the talk is based on joint work with Jan Volec and Fan Wei.
URL:https://dimag.ibs.re.kr/event/2023-08-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230809T163000
DTEND;TZID=Asia/Seoul:20230809T173000
DTSTAMP:20260420T002629
CREATED:20230403T234729Z
LAST-MODIFIED:20240705T164149Z
UID:6963-1691598600-1691602200@dimag.ibs.re.kr
SUMMARY:R. Amzi Jeffs\, Intersection patterns of convex sets
DESCRIPTION:How can one arrange a collection of convex sets in d-dimensional Euclidean space? This guiding question is fundamental in discrete geometry\, and can be made concrete in a variety of ways\, for example the study of hyperplane arrangements\, embeddability of simplicial complexes\, Helly-type theorems\, and more. This talk will focus on the classical topic of d-representable complexes and its more recent generalization to convex codes. We will show how these frameworks differ\, share some novel Helly-type results\, and offer several tantalizing open questions.
URL:https://dimag.ibs.re.kr/event/2023-08-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230822T163000
DTEND;TZID=Asia/Seoul:20230822T173000
DTSTAMP:20260420T002629
CREATED:20230425T022914Z
LAST-MODIFIED:20240707T073336Z
UID:7057-1692721800-1692725400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Orientations of $P_4$ bind the dichromatic number
DESCRIPTION:An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. \nThe Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs\, which states that for any forest $F$\, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(G)$ has chromatic number at most $f(\omega(G))$. \nAboulker\, Charbit\, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker\, Charbit\, and Naserasr’s $\overrightarrow{\chi}$-boundedness conjecture states that for every oriented forest $F$\, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$\, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. \nIn this talk\, we perform the first step towards proving Aboulker\, Charbit\, and Naserasr’s $\overrightarrow{\chi}$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.
URL:https://dimag.ibs.re.kr/event/2023-08-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230829T163000
DTEND;TZID=Asia/Seoul:20230829T173000
DTSTAMP:20260420T002629
CREATED:20230706T112113Z
LAST-MODIFIED:20240707T073327Z
UID:7355-1693326600-1693330200@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, From coordinate subspaces over finite fields to ideal multipartite uniform clutters
DESCRIPTION:Take a prime power $q$\, an integer $n\geq 2$\, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$\, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper\, we determine when the clutter $\mathcal{C}$ is ideal\, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly\, the characterization differs depending on whether $q$ is $2\,4$\, a higher power of $2$\, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified\, and only then is the global structure determined. A key insight is that idealness of $\mathcal{C}$ depends solely on the underlying matroid of $S$. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence\, we prove the Replication and $\tau=2$ conjectures for this class of clutters. This is joint work with Ahmad Abdi (London School of Economics).
URL:https://dimag.ibs.re.kr/event/2023-08-29/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR