I've been working through Elements of Finite Model Theory (Leonid Libkin) and am stuck on exercise 3.4.

As in the title, the question asks "Using Ehrenfeucht-Fraïssé games, show that acyclicity of finite graphs is not FO-definable."

We know that a property over finite structures is inexpressible in FO iff for every $k$ there are two finite structures $\mathfrak{A, B}$ such that $\mathfrak{A}$ has said property but $\mathfrak{B}$ doesn't and the duplicator always has a winning strategy in $k$-round Ehrenfeucht-Fraïssé games.

My initial approach was to take $\mathfrak{A}$ to be a large enough cycle so that the spoiler cannot demonstrate its cyclicity. The issue is that, if $\mathfrak{B}$ is acyclic, then there is some vertex with in-degree equal to 0 (?) So for $k \geq 2$ the spoiler seems to have a winning strategy by choosing such a vertex in $\mathfrak{B}$ for the first round. Then when the duplicator responds with some $a \in \mathfrak{A}$ the spoiler can play the vertex in $\mathfrak{A}$ who has an edge pointing to $a$ which the duplicator is unable to replicate in $\mathfrak{B}$

Adding more structure to $\mathfrak{A}$ to try and work around this, I continue to run into similar problems.

This question seems to be asking the same thing (but without the restriction to finite graphs) but the answer seems to use two graphs which are both cyclic so I'm assuming I'm missing some critical understanding about the question/concept or they're working with a non-standard definition of cyclicity.


You are right that the question you link to uses a nonstandard definition of "cyclic": it requires that every vertex is contained in a cycle.

There is a deleted answer to that question using the normal definition of "cyclic" (by the same author as the later answer), which I quote here:

Consider the two following graphs: enter image description here Choose the number of rays, their lengths and the number of nodes on the circles to be very large w.r.t. $n$. Then you will not be able to distinguish between them in a game of length $n$. Of course this requires a proof...

  • $\begingroup$ Thanks! I realised the answerer had deleted a previous answer but didn't realise it was still visible somehow. This seems to work. $\endgroup$ – Dylan Aug 12 '18 at 16:11
  • $\begingroup$ @DylanB Deleted answers are visible to uses who have sufficient reputation (I believe it's 10,000). $\endgroup$ – Alex Kruckman Aug 12 '18 at 20:51
  • 1
    $\begingroup$ Do you really need such a large number of rays? It seems to me that $n$ would be sufficient. $\endgroup$ – Ibrahim Jun 26 at 14:02
  • $\begingroup$ Yes, I think $n$ rays is sufficient. Though I don't think taking everything to be 'very large' relative to $n$ makes the construction any more complicated and it slightly reduces the cognitive load required to verify the proof works. $\endgroup$ – Dylan Jun 27 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.