skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √ log n
We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√log n) on inputs with n vertices.  more » « less
Award ID(s):
1612061
PAR ID:
10054912
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017
Page Range / eLocation ID:
564 to 575
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough. 
    more » « less
  2. Abstract In this paper, we introduce a novel method for deriving higher order corrections to the mean-field description of the dynamics of interacting bosons. More precisely, we consider the dynamics of N $$d$$ d -dimensional bosons for large N . The bosons initially form a Bose–Einstein condensate and interact with each other via a pair potential of the form $$(N-1)^{-1}N^{d\beta }v(N^\beta \cdot )$$ ( N - 1 ) - 1 N d β v ( N β · ) for $$\beta \in [0,\frac{1}{4d})$$ β ∈ [ 0 , 1 4 d ) . We derive a sequence of N -body functions which approximate the true many-body dynamics in $$L^2({\mathbb {R}}^{dN})$$ L 2 ( R dN ) -norm to arbitrary precision in powers of $$N^{-1}$$ N - 1 . The approximating functions are constructed as Duhamel expansions of finite order in terms of the first quantised analogue of a Bogoliubov time evolution. 
    more » « less
  3. This data package contains bird abundance data collected in plots that have had various plant functional groups or species experimentally removed at the Jornada Basin LTER site in southern New Mexico, USA. This data was collected in an effort to distinguish the differential effects of plant community biomass, plant community functional groups, and biodiversity within functional groups on plant community function, including effects on animals. To make these distinctions, treatments were established by the selective removal of plant species or functional groups within experimental plots. There are eight treatments: control (C, no removals); four functional group removal treatments (PG, perennial grass removed; S, shrubs removed; SSh, subshrubs removed; Succ, succulents removed), and three species richness manipulation treatments. Richness manipulations included a simplified treatment (Simp), where only the single most abundant species of each growth form is preserved and all other species in the growth form are removed, a reduced‐Larrea treatment (rL), where the Larrea is assumed to be the dominant and is removed while minority components remain, and a reduced-Prosopsis treatment (rP), where Prosopis rather than Larrea is removed as the shrub dominant. Following treatments, bird abundance and habitat preference data was collected in 1997. This data set consists of plot number, treatment type, and time of bird presence by taxa and by habitat and behavior. This study is complete. 
    more » « less
  4. Let s ( n ) = ∑ d ∣ n ,   d > n d s(n)=\sum _{d\mid n,~d>n} d denote the sum of the proper divisors of n n . The second-named author proved that ω ( s ( n ) ) \omega (s(n)) has normal order log ⁡ log ⁡ n \log \log {n} , the analogue for s s -values of a classical result of Hardy and Ramanujan [ The normal number of prime factors of a number n [Quart. J. Math. 48 (1917), 76–92], AMS Chelsea Publ., Providence, RI, 2000, pp. 262–275]. We establish the corresponding Erdős–Kac theorem: ω ( s ( n ) ) \omega (s(n)) is asymptotically normally distributed with mean and variance log ⁡ log ⁡ n \log \log {n} . The same method applies with s ( n ) s(n) replaced by any of several other unconventional arithmetic functions, such as β ( n ) ≔ ∑ p ∣ n p \beta (n)≔\sum _{p\mid n} p , n − φ ( n ) n-\varphi (n) , and n + τ ( n ) n+\tau (n) ( τ \tau being the divisor function). 
    more » « less
  5. We consider minimizing harmonic maps u u from Ω<#comment/> ⊂<#comment/> R n \Omega \subset \mathbb {R}^n into a closed Riemannian manifold N \mathcal {N} and prove: 1. an extension to n ≥<#comment/> 4 n \geq 4 of Almgren and Lieb’s linear law. That is, if the fundamental group of the target manifold N \mathcal {N} is finite, we have\[ H n −<#comment/> 3 ( sing ⁡<#comment/> u ) ≤<#comment/> C ∫<#comment/> ∂<#comment/> Ω<#comment/> | ∇<#comment/> T u | n −<#comment/> 1 d H n −<#comment/> 1 ; \mathcal {H}^{n-3}(\operatorname {sing} u) \le C \int _{\partial \Omega } |\nabla _T u|^{n-1} \,\mathrm {d}\mathcal {H}^{n-1}; \]2. an extension of Hardt and Lin’s stability theorem. Namely, assuming that the target manifold is N = S 2 \mathcal {N}=\mathbb {S}^2 we obtain that the singular set of u u is stable under small W 1 , n −<#comment/> 1 W^{1,n-1} -perturbations of the boundary data. In dimension n = 3 n=3 both results are shown to hold with weaker hypotheses, i.e., only assuming that the trace of our map lies in the fractional space W s , p W^{s,p} with s ∈<#comment/> ( 1 2 , 1 ] s \in (\frac {1}{2},1] and p ∈<#comment/> [ 2 , ∞<#comment/> ) p \in [2,\infty ) satisfying s p ≥<#comment/> 2 sp \geq 2 . We also discuss sharpness. 
    more » « less