Clean tangled clutters, simplices, and projective geometries

DOI10.1016/J.JCTB.2021.12.006zbMATH Open1483.05018arXiv1908.10629OpenAlexW3045990241MaRDI QIDQ2668014FDOQ2668014

Authors: Ahmad Abdi, Matt Superdock, Gérard Cornuéjols 

Publication date: 3 March 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A clutter is emph{clean} if it has no delta or the blocker of an extended odd hole minor, and it is emph{tangled} if its covering number is two and every element appears in a minimum cover. Clean tangled clutters have been instrumental in progress towards several open problems on ideal clutters, including the $au=2$ Conjecture. Let $mathcalC$ be a clean tangled clutter. It was recently proved that $mathcalC$ has a fractional packing of value two. Collecting the supports of all such fractional packings, we obtain what is called the {it core} of $mathcalC$. The core is a duplication of the cuboid of a set of $0-1$ points, called the {it setcore} of $mathcalC$. In this paper, we prove three results about the setcore. First, the convex hull of the setcore is a full-dimensional polytope containing the center point of the hypercube in its interior. Secondly, this polytope is a simplex if, and only if, the setcore is the cocycle space of a projective geometry over the two-element field. Finally, if this polytope is a simplex of dimension more than three, then $mathcalC$ has the clutter of the lines of the Fano plane as a minor. Our results expose a fascinating interplay between the combinatorics and the geometry of clean tangled clutters.

Full work available at URL: https://arxiv.org/abs/1908.10629

Recommendations

• Delta minors, delta free clutters, and entanglement
• On ideal minimally non-packing clutters
• Clean clutters and dyadic fractional packings
• Ideal clutters
• Intersecting restrictions in clutters

zbMATH Keywords

simplicesodd holescluttersideal cluttersdegenerate projective planesprojective geometries over the two-element field

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of simplicial complexes (05E45) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Cuboids, a class of clutters
• Title not available (Why is that?)
• A Solution of the Shannon Switching Game
• Bottleneck extrema
• A class of simple games
• A Machine-Oriented Logic Based on the Resolution Principle
• The matroids with the max-flow min-cut property
• Ideal 0, 1 matrices
• Combinatorial optimization. Packing and covering
• The Forbidden Minors of Binary Clutters
• Title not available (Why is that?)
• On the width-length inequality
• Ideal clutters that do not pack
• The packing property.
• Identically self-blocking clutters
• Intersecting restrictions in clutters
• A new infinite class of ideal minimally non-packing clutters
• The minimally non-ideal binary clutters with a triangle
• Deltas, extended odd holes and their blockers
• Idealness of \(k\)-wise intersecting families

Cited In (5)

• Idealness of \(k\)-wise intersecting families
• Delta minors, delta free clutters, and entanglement
• Correction to: ``Idealness of \(k\)-wise intersecting families
• Idealness of \(k\)-wise intersecting families
• Clean clutters and dyadic fractional packings

Uses Software

• cuboids-code

This page was built for publication: Clean tangled clutters, simplices, and projective geometries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668014)