Eulerian properties of 3-uniform hypergraphs

Minisymposium: GENERAL SESSION TALKS

Content: A {\em flag} of a hypergraph $H=(V,E)$ is an ordered pair $(v,e)$ with $v \in V$, $e \in E$, and $v \in e$. A {\em closed trail} of $H$ is a sequence $W=v_0e_0v_1e_1v_2\ldots v_{k-1}e_{k-1}v_0$ with $v_i \in V$, $e_i \in E$, and $v_i,v_{i+1} \in e_i$ for each $i \in \mathbb{Z}_k$ such that no flag --- that is, $(v_i,e_i)$ or $(v_{i+1},e_i)$ --- is repeated. A closed trail $W$ is called an {\em Euler tour} of $H$ if it traverses each flag $(v,e)$ of $H$ exactly once, and a {\em strict Euler tour} if it traverses each edge of $H$ exactly once. A family of closed trails of $H$ that jointly traverse each edge of $H$ exactly once is called an {\em Euler family}. For a connected graph, the concepts of Euler tour, strict Euler tour, and Euler family are identical, however, for a general hypergraph, they give rise to three rather distinct problems. For example, while the problems of existence of an Euler tour and Euler family are polynomial on the set of all hypergraphs, the problem of existence of a strict Euler tour is NP-complete even just on the set of all linear 2-regular 3-uniform hypegraphs. In this talk, we shall briefly compare the three problems, and then focus on two main results: (1) every 3-uniform hypergraph without cut edges has an Euler family, and (2) every triple system has a strict Euler tour.

Back to all abstracts