5 papers
Algebras, graphs and thetas
Marcel K. de Carli Silva, Gabriel Coutinho, Chris Godsil +1
We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations…
Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on SDP
Nathan Benedetto Proença, Marcel K. de Carli Silva, Gabriel Coutinho
The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theo…
Strict Complementarity in MaxCut SDP
Marcel K. de Carli Silva, Levent Tunçel
The MaxCut SDP is one of the most well-known semidefinite programs, and it has many favorable properties. One of its nicest geometric/duality properties is the fact that the vertic…
Pointed Closed Convex Sets are the Intersection of All Rational Supporting Closed Halfspaces
Marcel K. de Carli Silva, Levent Tunçel
We prove that every pointed closed convex set in is the intersection of all the rational closed halfspaces that contain it. This generalizes a previous result by the…
A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations
Marcel K. de Carli Silva, Levent Tunçel
Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by li…