We consider class of directed graphs (self edges (=loop) are allowed). The aim is: construct example of two graphs $G_1$ and $G_2$ such that:

  1. for each graph $H$ with $\le 7$ nodes $G_1$ contains induced subgraph isomorphic to $H$ only and only if $G_2$ contains induced subgraph isomorphic to $H$.
  2. Player $1$ (spojler) has winning strategy in Game with $7$ rounds.

To my eye, is is sufficient to give $K_8$ and $K_7$, but each node has loop (edge to self).

For the first point, we know that $K_8$ contains as subgraph $K_7$, so if $K_9$ has subgraph isomorphic to some $H=(V,_)$ such that $|V|\le 7$ so $K_8$ also.
If $K_8$ has subgraph isomorphic to some $H$ then we may say the same about $K_7$ because $H$ has at most $7$ nodes, we may close this $H$ in subgraph of $K_8$ which is simultatenously $K_7$.

For the second point. We know that in our $K_8$ each node has exactly $7$ distinct neighbours, however in $K_7$ each node has only $6$ distinct neighbours. So, after $7$ moves of player $1$ duplicator has no move. Simlpy, Player one choose any node of $K_8$ and then choose all its neighbours.

Tell me please, is it correct ? If not, how to fix it ?

  • $\begingroup$ It is unclear to me how to reconstruct the Game that is being referred to in point 2. Please detail how this is a "first order sentence" as described in the title. $\endgroup$ – hardmath Nov 28 '16 at 12:07
  • $\begingroup$ Ok, I did mistake in title. Edited. $\endgroup$ – user343207 Nov 28 '16 at 12:09
  • $\begingroup$ It remains unclear what "Game" is referred to. Ideally the body of your Question ipresents a self-contained problem statement, plus of course the context of your thoughts about it (points of interest, request for help, etc.) . $\endgroup$ – hardmath Nov 28 '16 at 12:55

(For completeness: the game the OP is talking about is the Ehrenfeucht-Fraisse game.)

It looks to me like it takes Spoiler eight rounds to win: in seven moves alone, Duplicator can respond. So I don't think this works.

  • $\begingroup$ Ok, you are right. So lets decrease graphs - in both graps decrease number nodes by one. yeah ? $\endgroup$ – user343207 Nov 29 '16 at 20:24
  • 1
    $\begingroup$ @HaskellFun Now claim 1 fails for $G_1$ . . . $\endgroup$ – Noah Schweber Nov 29 '16 at 20:26
  • $\begingroup$ Ok, maybe the same graphs as before, but without loops ? $\endgroup$ – user343207 Nov 29 '16 at 20:27
  • $\begingroup$ @HaskellFun Doesn't Spoiler still need 8 moves to win? $\endgroup$ – Noah Schweber Nov 29 '16 at 20:40
  • $\begingroup$ hmm, Is it possible to rescue my solution ? $\endgroup$ – user343207 Nov 29 '16 at 20:44

Your Answer

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