Ehrenfeucht-Fraïssé Games on Random Structures

Certain results in circuit complexity (e.g., the theorem that AC

0

functions have low average sensitivity) [5, 17] imply the existence of winning strategies in Ehrenfeucht-Fraïssé games on pairs of random structures (e.g., ordered random graphs

G

 = 

G

(

n

,1/2) and

G

 + 

 = 

G

 ∪ {

random

edge

}). Standard probabilistic methods in circuit complexity (e.g., the Switching Lemma [11] or Razborov-Smolensky Method [19, 21]), however, give no information about how a winning strategy might look. In this paper, we attempt to identify specific winning strategies in these games (as explicitly as possible). For random structures

G

and

G

 + 

, we prove that the

composition of minimal strategies

in

r

-round Ehrenfeucht-Fraïssé games

$\Game_r(G,G)$

and

$\Game_r(G^{{+}},G^{{+}})$

is almost surely a winning strategy in the game

$\Game_r(G,G^{{+}})$

. We also examine a result of [20] that ordered random graphs

H

 = 

G

(

n

,

p

) and

H

 + 

 = 

H

 ∪ {random

k

-clique} with

p

(

n

) ≪ 

n

− 2/(

k

 − 1)

(below the

k

-clique threshold) are almost surely indistinguishable by

$\lfloor k/4 \rfloor$

-variable first-order sentences of any fixed quantifier-rank

r

. We describe a winning strategy in the corresponding

r

-round

$\lfloor k/4 \rfloor$

-pebble game using a technique that combines strategies from several auxiliary games.