Partitioning problems in dense hypergraphs (Q5957354)

Szemerédi's regularity lemma [\textit{E. Szemérdi}, Problèmes combinatoires et théorie des graphes, Colloq. Internat. CNRS No. 260, 399-401 (1978; Zbl 0413.05055)] and an algorithmic version thereof for hypergraphs [\textit{A. Czygrinow} and \textit{V. Rödl}, SIAM J. Comput. 30, No. 4, 1041-1066 (2000; Zbl 0971.05084)] are used to develop polynomial time approximation schemes for a general partition problem and a discrepancy problem in dense hypergraphs. More precisely, for all integers \(k\geq l\) there is an algorithm which, for every \(l\)-uniform hypergraph \(H=(V,E)\) with \(|V|=n\) and every \(\eta\), \(0 <\eta < 1\), finds in \(O(n^{2l-1}\log^2n)\) time a partition \(V_1, V_2,\dots, V_k\) of \(V\) such that \(f(V_1,\dots, V_k)\geq\max\{f(U_1,\dots, U_k):\bigcup U_i=V\) and \(U_i\cap U_j =\emptyset\text{ for } i\neq j\} -\eta n^l\), where \(f(V_1,\dots, V_k) =|\{e\in E:|e\cap V_i|\leq 1\text{ for } i=1,\dots,k\}|\). For every integer \(l\) there is an algorithm which, for every \(\{-1,+1\}\)-colouring \(\chi\) of the \(l\)-element subsets of \([n]=\{1,2,\dots,n\}\) and \(0 <\eta < 1\), finds in \(O(n^{2l-1}\log^2n)\) time a set \(S\subseteq[n]\) such that \(d(S)\geq\max\{d(T): T\subseteq[n]\} -\eta n^l\), where \(d(S) =|\sum_{|e|=l, e\subseteq S}\chi(e)|\).