En populär metod i kombinatorisk optimering är att uttrycka polytoper P, som potentiellt kan ha exponentiellt många facetter, som lösningar av linjära program som använder några extra variabler för att minska antalet begränsningar ner till ett polynom. Efter två decenniers stillestånd har de senaste åren medfört fantastiska framsteg när det gäller att visa lägre gränser för den så kallade förlängningskomplexiteten, som för en polytop P betecknar det minsta antal ojämlikheter som krävs för att beskriva en högredimensionell polytop Q som linjärt kan projiceras på P. Den centrala frågan inom detta område förblev dock vidöppen: kan den perfekta matchande polytopen skrivas som en LP med polynomiskt många begränsningar? Vi besvarar denna fråga negativt. I själva verket är utvidgningen komplexiteten i den perfekta matchande polytop i en komplett n-node graf 2  på (n). Genom en känd minskning, förbättrar detta också den lägre gränsen på förlängning komplexiteten för TSP polytope från 2  på ( n) till 2 på (n).
Rothvoß visade en exponentiell lägre gräns på storleken på utökade formuleringar för Matching problem REF.
The Matching Polytope has Exponential Extension Complexity
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}