More Like this

1. Ehrhart theory of paving and panhandle matroids

   https://doi.org/10.1515/advgeom-2023-0020  

   Hanely, Derek; Martin, Jeremy L.; McGinnis, Daniel; Miyata, Dane; Nasr, George D.; Vindas-Meléndez, Andrés R.; Yin, Mei (October 2023, Advances in Geometry)

   Abstract We show that the base polytopeP_Mof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofP_M, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. 

   more » « less
2. Supersolvable posets and fiber-type abelian arrangements

   https://doi.org/10.1007/s00029-024-00976-w  

   Bibby, Christin; Delucchi, Emanuele (November 2024, Selecta Mathematica)

   Abstract We present a combinatorial analysis of fiber bundles of generalized configuration spaces on connected abelian Lie groups. These bundles are akin to those of Fadell–Neuwirth for configuration spaces, and their existence is detected by a combinatorial property of an associated finite partially ordered set. This is consistent with Terao’s fibration theorem connecting bundles of hyperplane arrangements to Stanley’s lattice supersolvability. We obtain a combinatorially determined class of $K(\pi ,1)$toric and elliptic arrangements. Under a stronger combinatorial condition, we prove a factorization of the Poincaré polynomial when the Lie group is noncompact. In the case of toric arrangements, this provides an analogue of Falk–Randell’s formula relating the Poincaré polynomial to the lower central series of the fundamental group. 

   more » « less
3. Stabbing Planes

   https://doi.org/10.48550/arXiv.1710.03219  

   Beame, Paul; Fleming, Noah; Impagliazzo, Russell; Pankratov, Denis; Pitassi, Toniann; Robere, Robert (May 2022, ArXivorg)

   We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based modern SAT solvers. As with DPLL there is only a single rule: the current polytope can be subdivided by branching on an inequality and its “integer negation.” That is, we can (non-deterministically choose) a hyperplane ax ≥ b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying ax ≥ b, the points satisfying ax ≤ b, and the middle slab b − 1 < ax < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show that Stabbing Planes can efficiently simulate the Cutting Planes proof system, and is equivalent to a tree-like variant of the R(CP) system of Krajicek [54]. As well, we show that it possesses short proofs of the canonical family of systems of F_2-linear equations known as the Tseitin formulas. Finally, we prove linear lower bounds on the rank of Stabbing Planes refutations by adapting lower bounds in communication complexity and use these bounds in order to show that Stabbing Planes proofs cannot be balanced. 

   more » « less
4. Expansion of random 0/1 polytopes

   https://doi.org/10.1002/rsa.21184  

   Leroux, Brett; Rademacher, Luis (March 2024, Random Structures & Algorithms)

   Abstract A conjecture of Milena Mihail and Umesh Vazirani (Proc. 24th Annu. ACM Symp. Theory Comput., ACM, Victoria, BC, 1992, pp. 26–38.) states that the edge expansion of the graph of every polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a polytope in is greater than one over some polynomial function of . This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of arandompolytope in is at least with high probability. 

   more » « less
5. Fast Algorithms for Geometric Consensuses

   Har-Peled, Sariel; Jones, Mitchell (June 2020, 36th International Symposium on Computational Geometry, SoCG 2020)

   Cabello, Sergio; Chen, Danny (Ed.)

   Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others. 

   more » « less