Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
10 events found.
Events
-
-
Zoom ID: 869 4632 6610 (ibsdimag)
-
Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
Room B332 IBS (기초과학연구원)We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, …
-
Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon
Zoom ID: 224 221 2686 (ibsecopro)Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density, random subsets minimise the number of solutions to $\Psi$? This …
-
Maya Sankar, The Turán Numbers of Homeomorphs
Room B332 IBS (기초과학연구원)Let $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics …
-
-
Eunjin Oh (오은진), Parameterized algorithms for the planar disjoint paths problem
Room B332 IBS (기초과학연구원)Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find …
-
Marcelo Sales, On Pisier type problems
Zoom ID: 224 221 2686 (ibsecopro)A subset $A\subseteq \mathbb Z$ of integers is free if for every two distinct subsets $B, B'\subseteq A$ we have \Pisier asked if for every subset $A\subseteq \mathbb Z$ of …
-
Stijn Cambie, Recent progress on the Union-closed conjecture and related
Room B332 IBS (기초과학연구원)We give a summary on the work of the last months related to Frankl's Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set …
-
Paul Seymour, A loglog step towards the Erdős-Hajnal conjecture
Zoom ID: 869 4632 6610 (ibsdimag)In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size …
-
Younjin Kim (김연진), Problems on Extremal Combinatorics
Room B332 IBS (기초과학연구원)Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers, sets, graphs) satisfying certain properties. In this talk, I introduce the conjectures I solved on Extremal Combinatorics, and …
-
Qizhong Lin, Two classical Ramsey-Turán numbers involving triangles
Zoom ID: 224 221 2686 (ibsecopro)In 1993, Erdős, Hajnal, Simonovits, Sós and Szemerédi proposed to determine the value of Ramsey-Turán density $\rho(3,q)$ for $q\ge3$. Erdős et al. (1993) and Kim, Kim and Liu (2019) proposed …