Judicious partitions of hypergraphs
The authors show: Let \(G\) be a 3-uniform hypergraph with \(m\)-edges, let \(k\geq 2\) be an integer, and let \(p_1,\dots,p_k\) be nonnegative reals such that \(\sum_{i=1}^kp_i=1\). Then there is a partition \(V(G)=\bigcup_{i=1}^kV_i\) such that, for \(i=1,\dots,k\), we have \(e(V_i)\leq p_i^3m+5m^{6/7}(\log k)^{1/2}\) and \(e(\bigcup_{j=1}^iV_j)<(\sum_{j=1}^ip_j)^3m+5m^{6/7}(\log k)^{1/2}\), where \(e(V_i)\) is the total numbers of edges of \(V_i\). From this, the main result of the present paper follows easily: Let \(G\) be a 3-uniform hypergraph with \(m\)-edges and let \(k\geq 2\) be an integer. Then there is a vertex partition of \(G\) into \(k\) sets with at most \(m/k^3+5m^{6/7}(\log k)^{6/7}\) edges in each set.
- `` Strong NP-Completeness Results
- Global versus local asymptotic theories of finite-dimensional normed spaces
- How to make a graph bipartite
- scientific article; zbMATH DE number 3851127 (Why is no real title available?)
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 17671 (Why is no real title available?)
- scientific article; zbMATH DE number 193014 (Why is no real title available?)
- scientific article; zbMATH DE number 3510345 (Why is no real title available?)
- scientific article; zbMATH DE number 3639656 (Why is no real title available?)
- scientific article; zbMATH DE number 4128851 (Why is no real title available?)
- scientific article; zbMATH DE number 3307332 (Why is no real title available?)
- Probability Inequalities for Sums of Bounded Random Variables
- Some Extremal Properties of Bipartite Subgraphs
- Weighted sums of certain dependent random variables
- Über die Approximation von Zahlen durch Reihen mit positiven Gliedern
- The partition of a uniform hypergraph into pairs of dependent hyperedges
- Partitioning dense uniform hypergraphs
- Judicious partitions of 3-uniform hypergraphs
- Exact bounds for judicious partitions of graphs
- On the number of linear multipartite hypergraphs with given size
- On judicious bipartitions of directed graphs
- A bound on judicious bipartitions of directed graphs
- On judicious partitions of hypergraphs with edges of size at most 3
- The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
- On judicious partitions of uniform hypergraphs
- Judicious bisection of hypergraphs
- Bounds for pairs in judicious partitioning of graphs
- On some partitions of hypergraphs and cumulants having applications in statistical mechanics
- scientific article; zbMATH DE number 3950580 (Why is no real title available?)
- Judicious partitions of bounded‐degree graphs
- Bisections of graphs without short cycles
- The Bollobás-Scott conjecture for 4-uniform hypergraphs
- Problems and results on judicious partitions
- Judicious partitions of uniform hypergraphs
- Bounds for \(l\)-tuples in judicious partition of hypergraphs and graphs
- Judiciously 3-partitioning 3-uniform hypergraphs
- Balanced judicious bipartition is fixed-parameter tractable
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Judicious partitioning of hypergraphs with edges of size at most 2
- Erratum: The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs
- Partitioning problems in dense hypergraphs
- On several partitioning problems of Bollobás and Scott
- Partitions of hypergraphs under variable degeneracy constraints
- On bisections of graphs without complete bipartite graphs
- Graph partitioning: an updated survey
- Optimal bisections of directed graphs
- A note on judicious bisections of graphs
- Bisections of directed graphs without complete bipartite subgraphs
- On ratio-k-cuts of graphs
- Simple probabilistic analysis to generalize bottleneck graph multi-partitioning
- Bipartitions of oriented graphs
- Partitioning 3-uniform hypergraphs
- Bounds for pairs in partitions of graphs
- Max \(k\)-cut and judicious \(k\)-partitions
This page was built for publication: Judicious partitions of hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356017)
