Clean tangled clutters, simplices, and projective geometries

DOI10.1016/J.JCTB.2021.12.006MaRDI QIDQ2668014zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

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

Describes a project that uses

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)