%0 Journal Article %1 nagle2024cubic %A Nagle, Brendan %A Theado, John %B SIAM Journal on Discrete Mathematics %D 2024 %I Society for Industrial and Applied Mathematics %J SIAM J. Discrete Math. %K algorithm hypergraph mathematics %P 668--701 %R 10.1137/21M145046X %T Some Cubic Time Regularity Algorithms for Triple Systems %U https://doi.org/10.1137/21M145046X %X Szemerédi?s regularity lemma guarantees that, for fixed \(0\), every graph \(G = (V, E)\) admits an \(\varepsilon\)-regular and \(t\)-equitable partition \(\Pi (G)\), where \(t = O(1)\). These partitions are constructed by Kohayakawa, Rödl, and Thoma in time \(O(|V|^2)\). Analogous partitions of \(k\)-graphs \(H^(k)\) are constructed by Czygrinow and Rödl in time \(O(|V|^2k-1 łog^5 |V|)\). For \(k=3\), we construct these partitions (and others with slightly stronger regularity) in time \(O(|V|^3)\). We also discuss some applications.

@article{nagle2024cubic, abstract = {Szemerédi?s regularity lemma guarantees that, for fixed \(\varepsilon \gt 0\), every graph \(G = (V, E)\) admits an \(\varepsilon\)-regular and \(t\)-equitable partition \(\Pi (G)\), where \(t = O(1)\). These partitions are constructed by Kohayakawa, Rödl, and Thoma in time \(O(|V|^2)\). Analogous partitions of \(k\)-graphs \(H^{(k)}\) are constructed by Czygrinow and Rödl in time \(O(|V|^{2k-1} \log^5 |V|)\). For \(k=3\), we construct these partitions (and others with slightly stronger regularity) in time \(O(|V|^3)\). We also discuss some applications.}, added-at = {2024-02-09T12:35:04.000+0100}, author = {Nagle, Brendan and Theado, John}, biburl = {https://www.bibsonomy.org/bibtex/2a1b8ad6c93e2fc5b12668179762db06e/tabularii}, booktitle = {SIAM Journal on Discrete Mathematics}, comment = {doi: 10.1137/21M145046X}, doi = {10.1137/21M145046X}, interhash = {c6b498d1cfaddb66f7540e5ecdeb23d2}, intrahash = {a1b8ad6c93e2fc5b12668179762db06e}, issn = {08954801}, journal = {SIAM J. Discrete Math.}, keywords = {algorithm hypergraph mathematics}, month = feb, pages = {668--701}, publisher = {Society for Industrial and Applied Mathematics}, timestamp = {2024-02-09T12:35:04.000+0100}, title = {Some Cubic Time Regularity Algorithms for Triple Systems}, url = {https://doi.org/10.1137/21M145046X}, year = 2024 }