• Gabriëlle Zwaneveld, On Seymour-tight orientations

    Room B332 IBS (기초과학연구원)

    I discuss 'almost counterexamples' to Seymour's second neighbourhood conjecture. In what we call Seymour-tight orientations, the size of the first neighbourhood of each vertex equals the size of its second neighbourhood. We give several examples and constructions. Specifically, we prove that the class of Seymour-tight orientations is closed under taking (generalized) lexicographic products. Moreover, the …

  • David R. Wood, The Erdős-Sós Theorem

    Room B332 IBS (기초과학연구원)

    We present an exposition of a proof, discovered by GPT-6 Astra, of the Erdős-Sós Conjecture, which states that every graph with average degree greater than t−2 contains every tree on t≥2 vertices.

  • David R. Wood, Proof of the Clustered Hadwiger Conjecture

    Room B332 IBS (기초과학연구원)

    Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger's Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of …

  • Daniel McGinnis, Multi-generic initial ideals, regularity, and the optimal colorful fractional Helly theorem for $d$-Leray complexes

    Room B332 IBS (기초과학연구원)

    A celebrated result of Bayer and Stillman from 1987 states that for a homogeneous ideal $I$ of a polynomial ring $S$, the regularities of $S/I$ and $S/\textrm{GIN}(I)$ are the same under the reverse lexicographic monomial ordering, where $\textrm{GIN}(I)$ is the generic initial ideal. If $R$ is a polynomial ring whose variables are subdivided into disjoint …

  • Julien Codsi, Recent progress in the tree-⍺ world

    Room B332 IBS (기초과학연구원)

    Treewidth is a graph parameter commonly used to quantify how "close" a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk, we discuss the tree-independence number, a more versatile graph parameter that …

  • Xiying Du, Characterizing (2,3)-linked graphs

    Room B332 IBS (기초과학연구원)

    We say a graph $G$ is $(2,m)$-linked if, for every choice of $m+2$ distinct vertices $a_1,\ldots,a_m,b_1,b_2$ in $G$, there exist two vertex-disjoint connected subgraphs $A$ and $B$ of $G$ such that $\{a_1,\ldots,a_m\}\subseteq V(A)$ and $\{b_1,b_2\}\subseteq V(B)$. A related notion is $k$-linkedness: a graph is $k$-linked if, for any distinct vertices $s_1,\ldots,s_k,t_1,\ldots,t_k$, it contains $k$ pairwise …

  • Hyunwoo Lee (이현우), Proof of the Erdős-Szemerédi sunflower conjecture

    Room B332 IBS (기초과학연구원)

    In the 1970s, Erdős and Szemerédi conjectured that for any $n \ge k-1\ge 2$, any collection of subsets of $$ not containing a $k$-sunflower has size at most $c_k^n$ for some $c_k<2$. In the $k=3$ case, this follows from the work of Croot, Lev, and Pach and Ellenberg and Gijswijt on the cap-set problem, through …

  • Hikaru Yokoi, The self-duality of pathwidth

    Room B332 IBS (기초과학연구원)

    How close are the width parameters of a plane graph and its (geometric) dual? Research motivated by this question, known as the self-duality of width parameters, originated from the seminal work by Robertson and Seymour. In this talk, we focus on the self-duality of pathwidth and present new results for polyhedral embeddings (a generalization of …

  • Denys Bulavka, The Typical Algebraic Shifting of Graphs and Surfaces

    Room B332 IBS (기초과학연구원)

    We initiate a statistical study of Kalai's exterior algebraic shifting, focusing on concentration phenomena for random triangulations of a fixed space. First, for a uniform refinement of any given graph, we show that asymptotically almost-surely (a.a.s.) its exterior algebraic shifting is an explicit shifted graph depending only on the number of vertices and the Betti …

  • Joonkyung Lee (이준경), The positive graph theorem

    Room B332 IBS (기초과학연구원)

    A graph H is said to be positive if its homomorphism density tH(W) is non-negative for every bounded symmetric measurable function W:2 → ℝ. Antolín Camarena, Csóka, Hubai, Lippner and Lovász conjectured that a graph is positive if and only if it can be obtained by gluing two copies of the same graph along an …