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 …
10 events found.
Discrete Math Seminar
-
-
-
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 …
-
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 …
-
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, …
-
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 …
-
-
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 …
-
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 …
-
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 …
-
-
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 …
-
Nika Salia, Exact results for generalized extremal problems forbidding an even cycle
Room B332 IBS (기초과학연구원)We determine the maximum number of copies of $K_{s,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover, for $s\in\{2,3\}$ and any integer …