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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230802T163000
DTEND;TZID=Asia/Seoul:20230802T173000
DTSTAMP:20260419T002242
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:20230809T100000
DTEND;TZID=Asia/Seoul:20230809T160000
DTSTAMP:20260419T002242
CREATED:20230802T144334Z
LAST-MODIFIED:20240707T073343Z
UID:7441-1691575200-1691596800@dimag.ibs.re.kr
SUMMARY:2023 Mini-Workshop on Discrete Geometry
DESCRIPTION:2023 Mini-Workshop on Discrete Geometry will be held on August 9th at Room B332\, Institute for Basic Science (IBS)\, Daejeon\, Republic of Korea. \nThe workshop consists of three presentations on recent results and an open problem session. \nResearchers who are highly interested in this field are welcome to attend. \nTentative schedule\n\n10:00-10:50 Michael Dobbins (SUNY Binghamton): Colorful intersections\, Tverberg partitions\, and geometric transversals\n11:00-11:30 Andreas Holmsen (KAIST): The topology of the complex of ordered partitions\n11:30-13:30 Lunch and free discussion\n13:30-14:10 Minki Kim김민기 (GIST): Some variants of the colorful Helly theorems\n14:20-16:00 Open problem session\n16:30-17:30 Discrete Math Seminar: R. Amzi Jeffs (Carnegie Mellon University)\n\nOrganizers\n\nAndreas Holmsen (KAIST)\nJinha Kim김진하 (IBS Discrete Mathematics Group)\nMinki Kim김민기 (GIST)\nSang-il Oum엄상일 (IBS Discrete Mathematics Group / KAIST)\n\nAbstracts\nMichael Dobbins (SUNY Binghamton): Colorful intersections\, Tverberg partitions\, and geometric transversals\nGiven three red convex sets and three blue convex sets in three-dimensional space\, suppose every red set intersects every blue set. Montejano’s theorem says there is a line that intersects all the red sets or all the blue sets. This was generalized to k-transversals in $\mathbb R^d$ by Montejano and Karasev using sophisticated algebraic and topological tools. Here we give further generalizations based on more accessible methods such as the test-map/configuration space scheme\, Sarkaria’s tensor method\, and discrete Morse theory. \nAndreas Holmsen (KAIST): The topology of the complex of ordered partitions\nThe set of partitions of {1\,…\,n} into k nonempty ordered parts can be equipped with a natural cell-complex structure which we denote by P(n\,k). Here we use discrete Morse theory to show that P(n\,k) is homotopy equivalent to a wedge of (n-k)-dimensional spheres\, where the number of spheres is given in terms of Stirling numbers of the second kind. Our result has applications related to geometric transversals and Tverberg partitions. \nMinki Kim (GIST): Some variants of the colorful Helly theorems\n\nGiven a finite family $F$ of nonempty sets\, the nerve of $F$ is the simplicial complex on $F$ whose simplices are precisely the intersecting subfamilies of $F$. The colorful Helly theorem\, which generalizes Helly’s theorem\, asserts the following: if $X$ is the nerve of the disjoint union of $d+1$ many finite families $F_1\,\ldots\,F_{d+1}$ of convex sets in $\mathbb{R}^d$ where each $F_i$ is not a simplex in $X$\, then there is a colorful $(d+1)$-tuple that is not a simplex of $X$. It was shown by Kalai and Meshulam that the same statement holds for $d$-collapsible/Leray complexes. In this talk\, I will explain the notion of $d$-collapsibility and $d$-Lerayness of simplicial complexes\, and present recent results on variants of the colorful Helly theorem and applications. This is based on joint work with Alan Lew.
URL:https://dimag.ibs.re.kr/event/2023-discrete-geometry/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230809T163000
DTEND;TZID=Asia/Seoul:20230809T173000
DTSTAMP:20260419T002242
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:20260419T002242
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:20260419T002242
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