Some Cubic Time Regularity Algorithms for Triple Systems

DOI10.1137/21M145046XMaRDI QIDQ6188523zbMATH OpenOpenAlexWikidataFDO

Authors B. Nagle

Publication date 7 February 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/21m145046x

zbMATH Keywords

algorithmshypergraphsregularity

Mathematics Subject Classification ID

Triple systems (05B07) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• An Algorithmic Version of the Hypergraph Regularity Method
• Approximate hypergraph partitioning and applications
• scientific article; zbMATH DE number 1256685
• An Algorithmic Hypergraph Regularity Lemma
• The Algorithmic Aspects of the Regularity Lemma

Cites work

• A new generalization of the Erdős-Ko-Rado theorem
• A short proof of Gowers' lower bound for the regularity lemma
• A tight bound for hypergraph regularity
• A tight lower bound for Szemerédi's regularity lemma
• A Wowzer-type lower bound for the strong regularity lemma
• Almost all hypergraphs without Fano planes are bipartite
• Almost all triangle-free triple systems are tripartite
• Almost all triple systems with independent neighborhoods are semi-bipartite
• An algorithmic hypergraph regularity lemma
• An Algorithmic Hypergraph Regularity Lemma
• An Algorithmic Regularity Lemma for Hypergraphs
• An Algorithmic Version of the Hypergraph Regularity Method
• An Optimal Algorithm for Checking Regularity
• Bounds for graph regularity and removal lemmas
• Extremal problems on set systems
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 6273781 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Integer and fractional packings in dense graphs
• On sets of integers containing k elements in arithmetic progression
• On Triple Systems with Independent Neighbourhoods
• Regularity Lemma for k-uniform hypergraphs
• Regularity lemmas for hypergraphs and quasi-randomness
• Regularity properties for triple systems
• Stability theorems for cancellative hypergraphs
• The Algorithmic Aspects of the Regularity Lemma
• The uniformity lemma for hypergraphs

This page was built for publication: Some Cubic Time Regularity Algorithms for Triple Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188523)