English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In an early paper, Immerman raised a proposal on developing model-theoretictechniques to prove lower bounds on ordered structures, which represents along-standing challenge in finite model theory. An iconic question standing forsuch a challenge is how many variables are needed to define $k$-Clique infirst-order logic on the class of finite ordered graphs? If $k$ variables arenecessary, as widely believed, it would imply that the bounded (or finite)variable hierarchy in first-order logic is strict on the class of finiteordered graphs. In 2008, Rossman made a breakthrough by establishing an optimalaverage-case lower bound on the size of constant-depth unbounded fan-incircuits computing $k$-Clique. In terms of logic, this means that it needsgreater than $\lfloor\frac{k} {4}\rfloor$ variables to describe the $k$-Cliqueproblem in first-order logic on the class of finite ordered graphs, even in thepresence of arbitrary arithmetic predicates. It follows, with an unpublishedresult of Immerman, that the bounded variable hierarchy in first-order logic isindeed strict. However, Rossman's methods come from circuit complexity and anovel notion of sensitivity by himself. And the challenge before finite modeltheory remains there. In this paper, we give an alternative proof for thestrictness of bounded variable hierarchy in $\fo$ using pure model-theoretictoolkit, and anwser the question completely for first-order logic, i.e.$k$-variables are indeed needed to describe $k$-Clique in this logic. Incontrast to Rossman's proof, our proof is purely constructive. Then we embedthe main structures into a pure arithmetic structure to show a similar resultwhere arbitrary arithmetic predicates are presented. Finally, we discuss itsapplication in circuit complexity.

k variables are needed to define k-Clique in first-order logic