Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvátal rank. We determine the Chvátal rank of all known cutting planes and show that almost all of them have Chvátal rank 1. We observe that these inequalities have an associated hypergraph that is β-acyclic. Our second goal is to derive deeper cutting planes; to do so, we consider hypergraphs that admit β-cycles. We introduce a novel class of valid inequalities arising from odd β-cycles, that generally have Chvátal rank 2. These inequalities allow us to obtain the first characterization of the multilinear polytope for hypergraphs that contain β-cycles. Namely, we show that the multilinear polytope for cycle hypergraphs is given by the standard linearization inequalities, flower inequalities, and odd β-cycle inequalities. We also prove that odd β-cycle inequalities can be separated in linear time when the hypergraph is a cycle hypergraph. This shows that instances represented by cycle hypergraphs can be solved in polynomial time. Last, to test the strength of odd β-cycle inequalities, we perform numerical experiments that imply that they close a significant percentage of the integrality gap.
more »
« less
Tropicalization of graph profiles
A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its “combinatorial shadow”. We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities.
more »
« less
- Award ID(s):
- 1901950
- NSF-PAR ID:
- 10342024
- Date Published:
- Journal Name:
- Transactions of the American Mathematical Society
- ISSN:
- 0002-9947
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Let $K$ be a real closed field with a nontrivial non-archimedean absolute value. We study a refined version of the tropicalization map, which we call real tropicalization map, that takes into account the signs on $K$. We study images of semialgebraic subsets of $K^n$ under this map from a general point of view. For a semialgebraic set $S \subseteq K^n$ we define a space $S_r^{{\operatorname{an}}}$ called the real analytification, which we show to be homeomorphic to the inverse limit of all real tropicalizations of $S$. We prove a real analogue of the tropical fundamental theorem and show that the tropicalization of any semialgebraic set is described by tropicalization of finitely many inequalities, which are valid on the semialgebraic set. We also study the topological properties of real analytification and tropicalization. If $X$ is an algebraic variety, we show that $X_r^{{\operatorname{an}}}$ can be canonically embedded into the real spectrum $X_r$ of $X$, and we study its relation with the Berkovich analytification of $X$.
-
more » « less
Abstract We develop a convenient framework for characterizing multipartite entanglement in composite systems, based on relations between entropies of various subsystems. This continues the program initiated in [1], of using holography to effectively recast the geometric problem into an algebraic one. We prove that, for an arbitrary number of parties, our procedure identifies a finite set of entropic information quantities that we conveniently represent geometrically in the form of an arrangement of hyperplanes. This leads us to define the
holographic entropy arrangement , whose algebraic and combinatorial aspects we explore in detail. Using the framework, we derive three new information quantities for four parties, as well as a new infinite family for any number of parties. A natural construct from the arrangement is theholographic entropy polyhedron which captures holographic entropy inequalities describing the physically allowed region of entropy space. We illustrate how to obtain the polyhedron by winnowing down the arrangement through a sieve to pick out candidate sign‐definite information quantities. Comparing the polyhedron with the holographic entropy cone, we find perfect agreement for 4 parties and corroborating evidence for the conjectured 5‐party entropy cone. We work with explicit configurations in arbitrary (time‐dependent) states leading to both simple derivations and an intuitive picture of the entanglement pattern. -
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graph-constrained group testing. Graph-constrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology. The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graph-constrained group testing is near-optimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs. Finally, we provide empirical results which suggest that our connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.more » « less
-
Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks. In many of these applications, the underlying context is better modelled as a weighted hypergraph that keeps evolving with time. This motivates the problem of maintaining the densest subhypergraph of a weighted hypergraph in a dynamic setting, where the input keeps changing via a sequence of updates (hyperedge insertions/deletions). Previously, the only known algorithm for this problem was due to Hu et al. [19]. This algorithm worked only on unweighted hypergraphs, and had an approximation ratio of (1 +ϵ)r2 and an update time of O(poly(r, log n)), where r denotes the maximum rank of the input across all the updates. We obtain a new algorithm for this problem, which works even when the input hypergraph is weighted. Our algorithm has a significantly improved (near-optimal) approximation ratio of (1 +ϵ) that is independent of r, and a similar update time of O(poly(r, log n)). It is the first (1 +ϵ)-approximation algorithm even for the special case of weighted simple graphs. To complement our theoretical analysis, we perform experiments with our dynamic algorithm on large-scale, real-world data-sets. Our algorithm significantly outperforms the state of the art [19] both in terms of accuracy and efficiency.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/tran/8643
