Cargando…

Idealness of k-wise intersecting families

A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer [Formula: see text] , every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for [Formula: see text] for the cla...

Descripción completa

Detalles Bibliográficos
Autores principales: Abdi, Ahmad, Cornuéjols, Gérard, Huynh, Tony, Lee, Dabeen
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8907125/
https://www.ncbi.nlm.nih.gov/pubmed/35300154
http://dx.doi.org/10.1007/s10107-020-01587-x
_version_ 1784665565761110016
author Abdi, Ahmad
Cornuéjols, Gérard
Huynh, Tony
Lee, Dabeen
author_facet Abdi, Ahmad
Cornuéjols, Gérard
Huynh, Tony
Lee, Dabeen
author_sort Abdi, Ahmad
collection PubMed
description A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer [Formula: see text] , every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for [Formula: see text] for the class of binary clutters. Two key ingredients for our proof are Jaeger’s 8-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975. We also discuss connections to the chromatic number of a clutter, projective geometries over the two-element field, uniform cycle covers in graphs, and quarter-integral packings of value two in ideal clutters.
format Online
Article
Text
id pubmed-8907125
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher Springer Berlin Heidelberg
record_format MEDLINE/PubMed
spelling pubmed-89071252022-03-15 Idealness of k-wise intersecting families Abdi, Ahmad Cornuéjols, Gérard Huynh, Tony Lee, Dabeen Math Program Full Length Paper A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer [Formula: see text] , every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for [Formula: see text] for the class of binary clutters. Two key ingredients for our proof are Jaeger’s 8-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975. We also discuss connections to the chromatic number of a clutter, projective geometries over the two-element field, uniform cycle covers in graphs, and quarter-integral packings of value two in ideal clutters. Springer Berlin Heidelberg 2020-11-11 2022 /pmc/articles/PMC8907125/ /pubmed/35300154 http://dx.doi.org/10.1007/s10107-020-01587-x Text en © The Author(s) 2020 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Full Length Paper
Abdi, Ahmad
Cornuéjols, Gérard
Huynh, Tony
Lee, Dabeen
Idealness of k-wise intersecting families
title Idealness of k-wise intersecting families
title_full Idealness of k-wise intersecting families
title_fullStr Idealness of k-wise intersecting families
title_full_unstemmed Idealness of k-wise intersecting families
title_short Idealness of k-wise intersecting families
title_sort idealness of k-wise intersecting families
topic Full Length Paper
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8907125/
https://www.ncbi.nlm.nih.gov/pubmed/35300154
http://dx.doi.org/10.1007/s10107-020-01587-x
work_keys_str_mv AT abdiahmad idealnessofkwiseintersectingfamilies
AT cornuejolsgerard idealnessofkwiseintersectingfamilies
AT huynhtony idealnessofkwiseintersectingfamilies
AT leedabeen idealnessofkwiseintersectingfamilies