Abstract | ||
---|---|---|
Bollobás and Scott showed that the vertices of a graph of m edges can be partitioned into k sets such that each set contains at most m / k 2 + o ( m ) edges. They conjectured that the vertices of an r-uniform hypergraph, where r ¿ 3 , of m edges may likewise be partitioned into k sets such that each set contains at most m / k r + o ( m ) edges. In this paper, we prove the weaker statement that a partition into k sets can be found in which each set contains at most m ( k - 1 ) r + r 1 / 2 ( k - 1 ) r / 2 + o ( m ) edges. Some partial results on this conjecture are also given. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.jcta.2016.02.004 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
Uniform hypergraph,Judicious partition,Azuma–Hoeffding inequality | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Constraint graph,Hypergraph,Partition (number theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
141 | C | 0097-3165 |
Citations | PageRank | References |
5 | 0.45 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
liu | 1 | 195 | 21.38 |
Shu-Fei Wu | 2 | 9 | 2.92 |
Guiying Yan | 3 | 196 | 22.92 |