Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Norway

Marie Skłodowska-Curie Action · Running

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

Coordinator
Universitetet I Tromsoe - Norges Arktiske Universitet, Norway
Runs
1 September 2026 to 31 August 2028
Status
Running
EU funding
€252k
Total cost
—
Partners
2 organisations in 2 countries
Type
Marie Skłodowska-Curie Action
Grant agreement
101272610

What the project is doing

In the project's own words, from its summary on CORDIS.

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.

Topics

Who is involved

OrganisationCityCountryRole
Universitetet I Tromsoe - Norges Arktiske UniversitetTromsoNorwayCoordinator
University of WarwickCoventryUnited KingdomAssociatedpartner

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI