Judiciously 3‐partitioning 3‐uniform hypergraphs. Issue 4 (6th February 2020)

• Record Type: Journal Article
• Authors: Spink, Hunter; Tiba, Marius
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 1205
• Page End: 1221
• Publication Date: 2020-02-06
• Subjects: hypergraph -- judicious partition -- concentration inequality -- azuma‐hoeffding -- optimization; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20908
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Bollobás, Reed, and Thomason proved every 3‐uniform hypergraph ℋ with m edges has a vertex‐partition V ()= V 1 ⊔ V 2 ⊔ V 3 such that each part meets at least 1 3 ( 1 − 1 e ) m edges, later improved to 0.6 m by Halsegrave and improved asymptotically to 0.65 m + o ( m ) by Ma and Yu. We improve this asymptotic bound to 19 27 m + o ( m ), which is best possible up to the error term, resolving a special case of a conjecture of Bollobás and Scott.