I detta arbete studeras k-clique-frågans dynamiska beskrivande komplexitet. Det visas att när kanter endast kan infogas kan k-clique underhållas av ett kvantifier-fritt uppdateringsprogram av arity k − 1, men det kan inte underhållas av ett kvantifier-fri uppdateringsprogram av arity k − 2 (även i närvaro av unary hjälpfunktioner). Detta etablerar en areity hierarki för graffrågor för kvantifier-fri uppdateringsprogram under tillägg. Beviset på den nedre gränsen använder övre och nedre gränser för Ramsey nummer.
K-clique-frågan kan underhållas under kantinsatser av ett kvantifier-fritt uppdateringsprogram av arity k − 1 men inte av arity k − 2 REF.
The Dynamic Descriptive Complexity of k-Clique
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}