\((k-2)\)-linear connected components in hypergraphs of rank \(k\) (Q6599814)

A linear path in an undirected graph is a sequence of edges such that any two consecutive edges intersect on exactly one vertex and any two non-consecutive edges do not intersect. The existence of such paths is the subject matter of several extremal results. The connectivity problem associated with linear paths in 3-uniform hypergraphs has stimulated the authors to do this work. To probe the linear connected components to elucidate their structure, the authors develop methods that generalize to hypergraphs of rank \(k\geq 4\) when replacing linearity with a notion of \((k-2)\)-linearity. They introduce the general concept of a \(q\)-linear path, where any consecutive edges intersect between 1 and \(q\) vertices. The proof of their structural result allows them to compute the \((k-2)\)-linear connected components in polynomial time. This led to interesting sequels on two algorithmic problems that have existed in the literature for a long time. The first one is the problem of deciding the winner of the Maker-Breaker positional game. The second one is the ``paths avoiding forbidden pairs'' problem which, given two vertices \(x\), \(y\) in a graph \(G\) with blue and red edges, asks whether there exists a blue-induced path between \(x\) and \(y\) in \(G\).