Re: Indistinguishable families of graphs

From: "bill" <b92057@xxxxxxxxx>
Date: 25 Nov 2006 14:15:37 -0800

Artyom wrote:

Is there some natural not too trivial graph property such that all its
members are look-alikes. More precisely:

Can we find set of graphs S such that for any k there is N satisfying:
any two graphs 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?

What is an Ehre(n)feucht-Fraisse game?

regards,

Bill J.

.

References:
- Indistinguishable families of graphs
  - From: Artyom

Prev by Date: Re: Corrected Z.Irregular set theory.
Next by Date: Re: Indistinguishable families of graphs
Previous by thread: Re: Indistinguishable families of graphs
Next by thread: FInd solutions to f(x) + (1/x)f(1/x) = 1/[2(1+x)]
Index(es):
- Date
- Thread

Relevant Pages

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)
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)
Re: Question on computational complexity
... 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: ...
(comp.theory)