Porter, T. D. On a bottleneck bipartition conjecture of Erdős. (English) Zbl 0767.05059 Combinatorica 12, No. 3, 317-321 (1992). 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)}\). Reviewer: T.D.Porter (Carbondale) Cited in 2 ReviewsCited in 19 Documents MSC: 05C35 Extremal problems in graph theory Keywords:conjecture of Erdős; minimax; discrepancy; bipartition; max-cut PDFBibTeX XMLCite \textit{T. D. Porter}, Combinatorica 12, No. 3, 317--321 (1992; Zbl 0767.05059) Full Text: DOI References: [1] L. Clark, F. Shahrokhi, andL. A. Sz?kely: A Lineartime Algorithm For Graph Partition Problems, to appear inInform. Proc. Letters. [2] R. Entringer: Personal communication. [3] P. Erd?s: Personal communication. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.