2022 Combinatorics Workshop

Session

Session 3

1 Oct 2022, 10:00

Description

Chair: Heesung Shin

44. Some new results on geometric transversals

Andreas Holmsen (KAIST)

01/10/2022, 10:00

Invited talk

The study of geometric transversals deals with generalizations of Helly's theorem. Instead of intersecting convex sets by points, we now wish to intersect convex sets by $k$-dimensional affine flats. The modern development of Helly type theorems (colorful, fractional, $(p,q)$ versions) has given rise to a number of new questions about general geometric transversals. In this talk I will survey...

27. Strong Erd\H{o}s-Hajnal property on chordal graphs and its variants

Minho Cho (KAIST)

01/10/2022, 11:20

Contributed talk

A graph class $\mathcal{G}$ has the strong EH(Erd\H{o}s-Hajnal) property if there is a constant $c=c(\mathcal{G})>0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m,m}$ as a subgraph where $m\ge c|V(G)|$. We prove that the chordal graphs satisfy strong Erd\H{o}s-Hajnal property with constant $c=2/9$.

On the other hand, a...

22. Stability version of Dirac's theorem and its applications for generalized Turán problems

Nika Salia (IBS Extremal Combinatorics and Probability Group)

01/10/2022, 11:45

Contributed talk

In 1952, Dirac proved that every $2$-connected $n$-vertex graph with the minimum degree $k+1$ contains a cycle of length at least $min\{n,2(k+1)\}$. Here we obtain a stability version of this result by characterizing those graphs with minimum degree $k$ and circumference at most $2k+1$.

We present applications of the above-stated result by obtaining generalized Tur\'an numbers.
In...