The dynamic descriptive complexity of \(k\)-clique

DOI10.1016/j.ic.2017.04.005zbMath1376.68055arXiv1610.09089OpenAlexW2609634695MaRDI QIDQ2407083

Thomas Zeume

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.09089

zbMATH Keywords

Ramsey numbers\(k\)-cliquedynamic complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Descriptive complexity and finite models (68Q19)

Related Items

The dynamic complexity of acyclic hypergraph homomorphisms ⋮ Unnamed Item ⋮ Counting Triangles under Updates in Worst-Case Optimal Time ⋮ Dynamic complexity of expansion

Cites Work

• Unnamed Item
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• Deterministic FOIES are strictly weaker
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Incremental recomputation in local languages.
• Dynamic conjunctive queries
• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity theory revisited
• The Dynamic Descriptive Complexity of k-Clique
• The dynamic complexity of formal languages
• Partition relations for cardinal numbers
• Combinatorial Theorems on Classifications of Subsets of a Given Set