Large hypertree width for sparse random hypergraphs (Q2343976)

The authors show a linear hypertree in sparse random \(k\)-uniform hypergraphs. The paper is divided into four sections. In Section 1 are related results of other authors from the domain of this paper and in Section 2, the authors introduce the necessary definitions and notations: constraint satisfation problems, model RB and model RD, random hypergraphs, tree width, hypertree width. Lower bounds on hypertree width for random hypergraphs are shown in Section 3: when the number of hyperedges is super linear to the vertices, the linear hypertree width depends only on \(k\) and when the number of hyperedges is linear to the vertices, the linear hypertree width depends on \(k\) and the number of edges. In Section 4, the authors conclude with remarks on the results and open problems.