Two examples of hypergraph edge-coloring, and their connections with other topics in Combinatorics
Andrea Vietri · 2002
This thesis consists of two independent parts, whose common root is the notion of hypergraph edge-coloring. In the first part we deal with a class of non-directed hypergraphs. A particular kind of edge-coloring is defined and studied in Chapter 2. The analysis of such coloring leads to a different topic in Chapter 3, namely total weight orders over monomials of fixed degree. We remark that our results on weight orders are not related to Chapter 2. Indeed, the edge-coloring has provided nothing more than a motivation for subsequently focusing on the main topic. Nevertheless, some combinatorial properties of these hypergraphs seemed nice to us. This is the reason why we have dedicated the whole Chapter 2 to them. On the contrary, the second notion of edge-coloring has a fundamental role in Part II. In this context, every edge of a hypergraph consists of a tail (a subset of the vertices) and a head (one vertex). Following the current terminology, edges and vertices are renamed as arcs and nodes respectively, whereas the hypergraph is said to be directed. We define a notion of coloring for the arcs. Our definition is an extension of the existing notion of arc-coloring for directed graphs. We enlight some relationships between the incidence structure and the coloring properties. In particular, we analyze the question of minimizing the number of colors. We are led to consider some combinatorial properties of adjacency matrices for hypergraphs. Such matrices generalize the intuitive concept of a wall made of bricks. In our rephrasing, coloring the arcs corresponds to adequately coloring each brick of the wall.