Seminario delle Dottorande e dei Dottorandi

A 3-uniform hypergraph H consists of a set V of vertices, and a subset of triples of V, called set of edges E. Let a null labeling be an assignment of +1 or -1 to the triples such that each vertex has a signed degree equal to zero. If a null labeling exists, we say that the hypergraph is null. Assumed as necessary condition the degree of every vertex of H to be even, the Null Labeling Problem consists in determining whether H has a null labeling. It is remarkable that null hypergraphs arise considering two hypergraphs with the same degree sequence. In particular, the symmetric differences of these two hypergraphs give a new hypergraph that is null. From a discrete tomography point of view, null hypergraphs arise from matrices with the same projections, i.e. solutions of the same reconstruction problem. Therefore they allow modeling of switching components, a very used notion in this field of research.
Although the problem is NP-complete, the subclasses where the problem turns out to be polynomially solvable are of interest. We defined the notion of 2-intersection graph related to a 3-uniform hypergraph and we prove that if it is Hamiltonian then the related 3-hypergraph has a null labeling. Then we aimed to deepen the knowledge of the structural properties of 2-intersection graphs. Going into details, we studied when, given a graph G, it is possible to find a 3-hypergraph such that its 2-intersection graph is G. If it is possible, we say that G is reconstructable or equivalently, it has the 2-intersection property. It’s easy to see that the question is relatively straightforward for some classes. However, using some suitable gadgets, we proved that the problem in its general form is NP-Complete.