Events Search and Views Navigation

Event Views Navigation

Today

  • Chong Shangguan (上官冲), On the sparse hypergraph problem of Brown, Erdős and Sós

    Zoom ID: 224 221 2686 (ibsecopro)

    For fixed integers $r\ge 3, e\ge 3$, and $v\ge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973, Brown, Erdős and Sós initiated the study of the function $f_r(n,v,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. …

    Continue Reading

  • 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 each pair of two distinct vertices belong to a unique edge. A simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all …

    Continue Reading

  • The 2nd Workshop on Developments in Combinatorics

    Zoom ID: 346 934 4087 (202209)

    Official website (with the abstract) https://www.ibs.re.kr/ecopro/online-workshop-developments-in-combinatorics/ Invited Speakers Nov. 28 Monday Jie Han, Beijing Institute of Technology 15:30 Seoul, 14:30 Beijing, 06:30 UK, 07:30 EU Joonkyung Lee (이준경), Hanyang University 16:10 Seoul, 15:10 Beijing, 07:10 UK, 08:10 EU Lior Gishboliner, ETH Zürich 16:50 Seoul, 15:50 Beijing, 07:50 UK, 08:50 EU Alex Scott, University of Oxford …

    Continue Reading

  • Cosmin Pohoata, Convex polytopes from fewer points

    Zoom ID: 224 221 2686 (ibsecopro)

    Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position, there exist $n$ points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds, which was nearly settled by …

    Continue Reading

  • 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,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every …

    Continue Reading

  • Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles

    Zoom ID: 224 221 2686 (ibsecopro)

    Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that …

    Continue Reading

  • 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 determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising …

    Continue Reading

  • 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 Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the "subtour elimination" linear programming …

    Continue Reading

  • 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 decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain  how to define in MSOL branch-decompositions for finitely …

    Continue Reading

  • Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins

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

    We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for …

    Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.