An official website of the United States government
Chudnovsky’s conjecture and the stable Harbourne–Huneke containment
We investigate containment statements between symbolic and ordinary powers and bounds on the Waldschmidt constant of defining ideals of points in projective spaces. We establish the stable Harbourne conjecture for the defining ideal of a general set of points. We also prove Chudnovsky’s Conjecture and the stable version of the Harbourne–Huneke containment conjectures for a general set of sufficiently many points.
more »
« less
- Award ID(s):
- 2140355
- PAR ID:
- 10330262
- Date Published:
- Journal Name:
- Transactions of the American Mathematical Society, Series B
- Volume:
- 9
- Issue:
- 12
- ISSN:
- 2330-0000
- Page Range / eLocation ID:
- 371 to 394
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract A linear principal minor polynomial or lpm polynomial is a linear combination of principal minors of a symmetric matrix. By restricting to the diagonal, lpm polynomials are in bijection with multiaffine polynomials. We show that this establishes a one-to-one correspondence between homogeneous multiaffine stable polynomials and PSD-stable lpm polynomials. This yields new construction techniques for hyperbolic polynomials and allows us to find an explicit degree 3 hyperbolic polynomial in six variables some of whose Rayleigh differences are not sums of squares. We further generalize the well-known Fisher–Hadamard and Koteljanskii inequalities from determinants to PSD-stable lpm polynomials. We investigate the relationship between the associated hyperbolicity cones and conjecture a relationship between the eigenvalues of a symmetric matrix and the values of certain lpm polynomials evaluated at that matrix. We refer to this relationship as spectral containment.more » « less
-
Building on previous work by the same authors, we show that certain ideals defining Gorenstein rings have expected resurgence and thus satisfy the stable Harbourne conjecture. In prime characteristic, we can take any radical ideal defining a Gorenstein ring in a regular ring, provided that its symbolic powers are given by saturations with the maximal ideal. Although this property is not suitable for reduction to characteristic p, we show that a similar result holds in equicharacteristic 0 under the additional hypothesis that the symbolic Rees algebra of I is Noetherian.more » « less
-
Given a finite point set P in the plane, a subset S⊆P is called an island in P if conv(S) ⋂ P = S . We say that S ⊂ P is a visible island if the points in S are pairwise visible and S is an island in P. The famous Big-line Big-clique Conjecture states that for any k ≥ 3 and l ≥ 4, there is an integer n = n(k, l ), such that every finite set of at least n points in the plane contains l collinear points or k pairwise visible points. In this paper, we show that this conjecture is false for visible islands, by replacing each point in a Horton set by a triple of collinear points. Hence, there are arbitrarily large finite point sets in the plane with no 4 collinear members and no visible island of size 13.more » « less
-
We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γ-stable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))-stable instances on graphs of maximum degree ∆, (k − 1)-stable instances on k-colorable graphs and (1 + ε)-stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the Sherali-Adams hierarchy. For general graphs, we give an algorithm for (εn)-stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a by-product of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a γ-certified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of γ-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of γ ≥ 1 (hence, such algorithms not only solve γ-stable instances optimally, but also have guarantees even on unstable instances). Here, we obtain ∆-certified algorithms for Independent Set on graphs of maximum degree ∆, and (1 + ε)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((∆+1)/3 + ε)-certified algorithm for Independent Set on graphs of maximum degree ∆ where all weights are equal to 1.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/btran/103
