2020/03/31 by Luis Ferroni
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Bounded function #Cardinality (data modeling) #Combinatorics #Computer science #Discrete mathematics #Graphic matroid #Hyperplane #Mathematics #Matroid #Matroid partitioning #Polytope #Rank (graph theory) #graph theory and CDMA systems #math.CO #msc:05B35 #msc:11B73 #msc:52B20
paper · pdf · doi:10.1007/s00454-021-00313-4
15 pages, 2 figures. To appear in Discrete and Computational Geometry
arxiv created 2021/03/23 · openalex publication_date 2021/06/15 · arxiv updated 2021/06/17 · openalex created_date 2021/06/22 · openalex updated_date 2026/08/05
Abstract We provide a formula for the Ehrhart polynomial of the connected matroid of size n and rank k with the least number of bases, also known as a minimal matroid . We prove that their polytopes are Ehrhart positive and h^* <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:math> -real-rooted (and hence unimodal). We prove that the operation of circuit-hyperplane relaxation relates minimal matroids and matroid polytopes subdivisions, and also preserves Ehrhart positivity. We state two conjectures: that indeed all matroids are h^* <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:math> -real-rooted, and that the coefficients of the Ehrhart polynomial of a connected matroid of fixed rank and cardinality are bounded by those of the corresponding minimal matroid and the corresponding uniform matroid.