Zixiang Xu (徐子翔), On the degenerate Turán problems
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 …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
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 …
-
-
Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs
Room B332 IBS (기초과학연구원)The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the …
-
Mamadou Moustapha Kanté, MSOL-Definable decompositions
Room B332 IBS (기초과학연구원)I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with …