×

On a bottleneck bipartition conjecture of Erdős. (English) Zbl 0767.05059

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)}\).

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
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.