Idealness of k-wise Intersecting Families

Ahmad Abdi, Gérard Cornuéjols, Tony Huynh, Dabeen Lee

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

5 Citations (Scopus)

Abstract

A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that every 4-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it in the binary case. 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.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Subtitle of host publication21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020; London; United Kingdom; 8 June 2020 through 10 June 2020
EditorsDaniel Bienstock, Giacomo Zambelli
Place of PublicationCham Switzerland
PublisherSpringer-Praxis
Pages1-12
Number of pages12
Volume12125
ISBN (Print)9783030457709
DOIs
Publication statusPublished - 1 Jan 2020
EventInternational Conference on Integer Programming and Combinatorial Optimization, 2020 - Online, London, United Kingdom
Duration: 8 Jun 202010 Jun 2020
Conference number: 21st
https://www.lse.ac.uk/IPCO-2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integer Programming and Combinatorial Optimization, 2020
Abbreviated titleIPCO 2020
Country/TerritoryUnited Kingdom
CityLondon
Period8/06/2010/06/20
OtherThe 21st Conference on Integer Programming and Combinatorial Optimization (IPCO XXI) took place online on June 8-10. The conference was preceded by an online Summer School on June 6-7. The conference and summer school were organised by the Department of Mathematics at the London School of Economics.

IPCO conference is under the auspices of the Mathematical Optimization Society. It is held every year. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas.
Internet address

Cite this