Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Select All
Limit to events tagged with one or more of:
Select All
Limit to events where the audience is one or more of:
Select All
Friday, April 25, 2025 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte colloquium-Ahmad Abdi

Title:Strongly connected orientations and integer lattices

Speaker: Ahmad Abdi
Affiliation: London School of Economics and Political Science
Location: MC 5501

Abstract: Let D = (V, A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper 'slanted' face F of P. We prove under a mild necessary condition that the 0,1 points in F contain an integral basis B, i.e., B is linearly independent, and every integral vector in the linear of span of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis.

Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say k, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any odd prime number p, a p-adic packing of dijoins of value k and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by the 0,1 points in F, where F is the face of P satisfying x(C) = 1 for every minimum dicut C.

This is based on joint work with Gerard Cornuejols, Siyue Liu, and Olha Silina.