Search

Let G n be a graph on n vertices and let w k (G n) denote the number of walks of length k in G n divided by n. Erdős and Simonovits conjectured that w k (G n) t ≥ w t (G n) k when k ≥ t and both t and k are odd. In 2018, Sağlam proved this conjecture. We give a new shorter proof of this result. [ABSTRACT FROM AUTHOR]

Quantum states are represented by positive semidefinite Hermitian operators with unit trace, known as density matrices. An important subset of quantum states is that of separable states, the complement of which is the subset of entangled states. We show that the problem of deciding whether a quantum state is entangled can be seen as a moment problem in real analysis. Only a small number of such moments are accessible experimentally, and so in practice the question of quantum entanglement of a many-body system (e.g, a system consisting of several atoms) can be reduced to a truncated moment problem. By considering quantum entanglement of n identical atoms we arrive at the truncated moment problem defined for symmetric measures over a product of n copies of unit balls in R d . We work with moments up to degree 2 only, since these are most readily available experimentally. We derive necessary and sufficient conditions for belonging to the moment cone, which can be expressed via a linear matrix inequality of size at most 2 d + 2 , which is independent of n. The linear matrix inequalities can be converted into a set of explicit semialgebraic inequalities giving necessary and sufficient conditions for membership in the moment cone, and show that the two conditions approach each other in the limit of large n. The inequalities are derived via considering the dual cone of nonnegative polynomials, and its sum-of-squares relaxation. We show that the sum-of-squares relaxation of the dual cone is asymptotically exact, and using symmetry reduction techniques (Blekherman and Riener: Symmetric nonnegative forms and sums of squares. arXiv:1205.3102, 2012; Gatermann and Parrilo: J Pure Appl Algebra 192(1–3):95–128. https://doi.org/10.1016/j.jpaa.2003.12.011, 2004), it can be written as a small linear matrix inequality of size at most 2 d + 2 , which is independent of n. For the cone of symmetric nonnegative polynomials with the relevant support we also prove an analogue of the half-degree principle for globally nonnegative symmetric polynomials (Riener: J Pure Appl Algebra 216(4): 850–856. https://doi.org/10.1016/j.jpaa.2011.08.012, 2012; Timofte: J Math Anal Appl 284(1):174–190. https://doi.org/10.1016/S0022-247X(03)00301-9, 2003). [ABSTRACT FROM AUTHOR]

While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices—we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP. In this paper, we formally attempt to compare the strength of the sparse SDP relaxation vis-à-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k -PSD closure, which is the cone of matrices where PSD-ness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k -PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n. Other than linear algebra techniques, we extensively use probabilistic methods to arrive at these bounds. One of the lower bounds is obtained by observing a connection between matrices in the k -PSD closure and matrices satisfying the restricted isometry property. [ABSTRACT FROM AUTHOR]

We study symmetric non-negative forms and their relationship with symmetric sums of squares. For a fixed number of variables n and degree 2d, symmetric non-negative forms and symmetric sums of squares form closed, convex cones in the vector space of n-variate symmetric forms of degree 2d. Using representation theory of the symmetric group we characterize both cones in a uniform way. Further, we investigate the asymptotic behavior when the degree 2d is fixed and the number of variables n grows. Here, we show that, in sharp contrast to the general case, the difference between symmetric non-negative forms and sums of squares does not grow arbitrarily large for any fixed degree 2d. We consider the case of symmetric quartic forms in more detail and give a complete characterization of quartic symmetric sums of squares. Furthermore, we show that in degree 4 the cones of non-negative symmetric forms and symmetric sums of squares approach the same limit, thus these two cones asymptotically become closer as the number of variables grows. We conjecture that this is true in arbitrary degree 2d. [ABSTRACT FROM AUTHOR]

Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to write it as a sum of squares. In this paper, we identify a simple condition under which a graph density expression cannot be a sum of squares. Using this result, we prove that the Blakley-Roy inequality does not have a sum of squares certificate when the path length is odd. We also show that the same Blakley-Roy inequalities cannot be certified by sums of squares using a multiplier of the form one plus a sum of squares. These results answer two questions raised by Lovász. Our main tool is used again to show that the smallest open case of Sidorenko's conjectured inequality cannot be certified by a sum of squares. Finally, we show that our setup is equivalent to existing frameworks by Razborov and Lovász-Szegedy, and thus our results hold in these settings too. [ABSTRACT FROM AUTHOR]

We study the limits of the cones of symmetric nonnegative polynomials and symmetric sums of squares, when expressed in power-mean or monomial-mean basis. These limits correspond to forms with stable expression in power-mean polynomials that are globally nonnegative (resp. sums of squares) regardless of the number of variables. We introduce partial symmetry reduction to describe the limit cone of symmetric sums of squares, and reprove a result of Blekherman and Riener (Discrete Comput Geom 65:1–36, 2020) that limits of symmetric nonnegative polynomials and sums of squares agree in degree 4. We use tropicalization of the dual cones, first considered in the context of comparing nonnegative polynomials and sums of squares in Blekherman et al. (Trans Am Math Soc 375(09):6281–6310, 2022), to show differences between cones of symmetric polynomials and sums of squares starting in degree 6, which disproves a conjecture of Blekherman and Riener (Discrete Comput Geom 65:1–36, 2020). For even symmetric nonnegative forms and sums of squares we show that the cones agree up to degree 8, and are different starting with degree 10. We also find, via tropicalization, explicit examples of symmetric forms that are nonnegative but not sums of squares in the limit. [ABSTRACT FROM AUTHOR]

The minimum number of observations such that the maximum likelihood estimator in a Gaussian graphical model exists with probability one is called the maximum likelihood threshold of the underlying graph G. The natural algebraic relaxation is the generic completion rank introduced by Uhler. We show that the maximum likelihood threshold and the generic completion rank behave in the same way under clique sums, which gives us large families of graphs on which these invariants coincide. On the other hand, we determine both invariants for complete bipartite graphs Km,n and show that for some choices of m and n the two parameters may be quite far apart. In particular, this gives the first examples of graphs on which the maximum likelihood threshold and the generic completion rank do not agree. [ABSTRACT FROM AUTHOR]

Let X be a finite set of points in $${\mathbb {R}}^n$$ . A polynomial p nonnegative on X can be written as a sum of squares of rational functions modulo the vanishing ideal I( X). From the point of view of applications, such as polynomial optimization, we are interested in rational function representations of small degree. We derive a general upper bound in terms of the Hilbert function of X, and we show that this upper bound is tight for the case of quadratic functions on the hypercube $$C=\{0,1\}^n$$ , a very well studied case in combinatorial optimization. Using the lower bounds for C we construct a family of globally nonnegative quartic polynomials, which are not sums of squares of rational functions of small degree. To our knowledge this is the first construction for Hilbert's 17th problem of a family of polynomials of bounded degree which need increasing degrees in rational function representations as the number of variables n goes to infinity. We note that representation theory of the symmetric group $$S_n$$ plays a crucial role in our proofs of the lower bounds. [ABSTRACT FROM AUTHOR]

We show that for several notions of rank including tensor rank, Waring rank, and generalized rank with respect to a projective variety, the maximum value of rank is at most twice the generic rank. We show that over the real numbers, the maximum value of the real rank is at most twice the smallest typical rank, which is equal to the (complex) generic rank. [ABSTRACT FROM AUTHOR]

We prove a conjecture of Comon and Ottaviani that typical real Waring ranks of bivariate forms of degree d take all integer values between $\lfloor \frac{d+2}{2}\rfloor$ and d. That is, we show that for all d and all $\lfloor \frac{d+2}{2}\rfloor \leq m \leq d$ there exists a bivariate form f such that f can be written as a linear combination of m dth powers of real linear forms and no fewer, and additionally all forms in an open neighborhood of f also possess this property. Equivalently we show that for all d and any $\lfloor \frac{d+2}{2}\rfloor \leq m \leq d$ there exists a symmetric real bivariate tensor t of order d such that t can be written as a linear combination of m symmetric real tensors of rank 1 and no fewer, and additionally all tensors in an open neighborhood of t also possess this property. [ABSTRACT FROM AUTHOR]

It is well known that significant metabolic change take place as cells are transformed from normal to malignant. This review focuses on the use of different bioinformatics tools in cancer metabolomics studies. The article begins by describing different metabolomics technologies and data generation techniques. Overview of the data pre-processing techniques is provided and multivariate data analysis techniques are discussed and illustrated with case studies, including principal component analysis, clustering techniques, self-organizing maps, partial least squares, and discriminant function analysis. Also included is a discussion of available software packages. [ABSTRACT FROM AUTHOR]