July 2022

Jinyoung Park (박진영), Thresholds 2/2

Room B332 IBS (기초과학연구원)

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold.

August 2022

Seunghun Lee (이승훈), Inscribable order types

Room B332 IBS (기초과학연구원)

We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order

Eun Jung Kim (김은정), Directed flow-augmentation

Room B332 IBS (기초과학연구원)

We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,t\in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$

Noleen Köhler, Testing first-order definable properties on bounded degree graphs

Room B332 IBS (기초과학연구원)

Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study

Raul Lopes, Temporal Menger and related problems

Room B332 IBS (기초과학연구원)

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

Jun Gao, Number of (k-1)-cliques in k-critical graph

Room B332 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.

September 2022

Bjarne Schülke, A local version of Katona’s intersection theorem

Room B332 IBS (기초과학연구원)

Katona's intersection theorem states that every intersecting family $\mathcal F\subseteq^{(k)}$ satisfies $\vert\partial\mathcal F\vert\geq\vert\mathcal F\vert$, where $\partial\mathcal F=\{F\setminus x:x\in F\in\mathcal F\}$ is the shadow of $\mathcal F$. Frankl conjectured that for $n>2k$ and every intersecting family $\mathcal F\subseteq ^{(k)}$, there is some $i\in$ such that $\vert \partial \mathcal F(i)\vert\geq \vert\mathcal F(i)\vert$, where $\mathcal F(i)=\{F\setminus i:i\in F\in\mathcal Sebastian Wiederrecht, Killing a vortex Room B332 IBS (기초과학연구원) The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that, for every$t\in\mathbb{N},$there exists some constant$c_{t}$such that every$K_{t}$-minor-free graph admits a tree decomposition whose torsos can be transformed, by the removal of at most$c_{t}$vertices, to graphs that can be seen as the union of some Alexander Clifton, Ramsey Theory for Diffsequences Room B332 IBS (기초과학연구원) Van der Waerden's theorem states that any coloring of$\mathbb{N}$with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number$W(r,k)$which is the smallest$n$such that any$r$-coloring of$\{1,2,\cdots,n\}$guarantees the presence of a monochromatic arithmetic progression of length October 2022 Zixiang Xu (徐子翔), On the degenerate Turán problems Room B332 IBS (기초과학연구원) For a graph$F$, the Turán number is the maximum number of edges in an$n$-vertex simple graph not containing$F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \ where$\chi(F)$is the chromatic number of$H$. This theorem asymptotically solves the problem when$\chi(F)\geqslant 3$. In case of bipartite graphs$F\$, not even the order of magnitude

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209