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...
Autores principales: | , , , |
---|---|
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 |