id: 05810785
dt: j
an: 05810785
au: Ma, Jie; Yen, Pei-Lan; Yu, Xingxing
ti: On several partitioning problems of Bollobás and Scott.
so: J. Comb. Theory, Ser. B 100, No. 6, 631-649 (2010).
py: 2010
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: graph partition; judicious partition; Azuma-Hoeffding inequality
ci: 
li: doi:10.1016/j.jctb.2010.06.002
ab: Summary: Judicious partitioning problems on graphs and hypergraphs ask for
    partitions that optimize several quantities simultaneously. Let $G$ be
    a hypergraph with $m_i$ edges of size $i$ for $i= 1,2$. We show that
    for any integer $k\ge 1$, $V(G)$ admits a partition into $k$ sets each
    containing at most $m_1/k+ m_2/k^2+ o(m_2)$ edges, establishing a
    conjecture of Bollobás and Scott. We also prove that $V(G)$ admits a
    partition into $k\ge 3$ sets, each meeting at least $m_1/k+ m_2/(k- 1)+
    o(m_2)$ edges, which, for large graphs, implies a conjecture of
    Bollobás and Scott (the conjecture is for all graphs). For $k=2$, we
    prove that $V(G)$ admits a partition into two sets each meeting at
    least $m_1/2+ 3m_2/4+o(m_2)$ edges, which solves a special case of a
    more general problem of Bollobás and Scott.
rv: