Speaker: Songling Shan
Title: Eulerian hypergraphs
Abstract:
Let $k\ge 3$ and $H$ be a $k$-uniform hypergraph. An Euler tour in $H$ is an alternating sequence
$v_0, e_1, v_1, e_2, v_2, \cdots, v_{m-1}, e_m, v_m=v_0$ of vertices and edges in $H$ such that each
edge of $H$ appears in this sequence exactly once and $v_{i-1}, v_i\in e_i$,$v_{i-1}\ne v_i$, for every
$i= 1,2, . . . , m$. Lonc and Naroski showed that for $k\ge 3$, the problem of determining if a given
$k$-uniform hypergraph has an Euler tour is NP-complete. For $1\le \ell \le k$, the minimum $\ell$-degree
of $H=(V,E)$ is $\delta_{\ell}(H)=\min_{S\subseteq V, |S|=\ell}|\{ e \,|\, S\subseteq e, e\in E\}|$.
\v{S}ajna and Wagner showed that every 3-uniform hypergraph $H=(V,E)$ with $\delta_2(H)\ge 2$ admits an Euler tour.
As a consequence, every $k$-uniform hypergraph $H=(V,E)$ with $\delta_{k-1}(H)\ge 2$ has an Euler tour.
We investigate the existence of Euler tour in $k$-uniform hypergraphs for $k\ge 4$ under $\ell$-degree conditions with $1\le \ell \le k-2$.
In particular, for $k\ge 4$, we show that every $k$-uniform hypergraph $H=(V,E)$ with $\delta_2(H)\ge k$ or $\delta_{k-2}(H)\ge 4$
and with $|V|\ge \frac{k^2}{2}+\frac{k}{2}$ admits an Euler tour.
This is Joint work with Amin Bahmanian.