Maria Chudnovsky, Induced minors and treewidth
This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite …
10 events found.
Seminars and Colloquiums
Events
-
-
Room B332 IBS (기초과학연구원)
-
J. Pascal Gollin, Dominated balanced separators in wheel-induced-minor-free graphs
Room B332 IBS (기초과학연구원)The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices …
-
Harry Richman, Distinguishing graphs with tropical Weierstrass weights
Room B332 IBS (기초과학연구원)I will introduce a new structure on finite graphs, which takes the form of a labeling of the vertices by nonnegative integers (possibly repeated). This labeling is isomorphism invariant, and …
-
Stefan Weltge, The relaxation complexity of the standard simplex is logarithmic
Room B332 IBS (기초과학연구원)For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron P whose integer points are precisely those of X. In …
-
-
Ting-Wei Chao, The Oddtown Problem Modulo a Composite Number
Room B332 IBS (기초과학연구원)A family of sets in $$ is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by …
-
Yaobin Chen, Maximum in-general-position set in a random subset of $\mathbb{F}^d_q$
Room B332 IBS (기초과학연구원)Let $\alpha(\mathbb{F}_q^{d},p)$ be the maximum possible size of a point set in general position in a $p$-random subset of $\mathbb{F}_q^d$. We determine the order of magnitude of $\alpha(\mathbb{F}_q^{d},p)$ up to …
-
Sang-il Oum (엄상일), A proof of the cycle double cover conjecture by OpenAI
Room B332 IBS (기초과학연구원)The cycle double cover conjecture (CDC) claims that every graph without cut-edges has a list of cycles such that every edge appears exactly twice in the list. This conjecture was …
-
Zichao Dong, $k$-wise odd-even towns
Room B332 IBS (기초과학연구원)For $\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_k) \in {\mathbb F}_2^k$, an $\boldsymbol{\alpha} $-town is a set family in which every $i$-wise intersection has parity $\alpha_i$. Denote by $f_{\boldsymbol{\alpha} }(n)$ the maximum …
-
Stephan Kreutzer, Disjoint Paths in Graphs and Digraphs
Room B332 IBS (기초과학연구원)One of the important algorithmic consequences of Robertson and Seymour's Graph Minor Project is their proof that the k-Vertex-Disjoint Paths problem is fixed-parameter tractable on the class of all undirected …
-
-
Tomohiro Koana, A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
Room B332 IBS (기초과학연구원)We study restricted-link augmentation to 2-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1, \ldots, …