Sebastian Wiederrecht, Killing a vortex
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 …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
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 …
-
Florent Koechlin, Uniform random expressions lack expressivity
Room B332 IBS (기초과학연구원)In computer science, random expressions are commonly used to analyze algorithms, either to study their average complexity, or to generate benchmarks to test them experimentally. In general, these approaches only …
-
-
Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Room B332 IBS (기초과학연구원)Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers. The $(p,r,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists …
-
Sebastian Wiederrecht, Excluding single-crossing matching minors in bipartite graphs
Room B332 IBS (기초과학연구원)By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change …
-
Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
Room B332 IBS (기초과학연구원)A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices. A linear $3$-graph is called a Steiner triple system if …
-
-
Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Room B332 IBS (기초과학연구원)The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ …
-
Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets
Room B332 IBS (기초과학연구원)Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to …