Re: Question on computational complexity

Thanks for reply, Anuj!

Maybe I have stated that desired condition somewhat vague, so I restate
it once more for clarity:
Can we find set of graphs S such that for any k there is N satisfying:
any two graphs from S of order larger than N satisfy the same
first-order
formulas with at most k quantifiers, or equivalently are
undistinguashable by a k-round Ehrefeucht-Fraisse game?

It seems to me that your statement of necessarily FO-definability of S
is wrong.
Take, for example, S to be cycle graphs C_n. Then S is obviously not
first-order definable, by playing for each fixed k on large enough
C_{2n} and 2*C_n. On the other hand, for each fixed k, C_n and C_m with
large enough m and n are indistinguishable as well.
So, it seems question is somewhat subtler.

.

Relevant Pages

  • Re: Indistinguishable families of graphs
    ... members are look-alikes. ... Can we find set of graphs S such that for any k there is N satisfying: ... undistinguashable by a k-round Ehrefeucht-Fraisse game? ...
    (sci.math)
  • Re: Question on computational complexity
    ... Can we find set of graphs S such that for any k there is N satisfying: ... This would give the first-order definability I claimed. ... But, in this case, you can construct such an S of any desired complexity. ...
    (comp.theory)
  • Indistinguishable families of graphs
    ... members are look-alikes. ... Can we find set of graphs S such that for any k there is N satisfying: ...
    (sci.math)