PRISM · Graph Profiles via Invariants, Sums-of-squares and Moment methods

Lines connect the coordinator with its partners.

Project objective

Many questions in extremal graph theory boil down to simple trade-offs: if a graph has this many edges, how many triangles must it contain? Such trade-offs are captured by graph profiles, which describe which combinations of small patterns can occur in the same, much larger graph. Today, only a few profiles are known exactly, and the proofs rely on case-by-case tricks that do not generalize.Supported by the Marie Skłodowska-Curie Actions programme, PRISM will develop new ways to certify profile boundaries, i.e., to prove rigorously which combinations of small patterns are possible and which are not. It combines ideas from polynomial optimization, real algebraic geometry, representation theory, and combinatorics. We focus first on polynomial analogues, developing structure-exploiting optimization hierarchies for polynomials composed with invariants, and projections of (highly structured) polynomial matrix inequalities onto a few coordinates. Then, we integrate these methods into the flag algebra framework to attack graph profiles and provide a repeatable pathway for further cases.

Original text from CORDIS.

Participants

• UNIVERSITETET I TROMSOE - NORGES ARKTISKE UNIVERSITET · TromsoCoordinatorNorway
• UNIVERSITY OF WARWICK · COVENTRYUnited Kingdom

Links

• View on CORDIS
• DOI: 10.3030/101272610