Tuesday, August 23, 2022

2022-08-30 / 14:30 ~ 16:00

by ()

This talk is the very first talk for a semester long series on higher algebra. Higher algerbra is the study of algebraic objects in spaces, correcting abnormal behavior of classical homological algebra and encorporating spheres into algebra. In this talk, we will see a concerete example of a higher-algebraic structure on singular cochains, and what structures are needed to formalize such structures with concrete diagrams. We assume familiarity with algebraic topology, category theory and homological algebra (at the first year graduate level).

2022-08-30 / 16:30 ~ 17:30

IBS-KAIST 세미나 - 이산수학: Number of (k-1)-cliques in k-critical graph

by Jun Gao(IBS 극단조합및확률그룹)

We prove that for $n>k\geq 3$, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. This is joint work with Jie Ma.

2022-08-23 / 16:30 ~ 17:30

IBS-KAIST 세미나 - 이산수학: Temporal Menger and related problems

by Raul Lopes(CNRS, LAMSADE, Paris, France)

A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability, i.e. sequence of adjacent edges whose appearing times are non-decreasing. Given a graph G and vertices s and t of G, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s,t-paths is equal to the minimum size of a subset X for which G-X contains no s,t-path. This is a classical result in Graph Theory, taught in most basic Graph Theory courses, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe, Kleinberg and Kumar (STOC’00). In this talk, an overview of possible temporal versions of Menger’s Theorem will be discussed, as well as the complexity of the related problems.

Events for the 취소된 행사 포함