IMSc Webinar

On characterizing line graphs of hypergraphs

Pritam Majumder

TIFR, Mumbai

us02web.zoom.us/j/81955679702?pwd=OUdCTDg3bVJpd1ZTUXQrcEV5SVEvZz09
Meeting ID: 819 5567 9702. Password: Littlewood

A hypergraph is given by a finite set of vertices together with a collection of its subsets, called edges, of that set. A hypergraph is called k-uniform if all its edges have the same size k. The line graph of a k-uniform hypergraph is its edge-to-vertex dual graph, namely, its vertices bijectively correspond to the edges of the hypergraph and there is an edge between two vertices of the line graph if the corresponding edges in the hypergraph have non zero intersection. The characterization of line graphs of 2-uniform hypergraphs (graphs) have been extensively studied. The characterization of line graphs of k-uniform hypergraphs for k>2 is poorly understood. Partial results exist for linear hypergraphs (intersection of any two edges is at most 1 vertex). We study the problem of characterizing line graphs of k-uniform hypergraphs with bounded pair-degree by a finite class of forbidden subgraphs. We show that such a characterization is possible if we consider line graphs with certain minimum edge-degree. Time permitting, we shall discuss about some other reconstruction problems for hypergraphs, namely, characterizing degree sequences of hypergraphs and characterizing face numbers (f-vectors) of simplicial complexes.