Indistinguishable families of graphs
Artyom
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?
Butch Malahide
I'm not a logician, so I'm just *guessing* that these sets satisfy your
indistinguishability condition. Do they? Are any of them nontrivial?
1. The empty graphs (no edges).
2. The complete graphs K_n.
3. The complete bipartite graphs K_{m,n}.
3. The paths P_n.
4. The cycles C_n.
5. The grid graphs K_m times K_n.
6. The line graphs of complete graphs, L(K_n).
Artyom
All your guesses are correct, of course. The main point I want is to
fuse this certain similarity of graphs with some genericity built into
their family. Genericity may be measured like information content of
this set, maybe completeness/hardess for some not too week complexity
class, LOGSPACE at least. Thus listed examples are way too simple. One
example I have in mind are Paley graphs (by the way, do you know what
is the complexity of recognising whether graph is Paley or not?). Or I
can construct such a family straightforward, but more naturality
desired.
On Nov 25, 11:11 pm, "Butch Malahide" <fred.gal...@gmail.com> wrote:
> 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?I'm not a logician, so I'm just *guessing* that these sets satisfy your
bill
What is an Ehre(n)feucht-Fraisse game?
regards,
Bill J.
Butch Malahide
> 5. The grid graphs K_m times K_n.
Oops, those aren't grid graphs, I meant P_m times P_n.