The Grothendieck Constant of Random and Pseudo-Random Graphs
Discrete Optimization, 5 (2):
323 - 327 (2008)In Memory of George B. Dantzig.DOI: 10.1016/j.disopt.2006.06.004
Abstract
The Grothendieck constant of a graph G = ( V , E ) is the least constant K such that for every matrix A : V × V → R , max f : V → S | V | − 1 ∑ u , v ∈ E A ( u , v ) ⋅ 〈 f ( u ) , f ( v ) 〉 ≤ K max ϵ : V → − 1 , + 1 ∑ u , v ∈ E A ( u , v ) ⋅ ϵ ( u ) ϵ ( v ) . The investigation of this parameter, introduced in N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th \ACM\ STOC, \ACM\ Press, Baltimore, 2005, pp. 486–493 (Also: Invent. Math. 163 (2006) 499–522), is motivated by the algorithmic problem of maximizing the quadratic form ∑ u , v ∈ E A ( u , v ) ϵ ( u ) ϵ ( v ) over all ϵ : V → − 1 , 1 , which arises in the study of correlation clustering and in the investigation of the spin glass model. In the present note we show that for the random graph G ( n , p ) the value of this parameter is, almost surely, Θ ( log ( n p ) ) . This settles a problem raised in N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th \ACM\ STOC, \ACM\ Press, Baltimore, 2005, pp. 486–493 (Also: Invent. Math. 163 (2006) 499–522). We also obtain a similar estimate for regular graphs in which the absolute value of each nontrivial eigenvalue is small.
Links and resources
Tags
community
@ytyoun's tags highlighted