1,2

Comments from Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 13 2008 (Start): This is also the decimal expansion of 2 log 2, a constant cited in Percus. Abstract: The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises.

It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds.

Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold.

An intriguing algorithmic consequence is that although the problem is NP-hard, we can find cutsizes that are asymptotically within a factor 1 of optimal -- and possibly even the optimum itself -- in polynomial time for typical instances near the phase transition. (End)

Equals 2*A002162 = sum_{n=1..infinity} binomial(2n,n)/(n*4^n) [D. H. Lehmer, Am. Math. Monthly 92 (1985) 449] [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 04 2009]

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 2.

Harry J. Smith, Table of n, a(n) for n=1,...,20000

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Allon G. Percus, Gabriel Istrate, Bruno Goncalves, Robert Z. Sumi and Stefan Boettcher, The Peculiar Phase Structure of Random Graph Bisection, Aug 11, 2008. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 13 2008]

log(4)=sum(k>=1, H(k)/2^k) where H(k) is the k-th harmonic number - Benoit Cloitre (benoit7848c(AT)orange.fr), Jun 15 2003

Equals 1-sum_{k=1..infinity} (-1)^k/A002378(k) = 1+2*sum_{k=0..infinity} 1/A069072(k) = 5/4-sum_{k=1..infinity} (-1)^k/A007531(k+2). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jan 23 2009]

1.386294361119890618834464242916353136151000268720510508241360018986787... [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), May 16 2009]

(PARI) { default(realprecision, 20080); x=log(4); for (n=1, 20000, d=floor(x); x=(x-d)*10; write("b016627.txt", n, " ", d)); } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), May 16 2009]

Cf. A016732 Continued fraction. [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), May 16 2009]

Sequence in context: A016624 A021263 A081803 this_sequence A019604 A106291 A137987

Adjacent sequences: A016624 A016625 A016626 this_sequence A016628 A016629 A016630

nonn,cons

N. J. A. Sloane (njas(AT)research.att.com).

Fixed my PARI program, had -n Harry J. Smith (hjsmithh(AT)sbcglobal.net), May 19 2009

ArXiv URL replaced by non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 23 2009