Search

The moduli space of $n$ chains in the plane with generic side lengths that terminate on a fixed line is a smooth, closed manifold of dimension $n-1$. This manifold is also equipped with a locally standard action of $\mathbb{Z}_2^{n-1}$. The orbit space of this action is a simple polytope called the moment polytope. Interestingly, this manifold is also the fixed point set of an involution on a toric manifold known as the abelian polygon space. In this article we show that the moment polytope of the moduli space of chains is completely characterized by the combinatorial data, called the \emph{short code} of the length vector. We also classify aspherical chain spaces using a result of Davis, Januszkiewicz and Scott., Comment: 20 pages, 6 figures. Version 2: misprints and typos fixed, Section 2 shortened, calculations of characteristic functions added. Final version, will appear in Topology and its Applications

An integer vector $b \in \mathbb{Z}^d$ is a degree sequence if there exists a hypergraph with vertices $\{1,\dots,d\}$ such that each $b_i$ is the number of hyperedges containing $i$. The degree-sequence polytope $\mathscr{Z}^d$ is the convex hull of all degree sequences. We show that all but a $2^{-\Omega(d)}$ fraction of integer vectors in the degree sequence polytope are degree sequences. Furthermore, the corresponding hypergraph of these points can be computed in time $2^{O(d)}$ via linear programming techniques. This is substantially faster than the $2^{O(d^2)}$ running time of the current-best algorithm for the degree-sequence problem. We also show that for $d\geq 98$, the degree-sequence polytope $\mathscr{Z}^d$ contains integer points that are not degree sequences. Furthermore, we prove that the linear optimization problem over $\mathscr{Z}^d$ is $\mathrm{NP}$-hard. This complements a recent result of Deza et al. (2018) who provide an algorithm that is polynomial in $d$ and the number of hyperedges., Comment: 14 pages

We propose a unified perspective on two sets of objects that usually arise in the study of bipartite field theories. Each of the sets consists of a polytope, or equivalently a toric Calabi-Yau, and a quiver theory. We refer to the two sets of objects as original and twin. In the simplest cases, the two sides of the correspondence are connected by the graph operation known as untwisting. The democratic treatment that we advocate raises new questions regarding the connections between these objects, some of which we explore. With this motivation in mind, we establish a correspondence between the mutations of the original polytope and the twin quiver. This leads us to propose that non-toric twin quivers are naturally associated to generalized toric polygons (GTPs) and we explore various aspects of this idea. Supporting evidence includes global symmetries, the ability of twin quivers to encode the generalized $s$-rule, and the connection between the mutations of polytopes and of configurations of webs of 5-branes suspended from 7-branes. We introduce three methods for constructing twin quivers for GTPs. We also investigate the connection between twin quivers obtained using different toric phases. Twin quivers provide a powerful new perspective on GTPs. The ideas presented in this paper may represent a step towards the generalization of brane tilings to GTPs., Comment: 51 pages, 42 figures. v2: typos corrected, references added

Volume computation for $d$-polytopes $\mathcal{P}$ is fundamental in mathematics. There are known volume computation algorithms, mostly based on triangulation or signed-decomposition of the polytope. We consider the cone $ \mathrm{cone}(\mathcal{P})$ over $\mathcal{P}$ in view of Ehrhart theory. By using technique from algebraic combinatorics, we obtain an algorithm using only signed simplicial cone decompositions of $ \mathrm{cone}(\mathcal{P})$. Each cone is associated with a simple algebraic volume formula. Summing them gives the volume of the polytope. Our volume formula applies to various kind of cases. In particular, we use it to explain the traditional triangulation method and Lawrence's signed decomposition method., Comment: 23 pages, 2 figures

Let ${\rm sk}({\mathcal P})$ denote the $1$-skeleton of an convex polytope ${\mathcal P}$. Let $C$ be a clique (=complete subgraph) of ${\rm sk}({\mathcal P})$ and ${\rm conv}(C)$ the convex hull of the vertices of ${\mathcal P}$ belonging to $C$. In general, ${\rm conv}(C)$ may not be a face of ${\mathcal P}$. It will be proved that ${\rm conv}(C)$ is a face of ${\mathcal P}$ if ${\mathcal P}$ is either the order polytope ${\mathcal O}(P)$ of a finite partially ordered set $P$ or the stable set polytope ${\rm Stab}(G)$ of a finite simple graph $G$. In other words, when ${\mathcal P}$ is either ${\mathcal O}(P)$ or ${\rm Stab}(G)$, the simplicial complex consisting of simplices which are faces of ${\mathcal P}$ is the clique complex of ${\rm sk}({\mathcal P})$.

The collection of all $n$-point metric spaces of diameter $\le 1$ constitutes a polytope $\mathcal{M}_n \subset \mathbb{R}^{\binom{n}{2}}$, called the \emph{Metric Polytope}. In this paper, we consider the best approximations of $\mathcal{M}_n$ by ellipsoids. We give an exact explicit description of the largest volume ellipsoid contained in $\mathcal{M}_n$. When inflated by a factor of $Θ(n)$, this ellipsoid contains $\mathcal{M}_n$. It also turns out that the least volume ellipsoid containing $\mathcal{M}_n$ is a ball. When shrunk by a factor of $Θ(n)$, the resulting ball is contained in $\mathcal{M}_n$. We note that the general theorems on such ellipsoid posit only that the pertinent inflation/shrinkage factors can be made as small as $O(n^2)$., 17 pages

In this paper, we study the connected blocks polytope, which, apart from its own merits, can be seen as the generalization of certain connectivity based or Eulerian subgraph polytopes. We provide a complete facet description of this polytope, characterize its edges and show that it is Hirsch. We also show that connected blocks polytopes admit a regular unimodular triangulation by constructing a squarefree Gr\"obner basis. In addition, we prove that the polytope is Gorenstein of index $2$ and that its $h^\ast$-vector is unimodal.

In 1999, Pitman and Stanley introduced the polytope bearing their name along with a study of its faces, lattice points, and volume. The Pitman-Stanley polytope is well-studied due to its connections to probability, parking functions, the generalized permutahedra, and flow polytopes. Its lattice points correspond to plane partitions of skew shape with entries 0 and 1. Pitman and Stanley remarked that their polytope can be generalized so that lattice points correspond to plane partitions of skew shape with entries $0,1, \ldots , m$. Since then, this generalization has been untouched. We study this generalization and show that it can also be realized as a flow polytope of a grid graph. We give multiple characterizations of its vertices in terms of plane partitions of skew shape and integer flows. For a fixed skew shape, we show that the number of vertices of this polytope is a polynomial in $m$ whose leading term, in certain cases, counts standard Young tableaux of a skew shifted shape. Moreover, we give formulas for the number of faces, as well as generating functions for the number of vertices., Comment: 32 pages + appendix, 21 figures, 3 tables

For many statistical experiments, there exists a multitude of optimal designs. If we consider models with uncorrelated observations and adopt the approach of approximate experimental design, the set of all optimal designs typically forms a multivariate polytope. In this paper, we mathematically characterize the polytope of optimal designs. In particular, we show that its vertices correspond to the so-called minimal optimum designs. Consequently, we compute the vertices for several classical multifactor regression models of the first and the second degree. To this end, we use software tools based on rational arithmetic; therefore, the computed list is accurate and complete. The polytope of optimal experimental designs, and its vertices, can be applied in several ways. For instance, it can aid in constructing cost-efficient and efficient exact designs.

The purpose of this paper is twofold. We investigate a simple necessary condition, called the rhombus criterion, for two vertices in a polytope not to form an edge and show that in many examples of $0/1$-polytopes it is also sufficient. We explain how also when this is not the case, the criterion can give a good algorithm for determining the edges of high-dimenional polytopes. In particular we study the Chordal graph polytope, which arises in the theory of causality and is an important example of a characteristic imset polytope. We prove that, asymptotically, for almost all pairs of vertices the rhombus criterion holds. We conjecture it to hold for all pairs of vertices.

We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height of the integers and certain subdeterminants of the constraint matrix, which in some cases improves previously known results. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure $1-o(1)$ and polynomial diameter. Both bounds rely on spectral gaps -- of a certain Schr\"odinger operator in the first case, and a certain continuous time Markov chain in the second -- which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables., Comment: Refined the statement + proof of Theorem 1.1, comparison with related work. Fixed some minor mistakes, added references

Let $\mu$ be a probability distribution on $\mathbb{R}^d$ which assigns measure zero to every hyperplane and $S$ a set of points sampled independently from $\mu$. What can be said about the expected combinatorial structure of the convex hull of $S$? These polytopes are simplicial with probability one, but not much else is known except when more restrictive assumptions are imposed on $\mu$. In this paper we show that, with probability close to one, the convex hull of $S$ has a high degree of neighborliness no matter the underlying distribution $\mu$ as long as $n$ is not much bigger than $d$. As a concrete example, our result implies that if for each $d$ in $\mathbb{N}$ we choose a probability distribution $\mu_d$ on $\mathbb{R}^d$ which assigns measure zero to every hyperplane and then set $P_n$ to be the convex hull of an i.i.d. sample of $n \le 5d/4$ random points from $\mu_d$, the probability that $P_n$ is $k$-neighborly approaches one as $d \to \infty$ for all $k\le d/20$. We also give a simple example of a family of distributions which essentially attain our lower bound on the $k$-neighborliness of a random polytope.

Our study focuses on determining the best weight windows for a weighted moving average smoother under squared loss. We show that there exists an optimal weight window that is symmetrical around its center. We study the class of tapered weight windows, which decrease in weight as they move away from the center. We formulate the corresponding least squares problem as a quadratic program and finally as a projection of the origin onto a convex polytope. Additionally, we provide some analytical solutions to the best window when some conditions are met on the input data., Comment: arXiv admin note: substantial text overlap with arXiv:2203.02997

We investigate the properties of a family of polytopes that naturally arise in connection with a problem in distributed data storage, namely service rate region polytopes. The service rate region of a distributed coded system describes the data access requests that the underlying system can support. In this paper, we study the polytope structure of the service rate region with the primary goal of describing its geometric shape and properties. We achieve so by introducing various structural parameters of the service rate region and establishing upper and lower bounds for them. The techniques we apply in this paper range from coding theory to optimization. One of our main results shows that every rational point of the service rate region has a so-called rational allocation, answering an open question in the research area.

Every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. From the resulting directed graph one can define a notion of $f$-arborescence and $f$-monotone path on $P$, as well as a natural graph structure on the vertex set of $f$-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets.

Neural networks are widely used as a model for classification in a large variety of tasks. Typically, a learnable transformation (i.e. the classifier) is placed at the end of such models returning a value for each class used for classification. This transformation plays an important role in determining how the generated features change during the learning process. In this work, we argue that this transformation not only can be fixed (i.e. set as non-trainable) with no loss of accuracy and with a reduction in memory usage, but it can also be used to learn stationary and maximally separated embeddings. We show that the stationarity of the embedding and its maximal separated representation can be theoretically justified by setting the weights of the fixed classifier to values taken from the coordinate vertices of the three regular polytopes available in $\mathbb{R}^d$, namely: the $d$-Simplex, the $d$-Cube and the $d$-Orthoplex. These regular polytopes have the maximal amount of symmetry that can be exploited to generate stationary features angularly centered around their corresponding fixed weights. Our approach improves and broadens the concept of a fixed classifier, recently proposed in \cite{hoffer2018fix}, to a larger class of fixed classifier models. Experimental results confirm the theoretical analysis, the generalization capability, the faster convergence and the improved performance of the proposed method. Code will be publicly available., Comment: arXiv admin note: substantial text overlap with arXiv:1902.10441

The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances.

Data extraction algorithms on data hypercubes, or datacubes, are traditionally only capable of cutting boxes of data along the datacube axes. For many use cases however, this is not a sufficient approach and returns more data than users might actually need. This not only forces users to apply post-processing after extraction, but more importantly this consumes more I/O resources than is necessary. When considering very large datacubes from which users only want to extract small non-rectangular subsets, the box approach does not scale well. Indeed, with this traditional approach, I/O systems quickly reach capacity, trying to read and return unwanted data to users. In this paper, we propose a novel technique, based on computational geometry concepts, which instead carefully pre-selects the precise bytes of data which the user needs in order to then only read those from the datacube. As we discuss later on, this novel extraction method will considerably help scale access to large petabyte size data hypercubes in a variety of scientific fields., Comment: 10 pages, 13 figures

We determine the maximal hyperplane sections of the regular n-simplex, if the distance of the hyperplane to the centroid is fairly large, i.e. larger than the distance of the centroid to the midpoint of edges. Similar results for the n-cube and the l 1 n -ball were obtained by Moody, Stone, Zach and Zvavitch and by Liu and Tkocz. The maximal hyperplanes in these three cases are perpendicular to the vectors from the centroid to the vertices. For smaller distances -in a well-defined range- we show that these hyperplane sections are at least locally maximal. We also determine the hyperplane sections of the simplex, the cross-polytope and the cube which have maximal perimeter, i.e. maximal volume intersection with the boundary of the convex body.

Let P be a poset, O ( P ) the order polytope of P and C ( P ) the chain polytope of P. In this paper, we study the canonical ideal of the Ehrhart ring K [ C ( P ) ] of C ( P ) over a field K and characterize the level (resp. anticanonical level) property of K [ C ( P ) ] by a combinatorial structure of P. In particular, we show that if K [ C ( P ) ] is level (resp. anticanonical level), then so is K [ O ( P ) ] . We exhibit examples which show the converse does not hold. Moreover, we show that the symbolic powers of the canonical ideal of K [ C ( P ) ] are identical with ordinary ones and degrees of the generators of the canonical and anticanonical ideals are consecutive integers.

We study a certain polytope depending on a graph G and a parameter β ∈ (0,1) that arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Literature suggests a conjecture a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress toward a proof of the conjecture by proving results about the structure of feasible bases. In particular, we prove three main results: (1) the set of feasible bases is independent of the parameter β when the parameter is close to one, (2) the polytope can be interpreted as a generalized network flow polytope, and (3) we deduce a combinatorial interpretation of the feasible bases. We also provide a full characterization for a special class of feasible bases, and we apply this to provide some computational support for the conjecture.

The full root polytope of type $A$ is the convex hull of all pairwise differences of the standard basis vectors which we represent by forward and backward arrows. We completely classify all flag triangulations of this polytope that are uniform in the sense that the edges may be described as a function of the relative order of the indices of the four basis vectors involved. These fifteen triangulations fall naturally into three classes: three in the lex class, three in the revlex class and nine in the Simion class. We also consider a refined face count where we distinguish between forward and backward arrows. We prove the refined face counts only depend on the class of the triangulations. The refined face generating functions are expressed in terms of the Catalan and Delannoy generating functions and the modified Bessel function of the first kind., Comment: 42 pages, 7 figures and 4 tables

In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.

We prove a bijection between the triangulations of the 3-dimensional cyclic polytope C(n+2, 3) and persistent graphs with n vertices. We show that under this bijection the Stasheff-Tamari orders on triangulations naturally translate to subgraph inclusion between persistent graphs. Moreover, we describe a connection to the second higher Bruhat order B(n, 2). We additionally give an algorithm to efficiently enumerate all persistent graphs on n vertices and thus all triangulations of C(n+2, 3).

We study a lattice duality among families of K3 surfaces associated to coupling pairs that admit polytope duality with trivial toric contribution.

We present a simple and efficient acceleration technique for an arbitrary method for computing the Euclidean projection of a point onto a convex polytope, defined as the convex hull of a finite number of points, in the case when the number of points in the polytope is much greater than the dimension of the space. The technique consists in applying any given method to a "small" subpolytope of the original polytope and gradually shifting it, till the projection of the given point onto the subpolytope coincides with its projection onto the original polytope. The results of numerical experiments demonstrate the high efficiency of the proposed acceleration technique. In particular, they show that the reduction of computation time increases with an increase of the number of points in the polytope and is proportional to this number for some methods. In the second part of the paper, we also discuss a straightforward extension of the proposed acceleration technique to the case of arbitrary methods for computing the distance between two convex polytopes, defined as the convex hulls of finite sets of points., Comment: In the second version, a number of typos and small mistakes was corrected and a remark about the polynomial (in the number of points) complexity of the meta-algorithm was added

DP is a complexity class that is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis. In this paper, we will establish that, recognizing a facet for the knapsack polytope is DP-complete, as conjectured by Hartvigsen and Zemel in 1992. Moreover, we show that the recognition problem of a supporting hyperplane for the knapsack polytope and the exact knapsack problem are both DP-complete, and the membership problem of knapsack polytope is NP-complete.

We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs, hence, settling completely the extension complexity of the multilinear polytope of acyclic hypergraphs.

We study Newton polytopes of $F$-polynomials in a TSSS cluster algebra $\mathcal A$ and generalize them to a larger set consisting of polytopes $N_h$ for $h\in{\mathbb Z}^n$. The main contribution contains: (i) obtaining a recurrence construction of Laurent expression of a cluster variable in a cluster from its $g$-vector; (ii) proving the subset $\mathcal P$ of $\widehat{\mathcal P}$ consisting of Laurent polynomials in $\widehat{\mathcal P}$ is a strongly positive ${\mathbb Z}Trop(Y)$-basis for ${\mathcal U}({\mathcal A})$ consisting of certain universally indecomposable Laurent polynomials when $\mathcal A$ is a cluster algebra with principal coefficients. For a cluster algebra $\mathcal A$ over a semifield $\mathbb P$ in general, $\mathcal P$ is a strongly positive ${\mathbb Z}{\mathbb P}$-basis for a subalgebra ${\mathcal I}_{\mathcal P}({\mathcal A})}$ of ${\mathcal U}({\mathcal A})}$. We call $\mathcal P$ a polytope basis; (iii) constructing some explicit maps among $F$-polynomials, $g$-vectors, $d$-vectors and cluster variables to characterize their relationship. As applications of (i), we give an affirmation to positivity conjecture of cluster variables in a TSSS cluster algebra, which in particular provides a new method different from that given by Gross etc. to present the positivity of cluster variables in the skew-symmetrizable case. And, a conjecture on Newton polytopes posed by Fei is answered affirmatively. For (ii), we know in rank $2$ case, $\mathcal P$ coincides with the greedy basis introduced by Lee etc.. Hence, we can regard the polytope basis $\mathcal P$ as a natural generalization of the greedy basis in any rank. As application of (iii), the positivity of $d$-vectors associated to non-initial cluster variables, which was a conjecture raised, is proved in a TSSS cluster algebra., Comment: 68 pages

It is well known that the future thermal cone -- which is the set of all states thermomajorized by a given initial state -- forms a convex polytope in the quasi-classical realm, and that one can explicitly write down a map which relates the permutations to the extreme points of this polytope. Given any such extreme point we review a formula for a Gibbs-stochastic matrix that maps the initial state to said extremal state, and we uncover the simple underlying structure. This allows us to draw a connection to the theory of transportation polytopes, which leads to the notions of ``well-structured'' and ``stable'' Gibbs states. While the former relates to the number of extremal states being maximal, the latter characterizes when thermomajorization is a partial order in the quasi-classical realm; this corresponds to the impossibility of cyclic state transfers. Moreover, we give simple criteria for degeneracy of the polytope, that is, for checking whether the extreme point map maps two different permutations to the same state., Comment: 24+14 pages. Submitted to J. Math. Phys

We introduce a general class of symmetric polynomials that have saturated Newton polytope and their Newton polytope has integer decomposition property. The class covers numerous previously studied symmetric polynomials., Comment: 10 pages, 3 figures

Let $R$ be the Ehrhart ring of the stable set polytope of a cycle graph which is not Gorenstein. We describe the non-Gorenstein locus of $\mathrm{Spec} R$. Further, we show that $R$ is almost Gorenstein. Moreover, we show that the conjecture of Hibi and Tsuchiya is true., Comment: arXiv admin note: text overlap with arXiv:2201.02957, arXiv:2005.03259

We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the facial structure of multilinear polytopes, we propose novel linear programming relaxations for rank-one Boolean tensor factorization. To analyze the performance of the proposed linear programs, we consider a semi-random corruption model for the input tensor. We first consider the original NP-hard problem and establish necessary and sufficient conditions for the recovery of the ground truth with high probability. Next, we obtain sufficient conditions under which the proposed linear programming relaxations recover the ground truth with high probability. Our theoretical results as well as numerical simulations indicate that certain facets of the multilinear polytope significantly improve the recovery properties of linear programming relaxations for rank-one Boolean tensor factorization.

Chromatic symmetric functions are well-studied symmetric functions in algebraic combinatorics that generalize the chromatic polynomial and are related to Hessenberg varieties and diagonal harmonics. Motivated by the Stanley--Stembridge conjecture, we show that the allowable coloring weights for indifference graphs of Dyck paths are the lattice points of a permutahedron $\mathcal{P}_\lambda$, and we give a formula for the dominant weight $\lambda$. Furthermore, we conjecture that such chromatic symmetric functions are Lorentzian, a property introduced by Br\"and\'en and Huh as a bridge between discrete convex analysis and concavity properties in combinatorics, and we prove this conjecture for abelian Dyck paths. We extend our results on the Newton polytope to incomparability graphs of (3+1)-free posets, and we give a number of conjectures and results stemming from our work, including results on the complexity of computing the coefficients and relations with the $\zeta$ map from diagonal harmonics., Comment: 27 pages, 10 figures. v3: Updated references, updated figures to improve readability. Added footnote with update on proofs of Conj. 7.1. Revised definition of part listing representative in Theorem 5.3

The circumcenter of mass of a simplicial polytope $P$ is defined as follows: triangulate $P$, assign to each simplex its circumcenter taken with weight equal to the volume of the simplex, and then find the center of mass of the resulting system of point masses. The so obtained point is independent of the triangulation. The aim of the present note is to give a definition of the circumcenter of mass that does not rely on a triangulation. To do so we investigate how volumes of polytopes change under Möbius transformations., 4 pages

We present new results for online contention resolution schemes for the matching polytope of graphs, in the random-order (RCRS) and adversarial (OCRS) arrival models. Our results include improved selectability guarantees (i.e., lower bounds), as well as new impossibility results (i.e., upper bounds). By well-known reductions to the prophet (secretary) matching problem, a $c$-selectable OCRS (RCRS) implies a $c$-competitive algorithm for adversarial (random order) edge arrivals. Similar reductions are also known for the query-commit matching problem. For the adversarial arrival model, we present a new analysis of the OCRS of Ezra et al.~(EC, 2020). We show that this scheme is $0.344$-selectable for general graphs and $0.349$-selectable for bipartite graphs, improving on the previous $0.337$ selectability result for this algorithm. We also show that the selectability of this scheme cannot be greater than $0.361$ for general graphs and $0.382$ for bipartite graphs. We further show that no OCRS can achieve a selectability greater than $0.4$ for general graphs, and $0.433$ for bipartite graphs. For random-order arrivals, we present two attenuation-based schemes which use new attenuation functions. Our first RCRS is $0.474$-selectable for general graphs, and our second is $0.476$-selectable for bipartite graphs. These results improve upon the recent $0.45$ (and $0.456$) selectability results for general graphs (respectively, bipartite graphs) due to Pollner et al.~(EC, 2022). On general graphs, our 0.474-selectable RCRS provides the best known positive result even for offline contention resolution, and also for the correlation gap. We conclude by proving a fundamental upper bound of 0.5 on the selectability of RCRS, using bipartite graphs.

We study the application of the method of regions to Feynman integrals with massless propagators contributing to off-shell Green's functions in Minkowski spacetime (with non-exceptional momenta) around vanishing external masses, $p_i^2\to 0$. This on-shell expansion allows us to identify all infrared-sensitive regions at any power, in terms of infrared subgraphs in which a subset of the propagators become collinear to external lightlike momenta and others become soft. We show that each such region can be viewed as a solution to the Landau equations, or equivalently, as a facet in the Newton polytope constructed from the Symanzik graph polynomials. This identification allows us to study the properties of the graph polynomials associated with infrared regions, as well as to construct a graph-finding algorithm for the on-shell expansion, which identifies all regions using exclusively graph-theoretical conditions. We also use the results to investigate the analytic structure of integrals associated with regions in which every connected soft subgraph connects to just two jets. For such regions we prove that multiple on-shell expansions commute. This applies in particular to all regions in Sudakov form-factor diagrams as well as in any planar diagram., Comment: 73 pages, 16 figures

The (combinatorial) diameter of a polytope $P \subseteq \mathbb R^d$ is the maximum value of a shortest path between a pair of vertices on the 1-skeleton of $P$, that is the graph where the nodes are given by the $0$-dimensional faces of $P$, and the edges are given the 1-dimensional faces of $P$. The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, [Frieze and Teng, 1994] showed that computing the diameter of a polytope is (weakly) NP-hard. In this paper, we show that the problem of computing the diameter is strongly NP-hard even for a polytope with a very simple structure: namely, the \emph{fractional matching} polytope. We also show that computing a pair of vertices at maximum shortest path distance on the 1-skeleton of this polytope is an APX-hard problem. We prove these results by giving an \emph{exact characterization} of the diameter of the fractional matching polytope, that is of independent interest.

The first author showed that for a given point $p$ in an $nk$-polytope $P$ there are $n$ points in the $k$-faces of $P$, whose barycenter is $p$. We show that we can increase the dimension of $P$ by $r$, if we allow $r$ of the points to be in $(k+1)$-faces. While we can force points with a prescribed barycenter into faces of dimensions $k$ and $k+1$, we show that the gap in dimensions of these faces can never exceed one. We also investigate the weighted analogue of this question, where a convex combination with predetermined coefficients of $n$ points in $k$-faces of an $nk$-polytope is supposed to equal a given target point. While weights that are not all equal may be prescribed for certain values of $n$ and $k$, any coefficient vector that yields a point different from the barycenter cannot be prescribed for fixed $n$ and sufficiently large $k$., Comment: 6 pages

Popular approaches for Natural Language Understanding (NLU) usually rely on a huge amount of annotated data or handcrafted rules, which is laborious and not adaptive to domain extension. We recently proposed a Convex-Polytopic-Model-based framework that shows great potential in automatically extracting semantic patterns by exploiting the raw dialog corpus. The extracted semantic patterns can be used to generate semantic frames, which is essential in assisting NLU tasks. This paper further studies the CPM model in depth and visualizes its high interpretability and transparency at various levels. We show that this framework can exploit semantic-frame-related features in the corpus, reveal the underlying semantic structure of the utterances, and boost the performance of the state-of-the-art NLU model with minimal supervision. We conduct our experiments on the ATIS (Air Travel Information System) corpus.

Given a graph with edges colored red or blue and an integer $k$, the exact perfect matching problem asks if there exists a perfect matching with exactly $k$ red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this paper we show that there is no sub-exponential sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential sized linear program to describe the convex hull of perfect matchings with an odd number of red edges., Comment: SODA 2023

A weighted game or a threshold function in general admits different weighted representations even if the sum of non-negative weights is fixed to one. Here we study bounds for the diameter of the corresponding weight polytope. It turns out that the diameter can be upper bounded in terms of the maximum weight and the quota or threshold. We apply those results to approximation results between power distributions, given by power indices, and weights., Comment: 16 pages; typos corrected; arXiv admin note: text overlap with arXiv:1802.00497

We study the null set $N(\mathcal{P})$ of the Fourier-Laplace transform of a polytope $\mathcal{P} \subset \mathbb{R}^d$, and we find that $N(\mathcal{P})$ does not contain (almost all) circles in $\mathbb{R}^d$. As a consequence, the null set does not contain the algebraic varieties $\{z \in \mathbb{C}^d \mid z_1^2 + \dots + z_d^2 = \alpha^2\}$ for each fixed $\alpha \in \mathbb{C}$, and hence we get an explicit proof that the Pompeiu property is true for all polytopes. Our proof uses the Brion-Barvinok theorem, which gives a concrete formulation for the Fourier-Laplace transform of a polytope, and it also uses properties of Bessel functions. The original proof that polytopes (as well as other bodies) possess the Pompeiu property was given by Brown, Schreiber, and Taylor (1973) for dimension 2. Williams (1976) later observed that the same proof also works for $d>2$ and, using eigenvalues of the Laplacian, gave another proof valid for $d \geq 2$ that polytopes have the Pompeiu property.

A parallel server system is a stochastic processing network with applications in manufacturing, supply chain, ride-hailing, call centers, etc. Heterogeneous customers arrive in the system, and only a subset of servers can serve any customer type given by the flexibility graph. The goal of the system operator is to minimize the delay that depends on the scheduling policy and the flexibility graph. A long line of literature focuses on designing near-optimal scheduling policies given a flexibility graph. On the contrary, we fix the scheduling policy to be the so-called MaxWeight scheduling given its superior delay performance and focus on designing near-optimal, sparse flexibility graphs. Our contributions are threefold. First, we analyze the expected delay in the heavy-traffic asymptotic regime in terms of the properties of the flexibility graph and use this result to translate the design question in terms of transportation polytope, the deterministic equivalent of parallel server queues. Second, we design the sparsest flexibility graph that achieves a given delay performance and shows the robustness of the design to demand uncertainty. Third, given the budget to add edges arrives sequentially in time, we present the optimal schedule for adding them to the flexibility graph. These results are obtained by proving new results for transportation polytopes and are of independent interest. In particular, translating the difficulties to a simpler model, i.e. transportation polytope, allows us to develop a unified framework to answer several design questions., Comment: 56 pages, 10 Figures

We choose some special unit vectors $\boldsymbol{n}_1,\dots,\boldsymbol{n}_5$ in $\mathbb{R}^3$ and denote by $\mathscr{L}\subset\mathbb{R}^5$ the set of all points $(L_1,\dots,L_5)\in\mathbb{R}^5$ with the following property: there exists a compact convex polytope $P\subset\mathbb{R}^3$ such that the vectors $\boldsymbol{n}_1,\dots,\boldsymbol{n}_5$ (and no other vector) are unit outward normals to the faces of $P$ and the perimeter of the face with the outward normal $\boldsymbol{n}_k$ is equal to $L_k$ for all $k=1,\dots,5$. Our main result reads that $\mathscr{L}$ is not a locally-analytic set, i.\,e., we prove that, for some point $(L_1,\dots,L_5)\in\mathscr{L}$, it is not possible to find a neighborhood $U\subset\mathbb{R}^5$ and an analytic set $A\subset\mathbb{R}^5$ such that $\mathscr{L}\cap U=A\cap U$. We interpret this result as an obstacle for finding an existence theorem for a compact convex polytope with prescribed directions and perimeters of the faces., Comment: 9 pages, 3 figures. In version 2, some misprints are corrected

The Newton polytope related to a ``minimal" counterexample to the Jacobian conjecture is introduced and described. This description allows to obtain a sharper estimate for the geometric degree of the polynomial mapping given by a Jacobian pair and to give a new proof of the Abhyankar's two characteristic pair case.

By employing the ${\rm AdS}_3/{\rm CFT}_2$ correspondence in this note we observe an analogy between the structures found in connection with the Arkani-Hamed-Bai-He-Yan (ABHY) associahedron used for understanding scattering amplitudes, and the one used for understanding space-time emerging from patterns of entanglement. The analogy suggests the natural interpretation for the associahedron as a holographic entanglement polytope associated to the ${\rm CFT}_2$ vacuum. Our observations hint at the possibility that the factorization properties of scattering amplitudes are connected to the notion of separability of space-time as used in the theory of holographic quantum entanglement., 15 pages , 5 figures LaTeX

Given a graph $G=(V,E)$ and a set $S \subseteq \binom{V}{2}$ of terminal pairs, the minimum multicut problem asks for a minimum edge set $\delta \subseteq E$ such that there is no $s$-$t$-path in $G -\delta$ for any $\{s,t\}\in S$. For $|S|=1$ this is the well known $s$-$t$-cut problem, but in general the minimum multicut problem is NP-complete, even if the input graph is a tree. The multicut polytope $\text{MultC}^\square (G,S)$ is the convex hull of all multicuts in $G$; the multicut dominant is given by $\text{MultC}(G,S)=\text{MultC}^\square (G,S)+\mathbb{R}^E$. The latter is the relevant object for the minimization problem. While polyhedra associated to several cut problems have been studied intensively there is only little knowledge for multicut. We investigate properties of the multicut dominant and in particular derive results on liftings of facet-defining inequalities. This yields a classification of all facet-defining path- and edge inequalities. Moreover, we investigate the effect of graph operations such as node splitting, edge subdivisions, and edge contractions on the multicut-dominant and its facet-defining inequalities. In addition, we introduce facet-defining inequalities supported on stars, trees, and cycles and show that the former two can be separated in polynomial time when the input graph is a tree., Comment: 28 pages, 5 figures

The Birkhoff polytope $\mathcal{B}_d$ consisting of all bistochastic matrices of order $d$ assists researchers from many areas, including combinatorics, statistical physics and quantum information. Its subset $\mathcal{U}_d$ of unistochastic matrices, determined by squared moduli of unitary matrices, is of a particular importance for quantum theory as classical dynamical systems described by unistochastic transition matrices can be quantised. In order to investigate the problem of unistochasticity we introduce the set $\mathcal{L}_d$ of bracelet matrices that forms a subset of $\mathcal{B}_d$, but a superset of $\mathcal{U}_d$. We prove that for every dimension $d$ this set contains the set of factorisable bistochastic matrices $\mathcal{F}_d$ and is closed under matrix multiplication by elements of $\mathcal{F}_d$. Moreover, we prove that both $\mathcal{L}_d$ and $\mathcal{F}_d$ are star-shaped with respect to the flat matrix. We also analyse the set of $d\times d$ unistochastic matrices arising from circulant unitary matrices, and show that their spectra lie inside $d$-hypocycloids on the complex plane. Finally, applying our results to small dimensions, we fully characterise the set of circulant unistochastic matrices of order $d\leq 4$, and prove that such matrices form a monoid for $d=3$.