On a bottleneck bipartition conjecture of Erdős (Q1200279): Difference between revisions

This paper contains a solution to a conjecture of P. Erdős. In particular, for any graph \(G=\langle V,E\rangle\), let \((A,\overline A)\) be a bipartition of the vertex set \(F(G)\), and define \[ \gamma(G)=\min_{(A,\overline A)}\max\{e(A),e(\overline A)\}, \] where \(e(A)\) denotes the number of edges in the induced subgraph \(G[A]\). The paper mentions the computation of \(\gamma(G)\) has been shown to be NP- hard. P. Erdős conjectured (1988) that \({\gamma(G)\over e(G)}\leq{1\over 4}+o\left[{1\over\sqrt{e(G)}}\right]\). He recognized the second moment method fails. This paper shows using a non-constructive, non- probabilistic technique that \({\gamma(G)\over e(G)}\leq{1\over 4}\left[ 1+\sqrt{{2\over e(G)}}\right]\). Properties of the max-cut and its relation to \(\gamma\) are studied. An extension of the problem has been done recently by the author [Graph partitions, to appear in J. Comb. Math. Comb. Comput]. Let \((U_ 1,\dots,U_ s)\) be a partition of \(V(G)\) into \(s\)-classes. Define \[ \gamma_ s(G)=\min_{(U_ 1,\dots,U_ s)}\max\{e(U_ 1),\dots,e(U_ s)\} \] and define the maximum \(s\)-cut \(M_ s(G)\) as \[ M_ s(G)=\max_{(U_ 1,\dots,U_ s)}\left\{e(G)-\sum^ s_{i=1} e(U_ i)\right\}. \] The relation between \(M_ s\) and \(\gamma_ s\) is studied and the following is shown. For any graph \(G\), and all \(s=2^ k\), there is a partition of the vertex set of \(G\) into \(s\) sets \(U_ 1,\dots,U_ s\), so that both, \(e(U_ i)\leq{e(G)\over s^ 2}+\sqrt{{e(G)\over s}}\) for \(i=1,\dots,s\), and \(\sum^ s_{i=1} e(U_ i)\leq {e(G)\over s}\). Also, Bollobás and Scott (draft in progress) have recently shown, that for all \(s\), \(\gamma_ s(G)\leq {2e(G)\over s(s+1)}\).