Example of non-(normal) and non-($\tau$-normal) hypergraphs?

Question

According to Normal Hypergraphs and the Weak Perfect Graph Conjecture (these are definitions!):

• A hypergraph $H$ is normal if $\rho(H') \geq \delta(H')$ for every $H'$ partial hypergraph of $H$
• A hypergraph $H$ is $\tau$-normal if $\nu(H')\leq \tau(H')$ for every $H'$ partial hypergraph of $H$

Where:

1. $\rho(H):$ chromatic index of $H$, minimum number of colors needed to color the hyperedges so that intersecting hyperedges have different colors
2. $\delta(H):$ maximum (over all vertices) number of hyperedges containing a vertex
3. $\nu(H):$ maximum disjoint hyperedges (matching in Graph Theory)
4. $\tau(H):$ minimum cardinality of a set $A \subset V$, so that $A$ intersects all hyperedges (minimum covering vertices)

What is an example for a hypergraph that is not normal, and an example of a hypergraph that is not $\tau$-normal? I can't imagine how a (hyper)graph have a smaller chromatic index compared to degree of a vertex, though this might be because I'm not super familiar with hypergraphs yet.

I have learnt a fair amount of Graph Theory. Currently trying to understand the linked paper (in particular would like to understand the proof for the weak perfect graph theorem). I am also reading Claude Berge's book on Hypergraphs.

Furthermore, from Wikipedia:

The Konig property of a hypergraph H is the property that its minimum vertex-cover has the same size as its maximum matching.

If every partial hypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges - but not vertices), then H is called a normal hypergraph.

Is the definition in Wikipedia referring to a different class of hypergraphs? It looks like a smaller class of $\tau$-normal hypergraphs.

Answer 1

You have misquoted the definitions in the paper.

For normal hypergraphs, the paper says (adjusting for your notation):

Obviously, $\rho(H) \ge \delta(H)$. Let a hypergraph be called normal if equality holds for every partial hypergraph of it.

In other words, a hypergraph is normal if, for every partial hypergraph $H'$, $\rho(H') = \delta(H')$.

(Note: the words "partial hypergraph" indicate a hypergraph $H'$ with all the vertices of $H$ and a subset of its edges. This is the hypergraph analog of a spanning subgraph. A "subhypergraph" is the hypergraph version of an induced subgraph: it has a subset of the vertices of $H$, and keeps every edge of $H$ that intersects that subset. I wouldn't rely on this terminology universially, but both the Lovasz paper and the Wikipedia article on balanced hypergraphs use it.)

So, for example, the graph $C_5$ (which is also a $2$-uniform hypergraph) is not normal, because $\rho(C_5) = \chi'(C_5) = 3$ but $\delta(C_5) = 2$. Additionally, any graph (or hypergraph) which contains a copy of $C_5$ inside it is not normal.

Similarly, all hypergraphs $H$ satisfy $\nu(H) \le \tau(H)$. A hypergraph is called $\tau$-normal if $\nu(H') = \tau(H')$ for every partial hypergraph.

The definition of "normal hypergraph" in the Wikipedia article is the same as the definition "$\tau$-normal hypergraph" in the paper.