## Spectrum for first-order properties of random hypergraphs

## S.N. Popova 1

The notion of spectrum for first-order properties introduced by J. Spencer for Erd˝s-R´nyi o e random graph is considered in relation to random uniform hypergraphs. We study properties of spectrum for first-order formulae with bounded quantifier depth and estimate the values of minimum and maximum points of this spectrum. We also consider the set of limit points of the spectrum and give a bound for its minimum value.

Keywords: random hypergraphs, first-order properties, zero-one law.

## 1 Introduction

Asymptotic behavior of first-order properties probabilities of the Erd˝s-R´nyi random graph o e G n,p ( ) has been widely studied (see [1]-[10]). In [2] the notion of spectrum of first-order properties was introduced and it was shown that there exists a first-order property with infinite spectrum. In this paper, we consider spectrum of first-order properties in relation to random uniform hypergraphs. Let us define the random s -uniform hypergraph G s ( n, p ) . Consider the set Ω n = { G = ( V , E n ) } of all s -uniform hypergraphs ( s -hypergraphs) with the set of vertices V n = { 1 2 , , . . . , n } . The random hypergraph G s ( n, p ) is a random element with probability distribution

$$\Pr [ G ^ { s } ( n, p ) = G ] = p ^ { | E | } ( 1 - p ) ^ { \binom { n } { s } - | E | }.$$

Note that for s = 2 in this definition we obtain the Erd˝s-R´nyi random graph o e G n,p ( ) . Let us denote the event ' G s ( n, p ) has a property L ' by G s ( n, p ) = | L .

First-order properties of s -uniform hypergraphs are defined by first-order formulae (see [10], [11]) which are built of predicate symbols N, = , logical connectivities, variables and quantifiers ∀ ∃ , . The s -ary predicate symbol N expresses the property of s vertices to constitute an edge. Let us remind that the quantifier depth (see [10], [11]) of a first-order formula is the maximum number of nested quantifiers. Let L k denote the set of all first-order properties which can be expressed by first-order formulae with quantifier depth at most k .

We say that the random hypergraph G s ( n, p ) obeys the zero-one law if for any first-order property L the probability Pr[ G s ( n, p ) | = L ] tends either to 0 or to 1 as n →∞ . We say that the random hypergraph G s ( n, p ) obeys the zero-one k -law if for any first-order property L ∈ L k the probability Pr[ G s ( n, p ) = | L ] tends either to 0 or to 1 as n →∞ .

For any first order property L we define its spectrum S L ( ) . S L ( ) is the set of all α ∈ (0 , s -1) (we take the interval (0 , s -1) because the structure of G s ( n, n -α ) for α &gt; s -1 is considerably simpler than that for α &lt; s -1 and the study of G s ( n, p ) with p n ( ) /greatermuch n -s +1 is a subject of a separate investigation) which do not satisfy the following property: lim n →∞ Pr[ G s ( n, p ) | = L ] exists and is either 0 or 1 . Denote the union of S L ( ) over all L ∈ L k by S k . In other words, S k is the set of all α ∈ (0 , s -1) for which the random hypergraph G s ( n, n -α ) does not obey the zero-one k -law. Let ( S k ) ′ be the set of limit points in S k .

1 Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications.

S. Shelah and J. Spencer (see [1]) showed that when α is an irrational number and p n ( ) = n -α + (1) o then the random graph G n,p ( ) obeys the zero-one law. If α ∈ (0 , 1) ∩ Q , then G n,n ( -α ) does not obey the zero-one law. In [12] an extension of the result from [1] to the case of random uniform hypergraph G s ( n, p ) was established.

M. E. Zhukovskii proved the zero-one k -law for the random graph G n,n ( -α ) where α is close to 0 or close to 1. He also found the minimum and maximum points in S k .

Theorem 1 ([3]). If α &lt; 1 k -2 , then the random graph G n,n ( -α ) obeys the zero-one k -law. If α = 1 k -2 , then G n,n ( -α ) does not obey the zero-one k -law.

Theorem 2 ([4], [5]). Let k &gt; 3 be an arbitrary natural number. Let Q be the set of all positive rational numbers with numerator at most 2 k -1 , and let ˜ Q be the set of natural numbers not exceeding 2 k -1 -2 . The random graph G n,n ( -α ) obeys the zero-one k -law if α = 1 -1 2 k -1 + β , where β ∈ (0 , ∞ \Q ) . If α = 1 -1 2 k -1 + β , β ∈ Q ˜ , then G n,n ( -α ) does not obey the zero-one k -law. If α ∈ { 1 -1 2 k , 1 -1 2 k -1 } , then G n,n ( -α ) obeys the zero-one k -law.

Theorems 1 and 2 imply that min S k = 1 k -2 and max S k = 1 -1 2 k -2 .

M. E. Zhukovskii and J. Spencer examined the question about the minimum and the maximum limit points in S k for the random graph G n,n ( -α ) .

Theorem 3 ([6]). There exists such k 0 such that for any natural k &gt; k 0

$$\min ( S _ { k } ) ^ { \prime } \leq \frac { 1 } { k - 1 1 }, \ \max ( S _ { k } ) ^ { \prime } \geq 1 - \frac { 1 } { 2 ^ { k - 1 3 } }.$$

M. E. Zhukovskii obtained an upper bound for the minimum limit point in S k which is better than the bound from theorem 3 for small k .

Theorem 4 ([7]). For any k ≥ 5 , 1 /floorleft k/ 2 /floorright ∈ ( S k ) ′ .

Theorem 4 implies the following corollary about the minimum quantifier depth k for which S k is infinite.

Corollary 1 ([8]). The minimum k such that the set S k is infinite equals 4 or 5.

Note that since |L k | &lt; ∞ (see Proposition 3.1.3 in [11]), the set S k is infinite if and only if there exists L ∈ L k with infinite spectrum S L ( ) . The following theorem gives an almost exact bound for the minimum quantifier depth of a first-order formula with an infinite spectrum in the case of s -uniform hypergraphs, where s ≥ 3 .

Theorem 5 ([13]). For any s ≥ 3 , the minimum k such that the set S k is infinite equals s +1 or s +2 .

## 2 New results

We found an interval with the left endpoint equals to 0, such that for all α from this interval the random hypergraph G s ( n, n -α ) obeys the zero-one k -law. Note that G s ( n, n -α ) obeys the zero-one s -law for all α ∈ (0 , s -1) so we study zero-one k -laws for k ≥ s +1 .

Theorem 6. Let s ≥ 3 , k ≥ s +1 , α &gt; 0 and

$$\frac { 1 } { \alpha } > \binom { k - 1 } { s - 1 } - 1 - \frac { s - 1 } { k - 1 } + \frac { 2 \left ( 1 + \frac { s - 1 } { k - 1 } \right ) } { \binom { k - 1 } { s - 1 } + 2 }.$$

Then the random hypergraph G s ( n, n -α ) obeys the zero-one k -law.

We also prove that near the right endpoint of our interval there is a point α for which G s ( n, n -α ) does not obey the zero-one k -law.

Theorem 7. Let s ≥ 3 , k ≥ s +2 . Then there exists α &gt; 0 such that

$$\frac { 1 } { \alpha } & > \binom { k - 1 } { s - 1 } - 1 - \frac { s - 1 } { k - 1 } - \frac { 2 } { \binom { k - 1 } { s - 1 } } \\ o h e u \ t h e \ z e r o - o n e \ k _ { - } l a u n$$

and G s ( n, n -α ) does not obey the zero-one k -law.

The question what is the exact value of the minimal point for which the zero-one k -law does not hold remains open. Theorems 6 and 7 imply that this value is very close to 1 / ( ( k -1 s -1 ) -1 -s -1 k -1 ) .

We also examine the zero-one k -law for the left neighborhood of s -1 . Our results are the following.

Theorem 8 . Let α ∈ ( s -1 -1 2 k -s +1 , s -1 ) \Q k , where Q k = { s -1 -1 2 k -s +1 + a b | a, b ∈ N , a ≤ 2 k -s +1 } . Then the random hypergraph G s ( n, n -α ) obeys the zero-one k -law.

Theorem 9 . Let s ≥ 3 , k ≥ s +4 , α = s - -1 1 2 k -s +1 + a , where a ∈ N , a ≤ 2 k - -s 2 +2 k - -s 3 +1 . Then the random hypergraph G s ( n, n -α ) does not obey the zero-one k -law.

For an s -hypergraph G , denote by d G ( x, y ) the distance between vertices x, y ∈ V ( G ) which is defined as the minimal length of a path between x and y (the length of a path is the number of its edges).

Theorem 9 gives a weaker result than theorem 2 which is related to the fact that the following property (which was used for the proof of theorem 2) is true for graphs but is not true for s -hypergraphs, where s ≥ 3 : if for a graph G there exist vertices x , x 1 2 , x 3 ∈ V ( G ) such that d G ( x , x 1 2 ) = a , d G ( x , x 1 3 ) = /floorleft ( a + 1) / 2 /floorright , d G ( x , x 2 3 ) = /ceilingleft ( a + 1) / 2 /ceilingright then there exists a cyclic (2 a +1) -extension in G .

We also study the question about the minimum limit point in S k . Theorem 10. Let k ≥ s + C , where C is a constant. Then min( S k ) ′ ≤ 1 ( k -11 s -1 ) .

Taking into account the bound from theorem 6 we deduce that theorem 10 gives an asymptotically tight bound for min( S k ) ′ .

Corollary 2. We have min( S k ) ′ ∼ ( s -1)! k s -1 , as k →∞ .

We also obtain a bound for min( S k ) ′ which is better than the bound from theorem 10 for small k .

Theorem 11. Let either s = 2 and k ≥ 5 or s ≥ 3 and k ≥ s +2 . Then 1 ( l ( k ) s -1 ) ∈ ( S k ) ′ , where l k .

$$l ( k ) = \max \{ l \in \mathbb { N } \, \colon \, \binom { l } { s - 1 } ( l + 2 ) \leq \binom { k } { s } \}. \\ \mathcal { T } \colon \, \colon \, \colon \, \frac { \cdot } { s } \, \dots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots.$$

This theorem gives a bound for the minimum limit point in S k for all k for which it is known that S k is infinite (see corollary 1 and theorem 5). Note that if s = 2 , then l ( k ) = ⌊ √ k k ( -1) / 2 -1 ⌋ -1 and the bound for min( S k ) ′ obtained in theorem 11 improves the bound from theorem 4.

## 3 Auxiliary statements

## 3.1 Small sub-hypergraphs and extensions

For an arbitrary s -hypergraph G = ( V, E ) , set v G ( ) = | V | , e G ( ) = | E | , ρ G ( ) = e G ( ) v G ( ) , ρ max ( G ) = max H ⊆ G ρ H ( ) . G is called strictly balanced if the density ρ G ( ) of this graph is greater than the density of any its proper subhypergraph. Denote the property of containing a copy of G by L G . Theorem 12 ([14]). If p /lessmuch n -1 /ρ max ( G ) , then lim n →∞ Pr[ G s ( n, p ) | = L G ] = 0 . If p /greatermuch n -1 /ρ max ( G ) , then lim n →∞ Pr[ G s ( n, p ) = | L G ] = 1 .

In other words, the function n -1 /ρ max ( G ) is a threshold for the property L G .

Let G , . . . , G 1 m be strictly balanced s -hypergraphs, ρ G ( 1 ) = . . . = ρ G ( m ) = ρ . Let a i be the number of automorphisms of G i . Denote by N G i the number of copies of G i in G s ( n, p ) . The following theorem is a generalization of a classical result of Bollob´s (see, for example, [15]) to the a case of s -uniform hypergraphs.

Theorem 13 . If p = n -1 /ρ , then

$$( N _ { G _ { 1 } }, \dots, N _ { G _ { m } } ) \stackrel { d } { \rightarrow } ( P _ { 1 }, \dots, P _ { m } ),$$

where P i ∼ Pois ( 1 a i ) are independent Poisson random variables.

Consider arbitrary s -hypergraphs G and H such that H ⊂ G V H , ( ) = { x , . . . , x 1 l } , V ( G ) = { x , . . . , x 1 m } . Denote v G, H ( ) = v G ( ) -v H ( ) , e G, H ( ) = e G ( ) -e H ( ) , ρ G, H ( ) = e G,H ( ) v G,H ( ) , ρ max ( G,H ) = max H ⊂ K ⊆ G ρ K,H ( ) . The pair ( G,H ) is called strictly balanced if ρ G, H ( ) &gt; ρ K,H ( ) for any graph K such that H ⊂ K ⊂ G .

Consider s -hypergraphs ˜ H,G ˜ , where V ( ˜ ) = H { ˜ x , . . . , x 1 ˜ l } , V ( ˜ ) = G { ˜ x , . . . , x 1 ˜ m } , ˜ H ⊂ ˜ G . The hypergraph ˜ G is called ( G, ( x , . . . , x 1 l )) -extension of the collection (˜ x , . . . , x 1 ˜ ) l , if

$$\{ x _ { i _ { 1 } }, \dots, x _ { i _ { s } } \} \in E ( G ) \, \smallsetminus \, E ( H ) \Rightarrow \{ \tilde { x } _ { i _ { 1 } }, \dots, \tilde { x } _ { i _ { s } } \} \in E ( \tilde { G } ) \, \smallsetminus \, E ( \tilde { H } ).$$

If

$$\{ x _ { i _ { 1 } }, \dots, x _ { i _ { s } } \} \in E ( G ) \, \smallsetminus \, E ( H ) \Leftrightarrow \{ \tilde { x } _ { i _ { 1 } }, \dots, \tilde { x } _ { i _ { s } } \} \in E ( \tilde { G } ) \, \smallsetminus \, E ( \tilde { H } ),$$

we call ˜ G a strict ( G, ( x , . . . , x 1 l )) -extension of (˜ x , . . . , x 1 ˜ ) l .

Let α &gt; 0 . For any pair ( G,H ) , where H ⊂ G , set f α ( G,H ) = v G, H ( ) -αe G, H ( ) . The pair ( G,H ) is called α -safe , if f α ( K,H ) &gt; 0 for any K H , ⊂ K ⊆ G . If for any K such that H ⊂ K ⊆ G we have f α ( G,K ) &lt; 0 , then the pair ( G,H ) is called α -rigid . If for any K such that H ⊂ K ⊂ G we have f α ( K,H ) &gt; 0 and f α ( G,H ) = 0 , then the pair ( G,H ) is called α -neutral .

/negationslash

Let ˜ H ⊂ ˜ G ⊂ Γ , T ⊂ K and | V ( T ) | ≤ | V ( ˜ ) G | . The pair ( ˜ G,H ˜ ) is called ( K,T ) -maximal in Γ , if for any subhypergraph ˜ T ⊂ ˜ G with | V ( ˜ ) T | = | V ( T ) | and ˜ T ∩ ˜ = ˜ H T there does not exist a strict ( K,T ) -extension ˜ K of ˜ T in the hypergraph Γ \ ( ˜ G T \ ˜ ) such that E (( ˜ K ∪ ˜ ) G \ ˜ ) T \ ( E K ( ˜ \ ˜ ) T ∪ E G ( ˜ \ ˜ )) = T ∅ . The hypergraph ˜ G is called ( K,T ) -maximal in Γ , if for any subhypergraph ˜ T ⊂ ˜ G with | V ( ˜ ) T | = | V ( T ) | there does not exist a strict ( K,T ) -extension ˜ K of ˜ T in the hypergraph Γ \ ( ˜ G T \ ˜ ) such that E (( ˜ K ∪ ˜ ) G \ ˜ ) T \ ( E K ( ˜ \ ˜ ) T ∪ E G ( ˜ \ ˜ )) = T ∅ .

Let a pair ( G,H ) be α -safe and K r be the set of all α -rigid and α -neutral pairs ( K,T ) , where | V ( T ) | ≤ | V ( G ) | , | V ( K ) \ V ( T ) | ≤ r . Let ˜ x , . . . , x 1 ˜ l ∈ V n . Define a random variable N r ( G,H ) (˜ x , . . . , x 1 ˜ ) l which assigns to each hypergraph G ∈ Ω n the number of all strict ( G,H ) -extensions ˜ G of the hypergraph ˜ H = G| { ˜ x ,...,x 1 ˜ l } such that for any ( K,T ) ∈ K r the pair ( ˜ G,H ˜ ) is ( K,T ) -maximal in G .

The following theorem is the generalization of Lemma 10.7.6 from [16] and Proposition 1 from [17] to the case of s -uniform hypergraphs.

Theorem 14. Let p n ( ) = n -α , r ∈ N and ( G,H ) be α -safe. Then a.a.s. for every vertices ˜ x , . . . , x 1 ˜ l the following relation holds:

$$N _ { ( G, H ) } ^ { r } ( \tilde { x } _ { 1 }, \dots, \tilde { x } _ { l } ) \sim \mathbf E [ N _ { ( G, H ) } ^ { r } ( \tilde { x } _ { 1 }, \dots, \tilde { x } _ { l } ) ] = \Theta ( n ^ { f _ { \alpha } ( G, H ) } ).$$

Denote by L r ( G,H ) the following property: for any collection (˜ x , . . . , x 1 ˜ ) l there exists a strict ( G, ( x , . . . , x 1 l )) -extension which is ( K,T ) -maximal for all ( K,T ) ∈ K r . Theorem 14 implies that if ( G,H ) is α -safe, then the random hypergraph G s ( n, n -α ) satisfies L r ( G,H ) a.a.s.

Denote by ˜ L ( G,H ) the property that there exists a copy of H such that no copy of G contains it. Denote by ˜ N ( G,H ) the number of copies of H in G s ( n, p ) which are not contained in any copy of G .

Proposition 1 ([13]). Let H be a strictly balanced s -hypergraph, ( G,H ) be a strictly balanced pair, ρ H ( ) = ρ G, H ( ) = 1 /α . Let a 1 be the number of automorphisms of H which are extendable to some automorphism of G . Let a 2 be the number of automorphisms σ : V ( G ) → V ( G ) with σ x ( ) = x for all x ∈ V ( H ) . Then

$$\tilde { N } _ { ( G, H ) } \stackrel { d } { \longrightarrow } \text{Pois} \left ( \frac { 1 } { a ( H ) } \exp \left ( - \frac { a ( H ) } { a _ { 1 } a _ { 2 } } \right ) \right ).$$

## 3.2 Cyclic extensions

Consider a pair of s -hypergraphs ( G,H ) , G ⊃ H . We say that G is a cyclic m -extension of H if one of the following conditions holds:

- · there exists a vertex x 1 ∈ V ( H ) such that

$$V ( G ) \, \bar { \ } V ( H ) = \{ y _ { 1 }, \dots, y _ { k ( s - 1 ) }, z _ { 1 }, \dots, z _ { l } \},$$

$$E ( G ) \, \smallsetminus \, E ( H ) = \{ \{ x _ { 1 }, y _ { 1 }, \dots, y _ { s - 1 } \}, \dots, \{ y _ { ( k - 1 ) ( s - 1 ) }, \dots, y _ { k ( s - 1 ) } \}, \\ \{ y _ { k ( s - 1 ) }, z _ { 1 }, \dots, z _ { l }, u _ { 1 }, \dots, u _ { s - 1 - l } \} \},$$

where 1 ≤ k ≤ m -1 , 0 ≤ l &lt; s -1 and u , . . . , u 1 s - -1 l ∈ { y , . . . , y 1 k s ( -1) -1 } are distinct,

- · there exist distinct vertices x , x 1 2 ∈ V ( H ) such that

$$V ( G ) \, \bar { \ } V ( H ) = \{ y _ { 1 }, \dots, y _ { k ( s - 1 ) }, z _ { 1 }, \dots, z _ { l } \},$$

$$E ( G ) \, \smallsetminus \, E ( H ) = \{ \{ x _ { 1 }, y _ { 1 }, \dots, y _ { s - 1 } \}, \dots, \{ y _ { ( k - 1 ) ( s - 1 ) }, \dots, y _ { k ( s - 1 ) } \}, \\ \{ x _ { 2 }, y _ { k ( s - 1 ) }, z _ { 1 }, \dots, z _ { l }, u _ { 1 }, \dots, u _ { s - 2 - l } \} \},$$

where 1 ≤ k ≤ m -1 , 0 ≤ l ≤ s -2 and u , . . . , u 1 s - -2 l ∈ { y , . . . , y 1 k s ( -1) -1 } are distinct,

- · there exist distinct vertices x , . . . , x 1 l ∈ V ( H ) , where 2 ≤ l ≤ s -1 , such that

$$V ( G ) \, \smallsetminus V ( H ) = \{ y _ { 1 }, \dots, y _ { s - l } \}, E ( G ) \, \smallsetminus E ( H ) = \{ x _ { 1 }, \dots, x _ { l }, y _ { 1 }, \dots, y _ { s - l } \},$$

and ρ max ( G &lt; ) m m s ( -1) -1 .

For any m ≥ 1 , let us define a set of s -hypergraphs H m . The hypergraph ( { x , } ∅ ) , where x is a vertex, belongs to H m . If H ∈ H m , then H m contains all cyclic m -extensions of H and all s -hypergraphs G such that V ( G ) = V ( H ) , E G ( ) ⊃ E H ( ) and ρ max ( G &lt; ) m m s ( -1) -1 .

Note that for any hypergraph G ∈ H m there exists a sequence of hypergraphs G 0 = ( { x , } ∅ /subsetnoteql ) G ... 1 /subsetnoteql G t ⊆ G such that G i +1 is a cyclic m -extension of G i for all i ∈ { 0 , . . . , t - } 1 . Let us call such sequence of hypergraphs m -decomposition of G .

## Proposition 2 .

/negationslash

- 1) Let G ∈ H m , G = ( { x , } ∅ ) . Then either G is a cyclic m -extension of ( { x , } ∅ ) and 1 ρ max ( G ) = s -1 or there exist a, b ∈ N such that a ≤ m and 1 ρ max ( G ) = s -1 -1 m a/b + .
- 2) Let m ∈ N , ρ &lt; m m s ( -1) -1 . Then there exists η = η ρ ( ) ∈ N such that any hypergraph G ∈ H m with | V ( G ) | ≥ η contains a subhypergraph H ∈ H m with | V ( H ) | ≤ η and density ρ H ( ) &gt; ρ .

Let n , n 1 2 , n 3 , n 4 ∈ N , n 2 ≤ n 1 , n 4 ≤ n 3 , ρ &gt; 0 . Denote by K ρ the set of all 1 /ρ -rigid pairs ( K ,K 1 2 ) with v K ( 1 ) ≤ n 3 , v K ( 2 ) ≤ n 4 .We say that a s -hypergraph G is ( n , n 1 2 , n 3 , n 4 , ρ ) -sparse if it posseses the following properties.

- 1) Let H be a s -hypergraph with at most n 1 vertices. If ρ max ( H &gt; ρ ) , then G does not contain a subhypergraph isomorphic to H . If ρ max ( H &lt; ρ ) , then G contains an induced subhypergraph which is isomorphic to H and ( K ,K 1 2 ) -maximal in G for all ( K ,K 1 2 ) ∈ K ρ .
- 2) For any 1 /ρ -safe pair ( H ,H 1 2 ) with v H ( 1 ) ≤ n 1 , v H ( 2 ) ≤ n 2 and for any G 2 ⊂ G with v G ( 2 ) = v H ( 2 ) , there exists a subhypergraph G 1 ⊂ G such that G 1 is an exact ( H ,H 1 2 ) -extension of G 2 and ( G , G 1 2 ) is ( K ,K 1 2 ) -maximal in G for all ( K ,K 1 2 ) ∈ K ρ .

$$\text{Let } k \in \mathbb { N }, \, \rho > 0, \, 1 / \rho \in \left ( s - 1 - \frac { 1 } { 2 ^ { k - s + 1 } }, s - 1 \right ). \, \text{Set} \\ n, ( \alpha ) = n ( \alpha ) + ( k - s + 1 ) \mathbb { 2 } ^ { k - s + 1 } \ n _ { \alpha } ( \alpha ) = n ( \alpha ) + ( k - s ) 2$$

$$n _ { 1 } ( \rho ) = \eta ( \rho ) + ( k - s + 1 ) 2 ^ { k - s + 1 }, n _ { 2 } ( \rho ) = \eta ( \rho ) + ( k - s ) 2 ^ { k - s + 1 }, n _ { 3 } = 2 ^ { k - s + 1 }, n _ { 4 } = 2.$$

For a s -hypergraph G , denote by d G ( x, G ˜ ) the distance between a vertex x ∈ V ( G ) and a subhypergraph ˜ G ⊂ G . Denote by d G ( ˜ G , G 1 ˜ 2 ) the distance between ˜ G , G 1 ˜ 2 ⊂ G .

/negationslash

Proposition 3 . Let G be ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 , ρ ) -sparse. Let m ∈ N , m ≤ 2 k -s +1 . Then for any ˜ G ⊂ G with v G ( ˜ ) ≤ n 1 ( ρ ) and any x ∈ V ( ˜ ) G , there exist a vertex y ∈ V ( G ) and a path P ⊂ G such that d G ( y, G ˜ ) = m P , connects x and y , e P ( ) = m v P , ( ) = e P ( )( s -1) + 1 . Moreover, G does not contain any path P ′ of length at most m such that P ′ connects y with a vertex from ˜ G and P ′ = P .

Proposition 4 . Let G,H be ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 , ρ ) -sparse, where 1 /ρ ∈ ( s -1 -1 2 k -s +1 , s -1 ) \ Q k , Q k = { s -1 -1 2 k -s +1 + a b | a, b ∈ N , a ≤ 2 k -s +1 } . Then Duplicator has a winning strategy in EHR G,H,k ( ) .

## 3.3 Ehrenfeucht game

Let us define the Ehrenfeucht game EHR( G , G 1 2 ; k ) for hypergraphs G , G 1 2 and a number k . The game EHR( G , G 1 2 ; k ) is a two-player game (the players are called Spoiler and Duplicator), which is played on a pair of nonempty disjoint s -hypergraphs G 1 and G 2 for a fixed number of rounds k . On the i -th round ( i = 1 2 , , . . . , k ) Spoiler selects an arbitrary vertex x i ∈ V ( G 1 ) or y i ∈ V ( G 2 ) . After that Duplicator must select a vertex from the other graph. At the end of the k -th round there are k chosen vertices in each of the hypergraphs: x , x 1 2 , . . . , x k ∈ V ( G 1 ) and y , y 1 2 , . . . , y k ∈ V ( G 2 ) . Duplicator wins if and only if

$$G _ { 1 } | _ { \{ x _ { 1 }, x _ { 2 }, \dots, x _ { k } \} } \cong G _ { 2 } | _ { \{ y _ { 1 }, y _ { 2 }, \dots, y _ { k } \} },$$

that is the induced subgraphs in the sets of chosen vertices are isomorphic.

The following theorem relates Ehrenfeucht game to the zero-one law. It is a corollary of Ehrenfeucht's Theorem (see [18]).

Theorem 15 . The random s -hypergraph G s ( n, p ( n )) obeys the zero-one k -law if and only if

$$\lim _ { n, m \to \infty } \Pr [ D u p l i c a t o r \ w i n s \ E H R ( G _ { 1 }, G _ { 2 } ; k ) ] = 1,$$

where G 1 ∼ G s ( n, p ( n )) , G 2 ∼ G s ( m,p m ( )) are independently chosen and have disjoint vertex sets.

Thus, to prove that G s ( n, p ( n )) obeys the zero-one law it is sufficient to describe an a.a.s. Duplicator's winning strategy in an Ehrenfeucht game with arbitrary but fixed number of rounds k .

## 4 Proofs of theorems

Proof of theorem 6 . Denote by B m,l the set of all l -element subsets of the set { 1 , . . . , m } . Denote by deg G ( x ) the degree of a vertex x ∈ V ( G ) in a hypergraph G .

By theorem 15 it is sufficient to describe Duplicator's a.a.s. winning strategy in EHR( G , G , k 1 2 ) , where G 1 ∼ G s ( n, n -α ) , G 2 ∼ G s ( m,m -α ) are independently chosen.

1) Let 1 /α &gt; ( k -1 s -1 ) . Let ˜ Ω n be the set of all hypergraphs G ∈ Ω n satisfying the following property: for any r ∈ { s -1 , . . . , k - } A ⊂ B 1 , r,s -1 and distinct vertices z , . . . , z 1 r ∈ V n , there exists a vertex z ∈ V n \ { z , . . . , z 1 r } such that { z i 1 , . . . , z i s -1 , z } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A and { z i 1 , . . . , z i s -1 , z } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B r,s -1 \ A . This property is called the full level ( k -1) extension property . By theorem 14 lim n →∞ Pr[ G s ( n, n -α ) ∈ ˜ Ω ] = 1 n .

Let us consider several cases depending on the value of α . In each case we find sets ˜ Ω n ⊂ Ω n such that Pr[ G s ( n, n -α ) ∈ ˜ Ω ] n → 1 , n →∞ , and prove that for any n , n 1 2 ∈ N and hypergraphs G ∈ ˜ Ω n 1 , H ∈ ˜ Ω n 2 Duplicator has a winning strategy in the game EHR G,H,k ( ) . Denote the vertices chosen in G and H in the i -th round by x i and y i respectively.

Let us describe the winning strategy of Duplicator in EHR G,H,k ( ) , where G ∈ ˜ Ω n 1 , H ∈ ˜ Ω n 2 . Let Spoiler choose a vertex x i ∈ V ( G ) in the i -th round, 1 ≤ i ≤ k . Then by full level ( i -1) extension property Duplicator can choose a vertex y i such that for any distinct j 1 , . . . , j s -1 ∈ { 1 , . . . , i -1 } we have { x j 1 , . . . , x j s -1 , x i } ∈ E G ( ) if and only if { y j 1 , . . . , y j s -1 , y i } ∈ E H ( ) . Therefore, Duplicator wins after the k -th round.

- 2) Let ( k -1 s -1 ) -1 &lt; 1 /α ≤ ( k -1 s -1 ) . Let ˜ Ω n be the set of all hypergraphs G ∈ Ω n satisfying the following properties:
- 1) G satisfies full level ( k -2) extension property,
- 2) for any distinct vertices z , . . . , z 1 k -1 ∈ V n and A /subsetnoteql B k -1 ,s -1 , there exists a vertex z ∈ V n \ { z , . . . , z 1 k -1 } such that { z i 1 , . . . , z i s -1 , z } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A and { z i 1 , . . . , z i s -1 , z } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 \ A ,
- 3) for any distinct vertices z , . . . , z 1 k -2 and A ⊂ B k -2 ,s -1 there exist distinct vertices z k -1 , z k ∈ V n \{ z , . . . , z 1 k -2 } such that { z i 1 , . . . , z i s -1 , z k -1 } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A , { z i 1 , . . . , z i s -1 , z k -1 } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -2 ,s -1 \ A and { z i 1 , . . . , z i s -1 , z k } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 .
- 4) for any distinct vertices z , . . . , z 1 k -2 and A ⊂ B k -2 ,s -1 there exists a vertex z k -1 ∈ V n \ { z , . . . , z 1 k -2 } such that { z i 1 , . . . , z i s -1 , z k -1 } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A , { z i 1 , . . . , z i s -1 , z k -1 } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -2 ,s -1 \ A and there does not exist a vertex z k ∈ V n \{ z , . . . , z 1 k -1 } such that { z i 1 , . . . , z i s -1 , z k } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 .

Note that properties 1)-3) mean that the hypergraph G satisfies L 0 ( ˜ G,H ˜ ) for some pairs ( ˜ G,H ˜ ) , where ρ max ( ˜ G,H ˜ ) equals ( k -2 s -1 ) , ( k -1 s -1 ) -1 and |A| + ( k -1 s -1 ) 2 , where |A| ≤ ( k -2 s -1 ) , respectively. Since all these values don't exceed ( k -1 s -1 ) -1 &lt; 1 /α , theorem 14 implies that the random hypergraph G s ( n, n -α ) satisfies properties 1)-3) a.a.s. Since 1 /α ≤ ( k -1 s -1 ) , the property 4) is satisfied if the hypergraph G satisfies L 1 ( ˜ G,H ˜ ) for some pair ( ˜ G,H ˜ ) , where ρ max ( ˜ G,H ˜ ) = |A| ≤ ( k -2 s -1 ) &lt; 1 /α . Therefore, lim n →∞ Pr[ G s ( n, n -α ) ∈ ˜ Ω ] = 1 n .

Let us describe the winning strategy of Duplicator in EHR G,H,k ( ) , where G ∈ ˜ Ω n 1 , H ∈ ˜ Ω n 2 . Let Spoiler choose a vertex x i ∈ V ( G ) in the i -th round, 1 ≤ i ≤ k -2 . Then by full level ( i -1) extension property Duplicator chooses a vertex y i ∈ V ( H ) such that for any distinct j 1 , . . . , j s -1 ∈ { 1 , . . . , i - } 1 we have { x j 1 , . . . , x j s -1 , x i } ∈ E G ( ) if and only if { y j 1 , . . . , y j s -1 , y i } ∈ E H ( ) .

Let Spoiler choose a vertex x k -1 ∈ V ( G ) in the ( k -1) -th round. Since H satisfies 3) and 4) there exists a vertex y k -1 ∈ V ( H ) such that H | { y ,...,y 1 k -1 } and G | { x ,...,x 1 k -1 } are isomorphic and there exists a vertex x k ∈ V ( G ) such that deg G | { x ,...,x k 1 } ( x k ) = ( k -1 s -1 ) if and only if there exists a vertex y k ∈ V ( H ) such that deg H | { y 1 ,...,y k } ( y k ) = ( k -1 s -1 ) .

$$\text{wins.} \\ 3 ) \, & \text{Let } \, \binom { k - 1 } { s - 1 } - 1 - \frac { s - 1 } { k - 1 } + \frac { 2 \left ( 1 + \frac { s - 1 } { k - 1 } \right ) } { \binom { k - 1 } { s - 1 } + 2 } < 1 / \alpha \leq \binom { k - 1 } { s - 1 } - 1. \\ \text{Let } \, z _ { 1 }, \dots, z _ { k } \, \in \, V _ { n }. \, \text{Let } \, L _ { C } ( z _ { 1 }, \dots, z _ { k } ), \text{ where } \, C \, \in \, \mathcal { B } _ { k - 1, s - 1 },$$

Let Spoiler choose a vertex x k ∈ V ( G ) in the k -th round. If deg G | { x ,...,x k 1 } ( x k ) = ( k -1 s -1 ) , then by the definition of the vertex chosen by Duplicator in the ( k -1) -th round there exists a vertex y k ∈ V ( H ) with deg H | { y 1 ,...,y k } ( y k ) = ( k -1 s -1 ) . If deg G | { x ,...,x k 1 } ( x k ) &lt; ( k -1 s -1 ) , then by property 2) there exists a vertex y k ∈ V ( H ) such that for any distinct j 1 , . . . , j s -1 ∈ { 1 , . . . , i - } 1 we have { x j 1 , . . . , x j s -1 , x i } ∈ E G ( ) if and only if { y j 1 , . . . , y j s -1 , y i } ∈ E H ( ) . So in both cases Duplicator wins.

Let z , . . . , z 1 k ∈ V n . Let L C ( z , . . . , z 1 k ) , where C ∈ B k -1 ,s -1 , be the following property of a hypergraph G ∈ Ω n : { z i 1 , . . . , z i s -1 , z k } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 \ { C } and { z i 1 , . . . , z i s -1 , z k } ∈ / E G ( ) for { i 1 , . . . , i s -1 } = C . Let L ∅ ( z , . . . , z 1 k ) be the following property of a hypergraph G ∈ Ω n : { z i 1 , . . . , z i s -1 , z k } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 .

Let ˜ Ω n be the set of all hypergraphs G ∈ Ω n satisfying the following properties:

- 1) G satisfies full level ( k -2) extension property,
- 2) for any distinct vertices z , . . . , z 1 k -1 ∈ V n and A ⊂ B k -1 ,s -1 , where |A| ≤ ( k -1 s -1 ) -2 , there exists a vertex z ∈ V n \ { z , . . . , z 1 k -1 } such that { z i 1 , . . . , z i s -1 , z } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A and { z i 1 , . . . , z i s -1 , z } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -1 ,s -1 \ A ,
- 3) for any distinct vertices z , . . . , z 1 k -2 , A ⊂ B k -2 ,s -1 and C ⊂ B k -1 ,s -1 ∪ { ∅ } there exists a vertex z k -1 ∈ V n \{ z , . . . , z 1 k -2 } such that { z i 1 , . . . , z i s -1 , z k -1 } ∈ E G ( ) for all { i 1 , . . . , i s -1 } ∈ A { , z i 1 , . . . , z i s -1 , z k -1 } ∈ / E G ( ) for all { i 1 , . . . , i s -1 } ∈ B k -2 ,s -1 \A and for any C ∈ C there exists a vertex z C k ∈ V n \{ z , . . . , z 1 k -1 } such that the property L C ( z , . . . , z 1 k -1 , z C k ) is satisfied and for any C ∈ ( B k -1 ,s -1 ∪ { ∅ } ) \ C there does not exist a vertex z C k ∈ V n \ { z , . . . , z 1 k -1 } such that L C ( z , . . . , z 1 k -1 , z C k ) is satisfied.

Note that properties 1)-2) mean that the hypergraph G satisfies L 0 ( ˜ G,H ˜ ) for some pairs ( ˜ G,H ˜ ) , where ρ max ( ˜ G,H ˜ ) equals ( k -2 s -1 ) and ( k -1 s -1 ) -2 respectively. Since 1 /α ≤ ( k -1 s -1 ) -1 , the property 4)

is satisfied if the hypergraph G satisfies L 1 ( ˜ G,H ˜ ) for some pair ( ˜ G,H ˜ ) , where

$$\rho ^ { \max } ( \tilde { G }, \tilde { H } ) \leq \frac { \binom { k - 2 } { s - 1 } + \binom { k - 1 } { s - 1 } + \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) } { \binom { k - 1 } { s - 1 } + 2 } = \binom { k - 1 } { s - 1 } - 1 - \frac { \binom { k - 2 } { s - 2 } - 2 } { \binom { k - 1 } { s - 1 } + 2 } =$$

$$\frac { \stackrel { \kappa - c } { s - 1 } \choose s - 1 } + \stackrel { \kappa - 1 } { s - 1 } \choose s - 1 \choose s - 1 + 2 } = \binom { k - 1 } { s - 1 } - 1 - \frac { \stackrel { k - 2 } { s - 2 } \choose s - 1 } + 2 = \\ = \binom { k - 1 } { s - 1 } - 1 - \frac { s - 1 } { k - 1 } + \frac { 2 \left ( 1 + \frac { s - 1 } { k - 1 } \right ) } { \stackrel { k - 1 } { s - 1 } \choose s - 1 } + 2$$

Therefore, lim n →∞ Pr[ G s ( n, n -α ) ∈ ˜ Ω ] = 1 n .

$$\overline { \binom { k - 1 } { s - 1 } }.$$

Let us describe the winning strategy of Duplicator in EHR G,H,k ( ) , where G ∈ ˜ Ω n 1 , H ∈ ˜ Ω n 2 . Let Spoiler choose a vertex x i ∈ V ( G ) in the i -th round, 1 ≤ i ≤ k -2 . Then by full level ( i -1) extension property Duplicator chooses a vertex y i ∈ V ( H ) such that for any distinct j 1 , . . . , j s -1 ∈ { 1 , . . . , i - } 1 we have { x j 1 , . . . , x j s -1 , x i } ∈ E G ( ) if and only if { y j 1 , . . . , y j s -1 , y i } ∈ E H ( ) .

Let Spoiler choose a vertex x k -1 ∈ V ( G ) in the ( k -1) -th round. Then by property 3) there exists a vertex y k -1 ∈ V ( H ) such that H | { y ,...,y 1 k -1 } and G | { x ,...,x 1 k -1 } are isomorphic and for each C ∈ B k -1 ,s -1 ∪ { ∅ } there exists a vertex x k ∈ V ( G ) such that G satisfies L C ( x , . . . , x 1 k ) if and only if there exists a vertex y k ∈ V ( G ) such that H satisfies L C ( y , . . . , y 1 k ) .

Let Spoiler choose a vertex x k ∈ V ( G ) in the k -th round. If deg G | { x ,...,x k 1 } ( x k ) ≥ ( k -1 s -1 ) -1 , then there exists exactly one C ∈ B k -1 ,s -1 ∪{ ∅ } such that G satisfies L C ( x , . . . , x 1 k ) . By the definition of the vertex chosen by Duplicator in the ( k -1) -th round there exists a vertex y k ∈ V ( H ) such that H satisfies L C ( y , . . . , y 1 k ) . If deg G | { x ,...,x k 1 } ( x k ) &lt; ( k -1 s -1 ) -1 , then by property 2) there exists a vertex y k ∈ V ( H ) such that for any distinct j 1 , . . . , j s -1 ∈ { 1 , . . . , i - } 1 we have { x j 1 , . . . , x j s -1 , x i } ∈ E G ( ) if and only if { y j 1 , . . . , y j s -1 , y i } ∈ E H ( ) . So in both cases Duplicator wins.

/negationslash

Proof of theorem 7 . Denote by B m,l the set of all l -element subsets of the set { 1 , . . . , m } . Let A = {{ A,B } : A,B ∈ B k -2 ,s -1 , A = B } .

Let L be a property expressed by the formula

$$\exists x _ { 1 } \dots \exists x _ { k - 2 } \bigwedge _ { \{ A, B \} \in \mathcal { A } } \left ( \bigwedge _ { C \in \mathcal { B } _ { k - 1, s - 1 } } \exists x _ { k - 1 } \ Q _ { A, B, C } ( x _ { 1 }, \dots, x _ { k - 1 } ) \right ),$$

where

$$Q _ { A, B, C } ( x _ { 1 }, \dots, x _ { k - 1 } ) = R _ { A, B } ^ { 2 } ( x _ { 1 }, \dots, x _ { k - 1 } ) \wedge W _ { C } ( x _ { 1 }, \dots, x _ { k - 1 } ),$$

$$R _ { A, B } ^ { 2 } ( x _ { 1 }, \dots, x _ { k - 1 } ) = \left ( \bigwedge _ { \{ i _ { 1 }, \dots, i _ { k - 1 } \} \in \mathcal { B } _ { k - 2, s - 1 } \, \{ A, B \} } N ( x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } }, x _ { k - 1 } ) \right ) \bigwedge \\ / \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

/negationslash

$$\bigwedge \left ( \bigwedge _ { \{ i _ { 1 }, \dots, i _ { s - 1 } \} \in \{ A, B \} } ( \neg N ( x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } }, x _ { k - 1 } ) ) \right ) \bigwedge ( ( x _ { 1 } \neq x _ { 2 } ) \wedge \dots \wedge ( x _ { k - 2 } \neq x _ { k - 1 } ) ), \\ \Big.$$

/negationslash

$$W _ { C } ( x _ { 1 }, \dots, x _ { k - 1 } ) = \left ( \bigwedge _ { C ^ { \prime } \in \mathcal { B } _ { k - 1, e - 1 } \vee \{ C \} } \exists x _ { k } \, R _ { C ^ { \prime } } ^ { 1 } ( x _ { 1 }, \dots, x _ { k } ) \right ) \wedge ( - ( \exists x _ { k } \, R _ { C } ^ { 1 } ( x _ { 1 }, \dots, x _ { k } ) ),$$

/negationslash

/negationslash where { j 1 , . . . , j s -1 } = C . Let K be a hypergraph with

$$R _ { C } ^ { 1 } ( x _ { 1 }, \dots, x _ { k } ) = & \left ( \bigwedge _ { \{ i _ { 1 }, \dots, i _ { s - 1 } \} \in \mathcal { B } _ { k - 1, s - 1 } \vee \{ C \} } N ( x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } }, x _ { k } ) \right ) \bigwedge \\ & \bigwedge ^ { ( - N } ( x _ { j _ { 1 } }, \dots, x _ { j _ { s - 1 } }, x _ { k } ) ) \bigwedge ^ { ( ( x _ { k } \neq x _ { 1 } ) \wedge \dots \wedge ( x _ { k } \neq x _ { k - 1 } ) ) } \text{,} \\ \text{where } \{ j _ { 1 }, \dots, j _ { s - 1 } \} = C.$$

/negationslash

$$V ( K ) = \{ x _ { 1 }, \dots, x _ { k - 2 } \} \cup \left \{ x _ { k - 1 } ^ { A, B, C } \, \colon \{ A, B \} \in \mathcal { A }, C \in \mathcal { B } _ { k - 1, s - 1 } \right \} \cup \\ \cup \left \{ x _ { k } ^ { A, B, C, C ^ { \prime } } \, \colon \{ A, B \} \in \mathcal { A }, C, C ^ { \prime } \in \mathcal { B } _ { k - 1, s - 1 }, C \neq C ^ { \prime } \right \}$$

$$\cup \left \{ x _ { k } ^ { A, B, C, C ^ { \prime } } \colon \{ A, B \} \in \mathcal { A }, C, C ^ { \prime } \in \mathcal { B } _ { k - 1, s - 1 }, C \neq C ^ { \prime } \right \}$$

and

/negationslash

$$E ( K ) = \left \{ \left \{ x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } }, x _ { k - 1 } ^ { A, B, C } \right \} \colon \{ A, B \} \in \mathcal { A }, C \in \mathcal { B } _ { k - 1, s - 1 }, \{ i _ { 1 }, \dots, i _ { s - 1 } \} \in \mathcal { B } _ { k - 2, s - 1 } \ \left \{ A, B \} \right \} \cup \\ \cup \left \{ \left \{ x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } }, x _ { k } ^ { A, B, C, C ^ { \prime } } \right \} \colon \{ A, B \} \in \mathcal { A }, C, C ^ { \prime } \in \mathcal { B } _ { k - 1, s - 1 }, C \neq C ^ { \prime }, \\ \{ i _ { 1 }, \dots, i _ { s - 1 } \} \in \mathcal { B } _ { k - 2, s - 1 } \ \left \{ C ^ { \prime } \} \right \} \cup \left \{ \left \{ x _ { i _ { 1 } }, \dots, x _ { i _ { s - 2 } }, x _ { k - 1 } ^ { A, B, C }, x _ { k } ^ { A, B, C, C ^ { \prime } } \right \} \colon \\ \{ A, B \} \in \mathcal { A }, C, C ^ { \prime } \in \mathcal { B } _ { k - 1, s - 1 }, C \neq C ^ { \prime }, \{ i _ { 1 }, \dots, i _ { s - 2 } \} \in \mathcal { B } _ { k - 2, s - 2 }, \{ i _ { 1 }, \dots, i _ { s - 2 }, k - 1 \} \neq C ^ { \prime } \}.$$

/negationslash

{ A,B } ∈ A , C, C ′ ∈ B k -1 ,s -1 , C = C , ′ { i 1 , . . . , i s -2 } ∈ B k -2 ,s -2 , { i 1 , . . . , i s -2 , k - } /negationslash 1 = C ′ } .

The hypergraph K is strictly balanced and

$$| V ( K ) | = k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ),$$

$$| E ( K ) | = | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) + | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) ^ { 2 }.$$

Let us prove that if a hypergraph G posseses property L , then it contains either a subhypergraph isomorphic to K or a subhypergraph ˜ K with v K ( ˜ ) ≤ v K ( ) and ρ K ( ˜ ) &gt; ρ K ( ) . Suppose that a hypergraph G posseses property L . Then there exist distinct vertices x , . . . , x 1 k -2 , x A,B,C k -1 ∈ V ( G ) , where { A,B } ∈ A , C ∈ B k -1 ,s -1 , such that the predicates Q A,B,C ( x , . . . , x 1 k -2 , x A,B,C k -1 ) are true for all { A,B } ∈ A , C ∈ B k -1 ,s -1 . Let ˜ = V { x , . . . , x 1 k -2 }∪ { x A,B,C k -1 : { A,B } ∈ A , C ∈ B k -1 ,s -1 } . The truth of the predicate R 2 A,B ( x , . . . , x 1 k -2 , x A,B,C k -1 ) implies that deg G | { x ,...,x k 1 -2 ,x A,B,C k -1 } ( x A,B,C k -1 ) =

( k -2 s -1 ) -2 . The truth of the predicates W C ( x , . . . , x 1 A,B,C k -1 ) implies that there exist distinct vertices x , . . . , x 1 k N 1 k , x ˜ 1 k , . . . , x ˜ N 2 k ∈ V ( G ) \ ˜ V and numbers v , . . . , v 1 N 1 , w , . . . , w 1 N 2 ∈ N such that deg G | ˜ V ∪{ x i k } ( x i k ) = ( k -2 s -1 ) -1 + v i ( k -2 s -2 ) and deg G | ˜ V ∪{ ˜ x i k } (˜ x i k ) = ( k -2 s -1 ) + w i ( ( k -2 s -2 ) -1 ) , where

$$\sum _ { i = 1 } ^ { N _ { 1 } } v _ { i } = | \mathcal { A } | \binom { k - 2 } { s - 2 } \binom { k - 2 } { s - 1 } + | \mathcal { A } | \binom { k - 2 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) = | \mathcal { A } | \binom { k - 2 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ),$$

$$V ( \tilde { K } ) = k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } + N _ { 2 },$$

$$\sum _ { i = 1 } ^ { N _ { 1 } } v _ { i } & = | \mathcal { A } | \binom { k - 2 } { s - 2 } \binom { k - 2 } { s - 1 } + | \mathcal { A } | \binom { k - 2 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) = | \mathcal { A } | \binom { k - 2 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ), \\ \sum _ { i = 1 } ^ { N _ { 1 } } w _ { i } & = | \mathcal { A } | \binom { k - 2 } { s - 2 } \left ( \binom { k - 2 } { s - 2 } - 1 \right ) + | \mathcal { A } | \binom { k - 2 } { s - 1 } \binom { k - 2 } { s - 2 } = | \mathcal { A } | \binom { k - 2 } { s - 2 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ). \\ \text{Let } \tilde { K } & = G | _ { \tilde { V } \cup \{ x _ { k } ^ { 1 }, \dots, x _ { k } ^ { N _ { 1 } }, \tilde { K } ^ { 1 } _ { k }, \dots, \tilde { K } ^ { N _ { 2 } } _ { k } \} } \text{ Then } \\ V ( \tilde { K } ) & = k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } + N _ { 2 },$$

$$| E ( \tilde { K } ) | & \geq | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) + N _ { 2 } \binom { k - 2 } { s - 1 } + \sum _ { i = 1 } ^ { N _ { i } } v _ { i } \binom { k - 2 } { s - 2 } + \\ & + \sum _ { i = 1 } ^ { N _ { 2 } } w _ { i } \left ( \binom { k - 2 } { s - 2 } - 1 \right ) = | \mathcal { A } | \binom { k - 2 } { s - 2 } \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) + \\ + | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) - | \mathcal { A } | \binom { k - 2 } { s - 2 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) + N _ { 2 } \binom { k - 2 } { s - 1 }. \\ \text{Fence}$$

$$+ | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) - | \mathcal { A } | \binom { k - 2 } { s - 2 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) + N _ { 2 } \binom { k - 2 } { s - 1 }. \\ \text{Hence} \\ \rho ( \tilde { K } ) \geq \frac { e _ { 0 } + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) + N _ { 2 } \binom { k - 2 } { s - 1 } } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } + N _ { 2 } },$$

where

$$\rho ( \tilde { K } ) \geq \frac { e _ { 0 } + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) + N _ { 2 } \binom { k - 2 } { s - 1 } } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } + N _ { 2 } },$$

$$e _ { 0 } = | \mathcal { A } | \binom { k - 2 } { s - 2 } \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) + | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) - | \mathcal { A } | \binom { k - 2 } { s - 2 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ).$$

Note that 1 ≤ N 1 ≤ N max 1 , 1 ≤ N 2 ≤ N max 2 , where N max 1 = |A| ( k -2 s -1 ) ( ( k -1 s -1 ) -1 ) , N max 2 = |A| ( k -2 s -2 ) ( ( k -1 s -1 ) -1 ) . Since

$$\frac { e _ { 0 } + N _ { 1 } \left ( \binom { k - 2 } { s - 1 } - 1 \right ) } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } } & > \binom { k - 2 } { s - 1 }, \\ \text{as as $N_{o}$ grows. Similarlv. $o(\tilde{K}$) decreases as $N_{1}$}$$

the density ρ K ( ˜ ) decreases as N 2 grows. Similarly, ρ K ( ˜ ) decreases as N 1 grows. Therefore,

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ \rho ( \tilde { K } ) \geq \frac { e _ { 0 } + \left ( N _ { 1 } ^ { \max } + N _ { 2 } ^ { \max } \right ) \binom { k - 2 } { s - 1 } - N _ { 1 } ^ { \max } } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } + N _ { 1 } ^ { \max } + N _ { 2 } ^ { \max } } = \\ = \frac { | \mathcal { A } | \binom { k - 1 } { s - 1 } ^ { 2 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) + | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 1 } - 2 \right ) - | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 1 } { s - 1 } - 1 \right ) } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } ^ { 2 } } = \rho ( K ). \\ \text{The density } \rho ( \tilde { K } ) \, \text{equals } \rho ( K ) \, \text{if and only if } N _ { 1 } = N _ { 1 } ^ { \max }, \, N _ { 2 } = N _ { 2 } ^ { \max } \, \text{and } \, \tilde { K } \, \text{ is isomorphic to } K.$$

The density ρ K ( ˜ ) equals ρ K ( ) if and only if N 1 = N max 1 , N 2 = N max 2 and ˜ K is isomorphic to K . We have

$$\rho ( K ) = \binom { k - 1 } { s - 1 } - 1 - \frac { | \mathcal { A } | \binom { k - 1 } { s - 1 } \left ( \binom { k - 2 } { s - 2 } + 1 \right ) + ( k - 2 ) \left ( \binom { k - 1 } { s - 1 } - 1 \right ) } { k - 2 + | \mathcal { A } | \binom { k - 1 } { s - 1 } ^ { 2 } } \geq \\ \geq \binom { k - 1 } { s - 1 } - 1 - \frac { \binom { k - 2 } { s - 2 } + 1 } { \binom { k - 1 } { s - 1 } } - \frac { ( k - 2 ) } { | \mathcal { A } | \binom { k - 1 } { s - 1 } } \geq \binom { k - 1 } { s - 1 } - 1 - \frac { s - 1 } { k - 1 } - \frac { 2 } { \binom { k - 1 } { s - 1 } }. \\ \intertext {.,. } \, \text{Let $\alpha = 1/\rho(K)$. Then by theorem } 1 2 \Pr [ G ^ { * } ( n, n ^ { - \alpha } ) \models L ] = \Pr [ G ^ { * } ( n, n ^ { - \alpha } ) \models L _ { K } ] + o ( 1 ). \ B y$$

Let α = 1 /ρ K ( ) . Then by theorem 12 Pr[ G s ( n, n -α ) | = L ] = Pr[ G s ( n, n -α ) | = L K ] + o (1) . By theorem 13 there exists lim n →∞ Pr[ G s ( n, n -α ) = | L K ] ∈ (0 , 1) . Hence there exists lim n →∞ Pr[ G s ( n, n -α ) | = L ] ∈ (0 , 1) . So G s ( n, n -α ) does not follow the zero-one k -law and the theorem is proved.

Proof of Theorem 8 . Theorems 12 and 14 imply that G s ( n, n -α ) is ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparse a.a.s. Then by Proposition 4 Duplicator has a winning strategy in the game EHR G ( s ( n , n 1 -α 1 ) ,

G s ( n , n 2 -α 2 ) , k ) a.a.s. Therefore, by theorem 15 G s ( n, n -α ) follows the zero-one k -law.

## Proof of Theorem 9 . Let

$$D _ { 1 } ( x _ { 1 }, x _ { 2 } ) = ( x _ { 1 } = x _ { 2 } ) \vee ( \exists x _ { 3 } \dots \exists x _ { s } \ \ N ( x _ { 1 }, \dots, x _ { s } ) ),$$

$$D _ { i } ( x _ { 1 }, x _ { 2 } ) = \exists x _ { 3 } \ ( D _ { \lfloor i / 2 \rfloor } ( x _ { 1 }, x _ { 3 } ) \wedge D _ { \lceil i / 2 \rceil } ( x _ { 3 }, x _ { 2 } ) ), \ \ i > 1.$$

$$\begin{smallmatrix} \\ \end{smallmatrix}$$

Let

/negationslash

$$D _ { 1 } ^ { = } ( x _ { 1 }, x _ { 2 } ) = D _ { 1 } ( x _ { 1 }, x _ { 2 } ) \wedge ( x _ { 1 } \neq x _ { 2 } ), \ \ D _ { i } ^ { = } ( x _ { 1 }, x _ { 2 } ) = D _ { i } ( x _ { 1 }, x _ { 2 } ) \wedge ( \neg ( D _ { i - 1 } ( x _ { 1 }, x _ { 2 } ) ) ), \ \ i > 1.$$

Then quantifier depths of formulae D i and D = i equal /ceilingleft log 2 i /ceilingright + s -2 . D x ,x i ( 1 2 ) expresses the property that the the distance between vertices x 1 and x 2 is at most i . D = i ( x , x 1 2 ) expresses the property that the distance between x 1 and x 2 equals i . Let

/negationslash

/negationslash

/negationslash

$$\tilde { D } _ { 1 } ( x, x _ { 1 }, x _ { 2 } ) = ( x _ { 1 } \neq x ) \wedge ( x _ { 2 } \neq x ) \wedge ( ( x _ { 1 } = x _ { 2 } ) \vee ( \exists x _ { 3 } \dots \exists x _ { s } \quad ( N ( x _ { 1 }, \dots, x _ { s } ) \wedge \\ \wedge ( x _ { 3 } \neq x ) \wedge \dots \wedge ( x _ { s } \neq x ) ) ) ),$$

/negationslash

/negationslash

˜ ( D x,x ,x i 1 2 ) = ( x 1 = x ) ∧ ( x 2 = x ) ∧ ∃ ( x 3 (( x 3 = x ) ∧ ˜ D /floorleft i/ 2 /floorright ( x, x 1 , x 3 ) ∧ ˜ D /ceilingleft i/ 2 /ceilingright ( x, x 3 , x 2 ))) , i &gt; 1 .

/negationslash

/negationslash

Then ˜ ( D x,x ,x i 1 2 ) expresses the property that there exists a path of length at most i which connects x 1 and x 2 and does not contain x . The quantifier depth of ˜ D i equals /ceilingleft log 2 i /ceilingright + s -2 .

For i ∈ N , let

$$C _ { i } ( x _ { 1 } ) = \exists x _ { 2 } \, \left ( D _ { i } ^ { = } ( x _ { 1 }, x _ { 2 } ) \wedge \left ( \exists x _ { 3 } \, \left ( B _ { i + 1 } ( x _ { 1 }, x _ { 2 }, x _ { 3 } ) \wedge \tilde { D } _ { i } ( x _ { 3 }, x _ { 1 }, x _ { 2 } ) \right ) \right ) \right ),$$

where

$$B _ { i } ( x _ { 1 }, x _ { 2 }, x _ { 3 } ) = D _ { [ i / 2 ] } ^ { = } ( x _ { 1 }, x _ { 3 } ) \wedge D _ { [ i / 2 ] } ^ { = } ( x _ { 3 }, x _ { 2 } ), \ \ i \geq 2.$$

Then the quantifier depth of C i equals /ceilingleft log 2 i /ceilingright + s .

Let a ∈ N , a ≤ 2 k - -s 2 +2 k - -s 3 +1 . Then there exist a , a 1 2 , a 3 ∈ N such that 2 a 1 +2 a 2 +1+ a 3 = 2 k -s +1 + a , 2 ≤ a 1 ≤ 2 k -s , a 2 ≤ 2 k - -s 4 , a 3 ≤ 2 k - -s 2 and a 2 &lt; a 1 .

Let L be a property expressed by the formula

$$\exists x _ { 1 } \exists x _ { 2 } \left ( D _ { a _ { 1 } } ^ { = } ( x _ { 1 }, x _ { 2 } ) \wedge ( \exists x _ { 3 } \left ( B _ { a _ { 1 } } ( x _ { 1 }, x _ { 2 }, x _ { 3 } ) \wedge Q ( x _ { 3 } ) \right ) ) \wedge ( \exists x _ { 3 } \left ( B _ { a _ { 1 } } ( x _ { 1 }, x _ { 2 }, x _ { 3 } ) \wedge ( \neg Q ( x _ { 3 } ) ) \right ) ),$$

where

$$Q ( x _ { 3 } ) = \exists x _ { 4 } \ ( D _ { a _ { 3 } } ^ { = } ( x _ { 3 }, x _ { 4 } ) \wedge C _ { a _ { 2 } } ( x _ { 4 } ) ).$$

Then the quantifier depth of the formula expressing the property L is at most k . Let us prove that Pr[ G s ( n, n -α ) = | L ] tends neither to 0 nor to 1 . Let K be a hypergraph with

$$V ( K ) = \{ x _ { 1 }, \dots, x _ { 2 a _ { 1 } ( s - 1 ) }, y _ { 1 }, \dots, y _ { ( 2 a _ { 2 } + 1 ) ( s - 1 ) }, z _ { 1, \dots, z _ { a _ { 3 } ( s - 1 ) } - 1 } \},$$

E K ( ) = { x ( i -1)( s -1)+1 , . . . , x i ( s -1)+1 : 1 ≤ i &lt; 2 a 1 } ∪ {{ x (2 a 1 -1)( s -1)+1 , . . . , x 2 a 1 ( s -1) , x 1 }}∪ ∪{ y ( i -1)( s -1)+1 , . . . , y i ( s -1)+1 : 1 ≤ i &lt; 2 a 2 +1 } ∪ {{ y 2 a 2 ( s -1)+1 , . . . , y (2 a 2 +1)( s -1) , y 1 }}∪ ∪{{ x , z 1 1 , . . . , z s -1 } { , z ( a 3 -1)( s -1) , . . . , z a 3 ( s -1) -1 , y 1 }}∪{ z i ( s -1) , . . . , z ( +1)( i s -1) : 1 ≤ i &lt; a 3 - } 1

The hypergraph K is strictly balanced and 1 /ρ K ( ) = s -1 -1 2 k -s +1 + a = α . Theorem 12 implies that Pr[ G s ( n, n -α ) = | L ] ≥ Pr[ G s ( n, n -α ) | = L K ] + o (1) . Since by theorem 13 there exists lim n →∞ Pr[ G s ( n, n -α ) | = L K ] ∈ (0 , 1) , we obtain that lim inf n →∞ Pr[ G s ( n, n -α ) = | L &gt; ] 0 .

Let us show that if a hypergraph posseses property L , then it contains a subhypergraph ˜ K with e K ( ˜ ) ≤ 2 k -s +1 + a and v K ( ˜ ) ≤ e K ( ˜ )( s -1) -1 . Let G be a hypergraph which posseses property L . Then there exist distinct vertices x , x 1 2 , x 1 3 , x 2 3 ∈ V ( G ) such that

$$d _ { G } ( x _ { 1 }, x _ { 2 } ) = a _ { 1 }, \ \ d _ { G } ( x _ { 1 }, x _ { 3 } ^ { i } ) = \lfloor a _ { 1 } / 2 \rfloor, d _ { G } ( x _ { 2 }, x _ { 3 } ^ { i } ) = \lceil a _ { 1 } / 2 \rceil, \ \ i \in \{ 1, 2 \},$$

/negationslash

So we have Pr[ G s ( n, n -α ) = | L ] ≤ Pr[ G s ( n, n -α ) | = L K ] , where L K is the property of containing a subhypergraph isomorphic to one of the hypergraphs from the set K , where K is a finite set of s -hypergraphs with density at least 1 /α . By theorem 13 there exists lim n →∞ Pr[ G s ( n, n -α ) | = L K ] ∈ (0 , 1) . Hence lim sup n →∞ Pr[ G s ( n, n -α ) = | L &lt; ] 1 .

the predicate Q x ( 1 3 ) is true and the predicate Q x ( 2 3 ) is false. Let W i 1 be a path of length /floorleft a / 1 2 /floorright connecting x 1 and x i 3 , W i 2 be a path of length /ceilingleft a / 1 2 /ceilingright connecting x 2 and x i 3 . Then W 1 1 ∪ W 1 2 ∪ W 2 1 ∪ W 2 2 contains either a subhypergraph ˜ K with e K ( ˜ ) ≤ 2 a 1 and v K ( ˜ ) ≤ e K ( ˜ )( s -1) -1 or a cycle P 1 such that x , x 1 3 2 3 ∈ V ( P 1 ) , e P ( 1 ) ≤ 2 a 1 and v P ( 1 ) = e P ( 1 )( s -1) . Since Q x ( 1 3 ) is true, there exists a (2 a 2 + a 3 +1) -cyclic extension P 2 of ( { x 1 3 } , ∅ ) in G . Since Q x ( 2 3 ) is false, P 2 = P 1 . Therefore, for the hypergraph ˜ K = P 1 ∪ P 2 we have e K ( ˜ ) ≤ 2 a 1 +2 a 2 + a 3 +1 = 2 k -s +1 + a and v K ( ˜ ) ≤ e K ( ˜ )( s -1) -1 .

Therefore, G s ( n, n -α ) does not follow the zero-one k -law.

For vertices x , . . . , x 1 k in a hypergraph G denote by ˜ ( N x ,. . . , x 1 k ) the set of all vertices y ∈ V ( G ) such that for all distinct i 1 , . . . i s -1 ∈ { 1 , . . . , k } we have { y, x i 1 , . . . , x i s -1 } ∈ E ( G ) .

Proof of theorem 10 . Let L be a first-order property which is expressed by the formula ∃ x 1 . . . ∃ x k -11 ( Q 1 ( x , . . . , x 1 k -11 ) ∧ Q 2 ( x , . . . , x 1 k -11 )) , where the formulae Q 1 ( x , . . . , x 1 k -11 ) and Q 2 ( x , . . . , x 1 k -11 ) are defined below.

First, let us introduce some notation. Fix vertices x , . . . , x 1 k -11 , z . Set X = ˜ ( N x ,. . . , x 1 k -11 ) . Consider the following predicates:

/negationslash

$$T _ { z } ( x ) = \exists v \left ( ( v \in \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 3 }, z, x ) ) \wedge \\ ( \forall y \in X \left ( ( y \neq x ) \Rightarrow & \bigcap _ { \{ a _ { 1 }, \dots, a _ { s - 2 } \} \subset \{ x _ { 1 }, \dots, x _ { k - 1 3 }, z \} } ( \neg N ( v, y, a _ { 1 }, \dots, a _ { s - 2 } ) ) ) \right ) ),$$

/negationslash

$$R _ { z } ( a, b ) & = \exists v \left ( ( v \in \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 4 }, z, a, b ) ) \wedge \\ & \quad ( \forall y \in X \left ( ( ( y \neq a ) \wedge ( y \neq b ) \right ) \Rightarrow \bigcap _ { \{ a _ { 1 }, \dots, a _ { s - 2 } \} \subset \{ x _ { 1 }, \dots, x _ { k - 1 4 }, z \} } ( \neg N ( v, y, a _ { 1 }, \dots, a _ { s - 2 } ) ) ) ) ).$$

/negationslash

Let H 1 ( z ) = { x : T z ( x ) } , H 2 ( z ) = { x : ∃ y ∈ H 1 ( z , R ) z ( x, y ) } . For a vertex x set N z ( x ) = { y : R z ( x, y ) } .

Let

$$Q _ { 1 } ( x _ { 1 }, \dots, x _ { k - 1 1 } ) = \exists z \ ( \varphi _ { 1 } ( z ) \wedge \varphi _ { 2 } ( z ) \wedge \varphi _ { 3 } ( z ) \wedge \varphi _ { 4 } ( z ) ),$$

where

/negationslash

/negationslash

$$\varphi _ { 1 } ( z ) = \forall u _ { 1 } \in X \cap H _ { 1 } ( z ) \ \forall u _ { 2 } \in X \cap H _ { 1 } ( z ) \ \left ( ( u _ { 1 } \neq u _ { 2 } ) \Rightarrow \left ( ( N _ { z } ( u _ { 1 } ) \cap N _ { z } ( u _ { 2 } ) = \varnothing \right ) \\ \wedge ( N _ { z } ( u _ { 1 } ) \neq N _ { z } ( u _ { 2 } ) ) \wedge ( N _ { z } ( u _ { 1 } ) \cap H _ { 1 } ( z ) = \varnothing ) ),$$

$$\varphi _ { 2 } ( z ) = \forall x \in X \, \left ( ( x \in H _ { 1 } ( z ) ) \vee ( x \in H _ { 2 } ( z ) ) \right ),$$

$$\varphi _ { 3 } ( z ) = \forall u \in X \cap H _ { 1 } ( z ) \ ( M I N _ { z } ( u ) \Rightarrow ( N _ { z } ( u ) = ^ { * } H _ { 1 } ( z ) ) ),$$

$$\varphi _ { 4 } ( z ) = \forall u \in X \cap H _ { 1 } ( z ) \ \forall u _ { 1 } \in X \cap H _ { 1 } ( z ) \ \forall u _ { 2 } \in X \cap H _ { 1 } ( z ) \\ ( ( M I N _ { z } ( u ) \land N E X T _ { z } ( u _ { 1 }, u _ { 2 } ) ) \Rightarrow ( N _ { z } ( u _ { 2 } ) = ^ { z } N _ { z } ( u _ { 1 } ) \cdot ^ { z } N _ { z } ( u ) ) ),$$

$$M I N _ { z } ( u ) = \forall v \in X \cap H _ { 1 } ( z ) \ ( N _ { z } ( v ) \leq ^ { * } N _ { z } ( u ) ),$$

/negationslash

$$N E X T _ { z } ( u _ { 1 }, u _ { 2 } ) = ( N _ { z } ( u _ { 1 } ) < ^ { * } N _ { z } ( u _ { 2 } ) ) \wedge ( \forall v \in X \cap H _ { 1 } ( z ) \\ ( ( v \neq u _ { 2 } ) \wedge ( N _ { z } ( u _ { 1 } ) < ^ { * } N _ { z } ( v ) ) \Rightarrow ( N _ { z } ( u _ { 2 } ) < ^ { * } N _ { z } ( v ) ) ) ).$$

The formula ( A ≤ ∗ B ) expresses the property that implies the inequality | A | ≤ | B | :

/negationslash

$$( A \leq ^ { * } B ) = \exists \tilde { z } \ ( \forall x \ ( ( x \in A \ \Sigma ) \Rightarrow \exists y \ ( ( y \in B \ \Lambda ) \wedge R _ { \tilde { z } } ( x, y ) ) ) \wedge \\ ( ( x \in B \ \Lambda ) \Rightarrow ( \neg ( \exists y \ \exists \tilde { y } \ ( ( y \neq \tilde { y } ) \wedge R _ { \tilde { z } } ( x, y ) \wedge R _ { \tilde { z } } ( x, \tilde { y } ) ) ) ) ) ).$$

Denote ( A = ∗ B ) = ( A ≤ ∗ B ) ∧ ( B ≤ ∗ A ) , ( A &lt; ∗ B ) = ( A ≤ ∗ B ) ∧ ¬ ( ( A = ∗ B )) . The formula ( A = z B · z C ) expresses the property that implies the inequality | A | = | B C || | :

/negationslash

$$( A = ^ { z } B \cdot ^ { z } C ) = ( \forall a \in A \ \exists b \in B \ \exists c \in C \ ( R _ { z } ( a, b ) \wedge R _ { z } ( a, c ) \wedge \\ ( \forall \tilde { b } \in B \ ( ( b \neq \tilde { b } ) \Rightarrow ( \neg R _ { z } ( a, \tilde { b } ) ) ) ) \wedge ( \forall \tilde { c } \in C \ ( ( c \neq \tilde { c } ) \Rightarrow ( \neg R _ { z } ( a, \tilde { c } ) ) ) ) ) \wedge$$

/negationslash

/negationslash

( ∀ b ∈ B ∀ c ∈ C ∃ a ∈ A R ( z ( a, b ) ∧ R z ( a, c ) ∧ ∀ ( ˜ a ∈ A (( a = ˜) a ⇒ (( ¬ R z ( a, b ˜ )) ∨ ¬ ( R z ( a, c ˜))))))) .

Let

$$\dots Q _ { 2 } ( x _ { 1 }, \dots, x _ { k - 1 1 } ) = \forall y \ ( \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 1 } ) \geq ^ { * } \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 2 }, y ) ).$$

Let us say that vertices x , . . . , x 1 k -11 are moderate , if

$$| \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 1 } ) | = \max _ { y } | \tilde { N } ( x _ { 1 }, \dots, x _ { k - 1 2 }, y ) |.$$

Set where Σ = 4 m m +1 -m m -1 , m = ( j k -10) , j ∈ N .

$$\alpha & = \frac { 1 } { \binom { k - 1 1 } { s - 1 } } + \frac { k - 1 0 } { \binom { k - 1 1 } { s - 1 } \Sigma }, \\ 1 0 ). \ i & \in \mathbb { N }.$$

Let ˜ Ω n be the set of all hypergraphs G from Ω n which satisfy the following properties.

- 1) For any vertices x , . . . , x 1 k -11 we have | ˜ ( N x ,. . . , x 1 k -11 ) | ≤ k -11 k -10 Σ .
- 2) For any vertices x , . . . , x 1 k -12 there exists a vertex x k -11 such that | ˜ ( N x ,. . . , x 1 k -11 ) | ≥ Σ k -10 -1 .
- 3) There are no subhypergraphs with at most m m +1 vertices and density greater than 1 /α .
- 4) For any strictly balanced pair ( G,H ) such that ρ G, H ( ) &lt; 1 α and v G ( ) ≤ m m +1 , any collection of v H ( ) vertices has a ( G,H ) -extension in G .

Theorems 12 and 14 imply that Pr[ G s ( n, n -α ) ∈ ˜ Ω ] n → 1 , n →∞ .

Let a hypergraph G ∈ ˜ Ω n satisfy L . Then there exist vertices x , . . . , x 1 k -11 satisfying Q 1 ( x , . . . , x 1 k -11 ) ∧ Q 2 ( x , . . . , x 1 k -11 ) . Then x , . . . , x 1 k -11 are moderate and | ˜ ( N x ,. . . , x 1 k -11 ) | = t t +1 -t t -1 + t for some t ∈ N . If t &gt; m , then | ˜ ( N x ,. . . , x 1 k -11 ) | ≥ ( m +1) m +2 -m -1 m + m + 1 &gt; k -11 k -10 Σ which contradicts property 1) from the definition of ˜ Ω n . If t &lt; m , then | ˜ ( N x ,. . . , x 1 k -11 ) | ≤ ( m -1) m -m +1 m + m -1 &lt; Σ k -10 -1 which contradicts property 2) from the definition of ˜ Ω n . Thus t = m . Note that m predicates T z are necessary for constructing the set H 1 ( z ) , m m +1 -m m -1 predicates R z are necessary for constructing the set H 2 ( z ) and 2 m m +1 -m 2 m -1 predicates R z are necessary for representing all predicates A = z B · z C . Therefore, G contains a copy of a hypergraph G x , . . . , x ( 1 k -11 ) with k -10 + Σ vertices and ( k -11 s -1 ) Σ edges. The hypergraph G x , . . . , x ( 1 k -11 ) is strictly balanced and its density equals 1 α .

/negationslash

/negationslash

By theorem 13 the probability that G s ( n, n -α ) contains G x , . . . , x ( 1 k -11 ) for some x , . . . , x 1 k -11 tends to a constant c ∈ (0 , 1) . Therefore, lim n →∞ Pr[ G s ( n, n -α ) | = L ] = c .

Let us show that if a hypergraph G ∈ ˜ Ω n contains G x , . . . , x ( 1 k -11 ) for some x , . . . , x 1 k -11 then it satisfies L . Suppose that there exist x , . . . , x 1 k -11 such that G contains G x , . . . , x ( 1 k -11 ) . Then property 3) from the definition of ˜ Ω n implies that max y = x k -11 | ˜ ( N x ,. . . , x 1 k -12 , y ) | ≤ Σ k -10 . Therefore, ∀ y | ˜ ( N x ,. . . , x 1 k -11 ) | ≥ | ˜ ( N x ,. . . , x 1 k -12 , y ) | . The property 4) from the definition of ˜ Ω n implies ˜ ( L x , . . . , x 1 k -11 ) because we need max y = x k -11 | ˜ ( N x ,. . . , x 1 k -12 , y ) | ≤ Σ k -10 predicates R ˜ z for this. The property 4) also implies L x , . . . , x ( 1 k -11 ) because we need at most m m -1 predicates R ˜ z to represent predicates ≤ ∗ . Hence G satisfies L .

Letting j →∞ we obtain that 1 ( k -11 s -1 ) ∈ ( S k ) ′ .

Proof of theorem 11 . Let l = ( ) l k . From the conditions of the theorem it follows that l ≥ 2 if s = 2 and l ≥ s -1 if s ≥ 3 , so 1 ( l s -1 ) ∈ (0 , s -1) . Furthermore, l &lt; k -2 . Set t = k - -l 2 , then 1 ≤ t &lt; l . Let m ∈ N , α = l + m ( l -t + m ) ( l s -1 ) .

Let L be a first-order property which is expressed by the formula ∃ x 1 . . . ∃ x l Q x , . . . , x ( 1 l ) with quantifier depth k , where

$$Q ( x _ { 1 }, \dots, x _ { l } ) = Q _ { 1 } ( x _ { 1 }, \dots, x _ { l } ) \wedge ( \neg ( \exists z _ { 1 } \dots \exists z _ { t } \ ( Q _ { 2 } ( x _ { 1 }, \dots, x _ { l }, z _ { 1 }, \dots, z _ { l } ) \wedge Q _ { 3 } ( x _ { 1 }, \dots, x _ { l }, z _ { 1 }, \dots, z _ { t } ) ) ) ),$$

$$Q _ { 1 } ( x _ { 1 }, \dots, x _ { l } ) = \exists y _ { 1 } \dots \exists y _ { k - l } \left ( ( y _ { 1 } \in \tilde { N } ( x _ { 1 }, \dots, x _ { l } ) ) \wedge \dots \wedge ( y _ { k - l } \in \tilde { N } ( x _ { 1 }, \dots, x _ { l } ) ) \\ \wedge Q _ { 4 } ( x _ { 1 }, \dots, x _ { l }, y _ { 1 }, \dots, y _ { k - l } ) )$$

is a formula describing a strictly balanced s -hypergraph on vertices x , . . . , x 1 l , y 1 , . . . , y k -l which has ( l s -1 ) ( l +2) edges and contains edges of the form { y , x i i 1 , . . . , x i s -1 } , where i ∈ { 1 , . . . , k - } l and i 1 , . . . , i s -1 ∈ { 1 , . . . , l } are distinct (such an s -hypergraph exists, since ( l s -1 ) ( l + 2) ≤ ( ) k s ), and Q 4 ( x , . . . , x 1 l , y 1 , . . . , y k -l ) is a formula describing the rest ( l s -1 ) ( l +2) -( l s -1 ) ( k -l ) edges of this s -hypergraph,

$$Q _ { 2 } ( x _ { 1 }, \dots, x _ { l }, z _ { 1 }, \dots, z _ { t } ) = \forall y \left ( ( y \in \tilde { N } ( x _ { 1 }, \dots, x _ { l } ) ) \Rightarrow ( \exists v \left ( ( v \in \tilde { N } ( z _ { 1 }, \dots, z _ { t }, y, x _ { t + 2 }, \dots, x _ { l } ) \wedge \\ \bigcap _ { \{ a _ { 1 }, \dots, a _ { s - 1 } \} \subset \{ z _ { 1 }, \dots, z _ { t }, x _ { 1 }, \dots, x _ { l } \}, \{ a _ { 1 }, \dots, a _ { s - 1 } \} \cap \{ x _ { 1 }, \dots, x _ { t + 1 } \} \neq \mathcal { Z } } ( \neg N ( v, a _ { 1 }, \dots, a _ { s - 1 } ) ) ) ) \right ) ),$$

$$Q _ { 3 } ( x _ { 1 }, \dots, x _ { l }, z _ { 1 }, \dots, z _ { t } ) = \bigcap _ { i = t + 1 } ^ { l } ( \exists u \left ( ( u \in \tilde { N } ( z _ { 1 }, \dots, z _ { t }, x _ { 1 }, \dots, x _ { i - 1 }, x _ { i + 1 }, \dots, x _ { l } ) ) \wedge$$

$$\bigcap _ { \{ a _ { 1 }, \dots, a _ { s - 2 } \} \subset \{ z _ { 1 }, \dots, z _ { t }, x _ { 1 }, \dots, x _ { i - 1 }, x _ { i + 1 }, \dots x _ { i } \} } ( \neg N ( u, x _ { i }, a _ { 1 }, \dots, a _ { s - 2 } ) ). ) )$$

Note that if t = l -1 then

$$Q _ { 2 } ( x _ { 1 }, \dots, x _ { l }, z _ { 1 }, \dots, z _ { t } ) = \forall y \left ( ( y \in \tilde { N } ( x _ { 1 }, \dots, x _ { l } ) ) \Rightarrow ( \exists v \left ( ( v \in \tilde { N } ( z _ { 1 }, \dots, z _ { t }, y ) ) \wedge \\ \bigcap _ { \{ a _ { 1 }, \dots, a _ { s - 1 } \} \subset \{ z _ { 1 }, \dots, z _ { t }, x _ { 1 }, \dots, x _ { l } \}, \{ a _ { 1 }, \dots, a _ { s - 1 } \} \cap \{ x _ { 1 }, \dots, x _ { l } \} \neq \mathfrak { O } } ( \neg N ( v, a _ { 1 }, \dots, a _ { s - 1 } ) ) ) ).$$

Let ˜ Ω n be the set of all hypergraphs G from Ω n which satisfy the following properties.

- 1) For any strictly balanced pair ( G,H ) such that ρ G, H ( ) &lt; 1 α and v G ( ) ≤ 2( l + m +1) , any collection of v H ( ) vertices has a ( G,H ) -extension in G .
- 2) For any hypergraph G with ρ max ( G &gt; ) 1 α and v G ( ) ≤ 2( l + m +1) , there is no copy of G in G .

Theorems 12 and 14 imply that Pr[ G s ( n, n -α ) ∈ ˜ Ω ] n → 1 , n →∞ .

Let ˜ H be an s -hypergraph with V ( H ) = { x , . . . , x 1 l , y 1 , . . . , y k -l } and ( l s -1 ) ( l +2) edges which was determined above in defining of the formula Q 1 ( x , . . . , x 1 l ) . Let H be an s -hypergraph with a set of vertices V ( H ) = { x , . . . , x 1 l , y 1 , . . . , y m } and a set of edges

Suppose that G ∈ ˜ Ω n . Let us show that for any vertices x , . . . , x 1 l satisfying Q x , . . . , x ( 1 l ) we have | ˜ ( N x ,. . . , x 1 l ) | = m . Let ˜ ( N x ,. . . , x 1 l ) = { y , . . . , y 1 χ } . Let us prove that χ ≤ m . Suppose that χ &gt; m . Since Q 1 ( x , . . . , x 1 l ) is true, there exist k -l vertices among y , . . . , y 1 χ (w.l.o.g. y , . . . , y 1 k -l ) such that G| { x ,...,x ,y 1 l 1 ,...,y k -l } contains at least ( l s -1 ) ( l +2) = ( l s -1 ) ( k -l )+ f edges, where f = ( l -t ) ( l s -1 ) . Then the density of the subhypergraph G| { x ,...,x ,y 1 l 1 ,...,y m +1 } is at least ( l s -1 ) ( m +1)+ f l + m +1 &gt; 1 α . This contradicts property 1) from the definition of ˜ Ω n . Let us prove that χ ≥ m . Suppose that χ &lt; m . By the definition of ˜ Ω n , in G there are distinct vertices z , . . . , z 1 t , v 1 , . . . , v χ , u 1 , . . . , u l -t such that for any i ∈ { 1 , . . . , χ } we have v i ∈ ˜ ( N z , . . . , z 1 t , y i , x t +2 , . . . , x l ) and for any j ∈ { 1 , . . . , l - } t we have u j ∈ N z , . . . , z ( 1 t , x 1 , . . . , x t + j -1 , x t + +1 j , . . . , x l ) . Indeed, in this case the pair ( G| W , G| U ) , where U = { x , . . . , x 1 l , y 1 , . . . , y χ } , W = U ∪{ z , . . . , z 1 t , v 1 , . . . , v χ , u 1 , . . . , u l -t } , is strictly balanced with the density ( l -t + ) χ ( l s -1 ) l + χ &lt; ( l -t + m ) ( l s -1 ) l + m = 1 α . This contradicts Q x , . . . , x ( 1 l ) . Thus χ = m .

$$E ( H ) = \bigcup _ { i = 1 } ^ { m } \{ \{ y _ { i }, x _ { i _ { 1 } }, \dots, x _ { i _ { s - 1 } } \}, \{ i _ { 1 }, \dots, i _ { s - 1 } \} \subset \{ 1, \dots, l \} \} \cup E ( \tilde { H } ),$$

G ⊃ H be an s -hypergraph with a set of vertices V ( G ) = V ( H ) ∪ { z , . . . , z 1 t , v 1 , . . . , v m , u 1 , . . . , u l -t } and a set of edges

$$E ( G ) = E ( H ) \cup \bigcup ^ { m } \{ \{ v _ { i }, a _ { 1 }, \dots, a _ { s - 1 } \}, \{ a _ { 1 }, \dots, a _ { s - 1 } \} \subset \{ y _ { i }, z _ { 1 }, \dots, z _ { t }, x _ { t + 2 }, \dots, x _ { l } \} \} \cup$$

$$\bigcup _ { i = 1 } ^ { \dots }$$

$$\bigcup _ { i = 1 } ^ { l - t } \{ \{ u _ { i }, a _ { 1 }, \dots, a _ { s - 1 } \}, \{ a _ { 1 }, \dots, a _ { s - 1 } \} \subset \{ z _ { 1 }, \dots, z _ { t }, x _ { 1 }, \dots, x _ { t + i - 1 }, x _ { t + i + 1 }, \dots, x _ { l } \} \}.$$

Then H is strictly balanced, the pair ( G,H ) is strictly balanced and ρ H ( ) = ρ G, H ( ) = 1 α . Let ˜ L be the property that in G there exists a copy of H such that no copy of G contains it.

Let us prove that a hypergraph G ∈ ˜ Ω n satisfies L if and only if it satisfies ˜ L . Suppose that G satisfies L . Then there exist vertices x , . . . , x 1 l satisfying Q x , . . . , x ( 1 l ) . As we have shown, | ˜ ( N x ,. . . , x 1 l ) | = m . Then G| { x ,...,x 1 l }∪ ˜ ( N x ,...,x 1 l ) is isomorphic to H . The existence of a copy of G containing G| { x ,...,x 1 l }∪ ˜ ( N x ,...,x 1 l ) contradicts Q x , . . . , x ( 1 l ) . Thus G satisfies ˜ L .

Suppose that G satisfies ˜ L . Then there exists a copy of H such that no copy of G contains it. Let x , . . . , x 1 l , y 1 , . . . , y m be the vertices of this copy of H . Then ˜ ( N x ,. . . , x 1 l ) = { y , . . . , y 1 m } . Indeed, otherwise G contains a subhypergraph with m + +1 l vertices and density more than 1 /α which contradicts the definition of ˜ Ω n . Suppose that Q x , . . . , x ( 1 l ) is false. Since Q 1 ( x , . . . , x 1 l ) is true, there exist vertices z , . . . , z 1 t ∈ V ( G ) such that the predicates Q 2 ( x , . . . , x 1 l , z 1 , . . . , z t ) and Q 3 ( x , . . . , x 1 l , z 1 , . . . , z t ) are true. The predicates Q 2 ( x , . . . , x 1 l , z 1 , . . . , z t ) and Q 3 ( x , . . . , x 1 l , z 1 , . . . , z t ) imply the existence of a number r ≤ m , distinct vertices v , . . . , v 1 r , u , . . . , u 1 l -t and disjoint subsets Y , . . . , Y 1 r , Y 1 /unionsq . . . /unionsq Y r = { y , . . . , y 1 m } , such that

- 1) for any i ∈ { 1 , . . . , r } and for any y ∈ Y i we have v i ∈ ˜ ( N z , . . . , z 1 t , y, x t +2 , . . . , x l ) ,
- 2) for any j ∈ { 1 , . . . , l - } t we have u j ∈ ˜ ( N z , . . . , z 1 t , x 1 , . . . , x t + j -1 , x t + +1 j , . . . , x l ) .

Set W = { x , . . . , x 1 l , y 1 , . . . , y m } ∪ { z , . . . , z 1 t , v 1 , . . . , v r , u 1 , . . . , u l -m } . Then the density of G| W is at least

$$\frac { 2 ( l - t + m ) \binom { l } { s - 1 } - ( m - r ) \binom { l - 1 } { s - 1 } } { 2 l + m + r },$$

which is greater than 1 /α if r &lt; m . The definition of ˜ Ω n implies that r = m and G| W is a copy of G . This contradicts the property ˜ L . Therefore, Q x , . . . , x ( 1 l ) is true, and hence G satisfies L .

By proposition 1, there exists lim n →∞ Pr[ G s ( n, n -α ) | = ˜ ] = L c ∈ (0 , 1) . Since lim n →∞ Pr[ G s ( n, n -α ) ∈ ˜ Ω ] = 1 n , it follows from the above that lim n →∞ Pr[ G s ( n, n -α ) = | L ] = c. Letting m →∞ we obtain that 1 ( l s -1 ) ∈ ( S k ) ′ .

## 5 Proofs of propositions

## Proof of proposition 2 .

1) Let G , G , . . . , G , G 0 1 t be the m -decomposition of G . Set e i = ( e G , G i i -1 ) -1 , v i = v G , G ( i i -1 ) -e i ( s -1) for all i ∈ { 1 , . . . , t } . Set e 0 = e G ( ) -e G ( t ) . Note that e i ≤ m -1 , 0 ≤ v i ≤ s -2 . We have

Note that ( t + e 0 )( s -1) -∑ v i -1 ≥ ( t + e 0 )( s -1) -t ( s -2) -1 = t + e 0 ( s -1) -1 . Therefore, 1 ρ G ( ) ≤ s -1 and the equality holds if and only if e 0 = 0 , t = 1 and v 1 = s -2 . Hence either G is a cyclic m -extension of ( { x , } ∅ ) and 1 ρ max ( G ) = s -1 or 1 ρ G ( ) &lt; s -1 .

$$\intertext { \ a v e } \frac { 1 } { \rho ( G ) } & = \frac { \sum _ { i = 1 } ^ { t } ( e _ { i } ( s - 1 ) + v _ { i } ) + 1 } { \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } } = s - 1 - \frac { ( t + e _ { 0 } ) ( s - 1 ) - \sum v _ { i } - 1 } { \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } }. \\ \intertext { \ a v e t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a c t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h b a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a s t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h c t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t a t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t a a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h b t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h o t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t H a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a T h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h b e t a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h A t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t i a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a e t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a a a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h a t h$$

Suppose that 1 ρ G ( ) &lt; s -1 . Then

$$\frac { 1 } { \rho ( G ) } = s - 1 - \frac { 1 } { \tau }, \quad \text{where} \quad \tau = \frac { \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } } { ( t + e _ { 0 } ) ( s - 1 ) - \sum v _ { i } - 1 }. \\ G ) < \frac { m } { m \ell = 1 \llcorner - 1 }, \, \tau \geq m. \, \text{We have } \tau = m + \frac { a } { k }, \, \text{where}$$

Since ρ G ( ) &lt; m m s ( -1) -1 , τ ≥ m . We have τ = m + a b , where

$$a = \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } - m ( s - 1 ) ( e _ { 0 } + t ) + m \left ( \sum v _ { i } + 1 \right ), \ \ b = ( t + e _ { 0 } ) ( s - 1 ) - \sum v _ { i } - 1.$$

Since e i ≤ m -1 and v i ≤ s -2 , we obtain a ≤ mt + e 0 -m s ( -1)( e 0 + ) + t m s (( -2) t +1) ≤ m -e 0 ( m s ( -1) -1) ≤ m.

Let H ⊂ G ρ G , ( ) &lt; ρ H ( ) &lt; m m s ( -1) -1 . Let v = v G ( ) -v H ( ) , e = ( e G ) -e H ( ) . Then where

$$\frac { 1 } { \rho ( H ) } = \frac { \sum _ { i = 1 } ^ { t } ( e _ { i } ( s - 1 ) + v _ { i } ) + 1 - v } { \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } - e } = s - 1 - \frac { 1 } { \tau ^ { \prime } }, \\.$$

$$\tau ^ { \prime } & = \frac { \sum _ { i = 1 } ^ { t } e _ { i } + t + e _ { 0 } - e } { ( t + e _ { 0 } ) ( s - 1 ) - \sum v _ { i } - 1 + v - e ( s - 1 ) }. \\ \frac { m } { \cdot - 1 ) - 1 }, \, \tau ^ { \prime } & \geq m. \, \text{We have } \tau ^ { \prime } = m + \frac { a ^ { \prime } } { b ^ { \prime } }, \, \text{where}$$

Since ρ H ( ) &lt; m m s ( -1) -1 , τ ′ ≥ m . We have τ ′ = m + a ′ b ′ , where

$$a ^ { \prime } = a + e ( m ( s - 1 ) - 1 ) - m v, \ \ b ^ { \prime } = b + v - e ( s - 1 ).$$

Since G is connected, v ≤ e s ( -1) . Therefore, b ′ ≤ b . Since ρ G ( ) &lt; ρ H ( ) , we have a ′ b ′ ≤ a b and a ′ &lt; a ≤ m . So we obtain that 1 ρ H ( ) = s -1 -1 m a /b + ′ ′ , where a ′ ≤ m .

2) Let G , G , . . . , G , G 0 1 t be the m -decomposition of a hypergraph G ∈ H m . Then 1 ρ G ( ) = s -1 -1 τ , where

$$\tau \leq \frac { m t } { t ( s - 1 ) - t ( s - 2 ) - 1 } = \frac { m t } { t - 1 }.$$

Note that | V ( G ) | ≤ t ( m -1)( s -1)+ ( t s -2)+1 . Therefore, if | V ( G ) | ≥ l ( m -1)( s -1)+ ( l s -2)+1 , then 1 ρ G ( ) ≤ s - -1 l -1 ml . For any ρ &lt; m m s ( -1) -1 , there exists l = ( ) l ρ such that s - -1 l -1 ml &lt; 1 /ρ . Then ρ G ( ) &gt; ρ for any G ∈ H m with | V ( G ) | ≥ l ( ρ )(( m -1)( s -1)+( s -2))+1 . Since v G ( i +1 ) -v G ( i ) ≤ ( m -1)( s -1)+ s -2 , any hypergraph H ∈ H m with at least ( ( l ρ ) + 1)(( m -1)( s -1)+( s -2)) + 1 vertices contains a subhypergraph H ′ ∈ H m with v H ( ′ ) ∈ { l ( ρ )(( m -1)( s -1) + ( s -2)) + 1 , . . . , ( ( l ρ )+1)(( m -1)( s -1)+( s -2))+1 } . Therefore, η = η ρ ( ) = ( ( l ρ )+1)(( m -1)( s -1)+( s -2))+1 satisfies the statement of proposition.

Proof of proposition 3 . Consider a pair ( ˜ G ∪ ˜ H,G ˜ ) , where V ( ˜ ) H ∩ V ( ˜ ) G = { x } , V ( ˜ ) H = { x, y 1 , . . . , y m s ( -1) } ,

$$E ( \tilde { H } ) = \{ \{ x, y _ { 1 }, \dots, y _ { s - 1 } \} \} \cup \{ \{ y _ { i ( s - 1 ) }, \dots, y _ { ( i + 1 ) ( s - 1 ) } \} \colon 1 \leq i < m \}.$$

Then ρ G ( ˜ ∪ ˜ H,G ˜ ) = 1 s -1 and ( ˜ G ∪ ˜ H,G ˜ ) is 1 /ρ -safe. Since G is ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparse, there exists a subhypergraph G 1 ⊂ G such that G 1 is an exact ( ˜ G ∪ ˜ H,G ˜ ) -extension of ˜ G and ( G , G 1 ˜ ) is ( K ,K 1 2 ) -maximal in G for all ( K ,K 1 2 ) ∈ K ρ . Then there exists a vertice y ∈ V ( G 1 ) such that d G 1 ( y, G ˜ ) = m . Moreover, G 1 \ ( ˜ G \ { x } ) is a path which connects x and y and has m edges and m s ( -1) + 1 vertices. Since ( G , G 1 ˜ ) is ( K ,K 1 2 ) -maximal in G for all ( K ,K 1 2 ) ∈ K ρ , there does not exist a path P ′ = P which connects y with a vertex from ˜ G and has at most m edges.

/negationslash

Proof of proposition 4 . Let X i and Y i be the hypergraphs chosen in the i -th round by Spoiler and Duplicator respectively. We denote vertices which are chosen in the first i rounds in X i and Y i by x , . . . , x 1 i i i and y , . . . , y 1 i i i .

Let i rounds be finished, where 1 ≤ i ≤ k -s + 2 . Let r ∈ { 1 , . . . , i } . Let ˜ X ,.. . , X 1 i ˜ r i ⊂ X i and ˜ Y 1 i , . . . , Y ˜ r i ⊂ Y i be subhypergraphs of X i and Y i respectively. We say that ˜ X ,.. . , X 1 i ˜ r i and ˜ Y 1 i , . . . , Y ˜ r i are ( k, i, r ) -regular equivalent in ( X , Y i i ) , if the following properties hold.

- (I) x , . . . , x 1 i i i ∈ V ( ˜ X 1 i ∪ . . . ∪ ˜ X r i ) , y , . . . , y 1 i i i ∈ V ( ˜ Y 1 i ∪ . . . ∪ ˜ Y r i ) .
- (II) For any distinct j 1 , j 2 ∈ { 1 , . . . , r } , the inequalities d X i ( ˜ X j 1 i , X ˜ j 2 i ) &gt; 2 k - -i s +2 , d Y i ( ˜ Y j 1 i , Y ˜ j 2 i ) &gt; 2 k - -i s +2 hold.
- (III) For any j ∈ { 1 , . . . , r } , there is no cyclic 2 k - -i s +2 -extension of ˜ X j i in the hypergraph X i and there is no cyclic 2 k - -i s +2 -extension of ˜ Y j i in the hypergraph Y i .
- (IV) Cardinalities of the sets V ( ˜ X 1 i ∪ . . . ∪ ˜ X r i ) and V ( ˜ Y 1 i ∪ . . . ∪ ˜ Y r i ) are at most η ρ ( )+( i -1)2 k -s +1 .
- (V) The hypergraphs ˜ X j i and ˜ Y j i are isomorphic for any j ∈ { 1 , . . . , r } and there exists a corresponding isomorphism (one for all these pairs of hypergraphs) which maps the vertices x l i to the vertices y l i for all l ∈ { 1 , . . . , i } .

The main idea of Duplicator's strategy is the following. Duplicator should play in such way that after i rounds, where 1 ≤ i ≤ k -s +2 , there exist a number r ∈ { 1 , . . . , i } and ( k, i, r ) -regular equivalent hypergraphs ˜ X ,.. . , X 1 i ˜ r i ⊂ X i and ˜ Y 1 i , . . . , Y ˜ r i ⊂ Y i .

/negationslash

Let us describe Duplicator's strategy in the first round. By virtue of lemma 1 and ( n 1 ( ρ , n ) 2 ( ρ , ) n , n 3 4 ) -sparseness of X 1 it does not contain any hypergraph H ∈ H 2 k -s +1 with v H ( ) ≥ η ρ ( ) . Let ˜ X 1 1 be the subhypergraph of X 1 with maximum number of vertices such that x 1 1 ∈ ˜ X 1 1 and ˜ X 1 1 ∈ H 2 k -s +1 . Then v X ( ˜ 1 1 ) &lt; η ρ ( ) &lt; n 1 ( ρ ) . Since X 1 is ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparse, the density ρ X ( ˜ 1 1 ) ≤ ρ . Proposition 2 implies that ρ X ( ˜ 1 1 ) = ρ , since ρ / ∈ Q k . Therefore, ρ X ( ˜ 1 1 ) &lt; ρ and by the property of ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparseness Y 1 contains a induced subhypergraph ˜ Y 1 1 which is isomorphic to ˜ X 1 1 and ( K ,K 1 2 ) -maximal in Y 1 for all ( K ,K 1 2 ) ∈ K ρ . Let ϕ 1 : ˜ X 1 1 → ˜ Y 1 1 be an isomorphism. Then Duplicator chooses the vertex y 1 1 = ϕ 1 ( x 1 1 ) . Since ˜ Y 1 1 is ( K ,K 1 2 ) -maximal in Y 1 for all ( K ,K 1 2 ) ∈ K ρ , there is no cyclic 2 k -s +1 -extension of ˜ Y 1 1 in Y 1 . Therefore, ˜ X 1 1 and ˜ Y 1 1 are ( k, 1 1) , -regular equivalent.

Let i rounds be finished, where 1 ≤ i ≤ k -s +1 . Let us describe Duplicator's strategy in the ( i +1) -th round. If X i +1 = X i , then set ˜ X j i +1 = ˜ X j i , ˜ Y j i +1 = ˜ Y j i . Otherwise, set ˜ X j i +1 = ˜ Y j i , ˜ Y j i +1 = ˜ X j i . Let ϕ i +1 : ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 → ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 be an isomorphism such that ϕ i +1 ( ˜ X j i +1 ) = ˜ Y j i +1 for all j ∈ { 1 , . . . , r } and ϕ i +1 ( x l i +1 ) = y l i +1 for all l ∈ { 1 , . . . , i } .

Consider three cases.

- 1) Spoiler chooses a vertex x i +1 i +1 ∈ V ( ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) . Then Duplicator chooses y i +1 i +1 = ϕ i +1 ( x i +1 i +1 ) . Obviously, hypergraphs ˜ X 1 i +1 , . . . , X ˜ r i +1 and ˜ Y 1 i +1 , . . . , Y ˜ r i +1 are ( k, i + 1 , r ) -regular equivalent.

/negationslash

2) Spoiler chooses a vertex x i +1 i +1 / V ∈ ( ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) such that d X i +1 ( x i +1 i +1 , X ˜ 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) ≤ 2 k - -i s +1 . Then by (II) there exists exactly one j ∈ { 1 , . . . , r } such that d X i +1 ( x i +1 i +1 , X ˜ j i +1 ) ≤ 2 k - -i s +1 . By (III) there exists exactly one path C X i +1 of length at most 2 k - -i s +1 connecting x i +1 i +1 with a vertex from ˜ X j i +1 . Let ˜ x j i +1 be the vertex of C X i +1 belonging to ˜ X j i +1 . (III) also implies that v C ( X i +1 ) = e C ( X i +1 )( s -1) + 1 (otherwise C X i +1 gives a cyclic 2 k - -i s +2 -extension of ˜ X j i +1 ). By (IV) | V ( ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 ) | ≤ η ρ ( ) + ( i -1)2 k -s +1 ≤ n 2 ( ρ ) . Therefore, by Proposition 3 there exist a vertex y i +1 i +1 ∈ Y i and a path C Y i +1 ⊂ Y i such that d Y i +1 ( y i +1 i +1 , Y ˜ 1 i +1 ∪ . . . ∪ ˜ Y r i +1 ) = d X i +1 ( x i +1 i +1 , X ˜ 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) , C Y i +1 is isomorphic to C X i +1 and connects y i +1 i +1 with ϕ i +1 (˜ x j i +1 ) and there does not exist any path C ′ ⊂ Y i +1 , C ′ = C Y i +1 , such that C ′ connects y i +1 i +1 with a vertex from ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 and e C ( ′ ) ≤ e C ( Y i +1 ) . Then there exists an isomorphism C X i +1 ∪ ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 → C Y i +1 ∪ ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 which maps the vertices x 1 i +1 , . . . , x i +1 i +1 to y 1 i +1 , . . . , y i +1 i +1 respectively. Redefine the hypergraphs ˜ X j i +1 , ˜ Y j i +1 : ˜ X j i +1 = ˜ X j i +1 ∪ C X i +1 , ˜ Y j i +1 = ˜ Y j i +1 ∪ C Y i +1 . Then ˜ X 1 i +1 , . . . , X ˜ r i +1 and ˜ Y 1 i +1 , . . . , Y ˜ r i +1 satisfy (I) and (V). Let us prove that properties (II), (III), (IV) are also satisfied.

/negationslash

Show that (II) holds. It is sufficient to show that d X i +1 ( ˜ X j i +1 , X ˜ j 2 i +1 ) &gt; 2 k - -i s +1 and d Y i +1 ( ˜ Y j i +1 , Y ˜ j 2 i +1 ) &gt; 2 k - -i s +1 for any j 2 = j . Suppose that d X i +1 ( ˜ X j i +1 , X ˜ j 2 i +1 ) ≤ 2 k - -i s +1 . Then there exists a vertex u ∈ V ( C X i +1 ) such that d X i +1 ( u, X ˜ j 2 i +1 ) ≤ 2 k - -i s +1 . Hence d X i +1 ( ˜ X j i +1 \ ( C X i +1 \ { ˜ x j i +1 } ) , X ˜ j 2 i +1 ) ≤ 2 k - -i s +2 . This contradicts the fact that ˜ X ,.. . , X 1 i ˜ r i and ˜ Y 1 i , . . . , Y ˜ r i satisfy (II). Therefore, d X i +1 ( ˜ X j i +1 , X ˜ j 2 i +1 ) &gt; 2 k - -i s +1 . The inequality d Y i +1 ( ˜ Y j i +1 , Y ˜ j 2 i +1 ) &gt; 2 k - -i s +1 is proved analogously.

Show that (III) holds. It is sufficient to show that there is no cyclic 2 k - -i s +1 -extension of ˜ X j i +1 in X i +1 and there is no cyclic 2 k - -i s +1 -extension of ˜ Y j i +1 in Y i +1 . Suppose that there exists W ⊂ X i +1 which is a cyclic 2 k - -i s +1 -extension of ˜ X j i +1 . Then e W,X ( ˜ j i +1 \ ( C X i +1 \ { ˜ x j i +1 } )) ≤ 2 k - -i s +2 and there exists a subhypergraph W ′ ⊂ W which is a cyclic 2 k - -i s +2 -extension of ˜ X j i +1 \ ( C X i +1 \ { ˜ x j i +1 } ) . This contradicts the fact that ˜ X ,.. . , X 1 i ˜ r i and ˜ Y 1 i , . . . , Y ˜ r i satisfy (III). Therefore, there is no cyclic 2 k - -i s +1 -extension of ˜ X j i +1 in X i +1 . The non-existence of cyclic 2 k - -i s +1 -extensions of ˜ Y j i +1 in Y i +1 is proved analogously.

Show that (IV) holds. We have

$$| V ( \tilde { X } ^ { 1 } _ { i + 1 } \cup \dots \cup \tilde { X } ^ { r } _ { i + 1 } ) | \leq | V ( \tilde { X } ^ { 1 } _ { i } \cup \dots \cup \tilde { X } ^ { r } _ { i } ) | + 2 ^ { k - i - s + 1 } \leq \eta ( \rho ) + i 2 ^ { k - s + 1 },$$

therefore, (IV) holds.

Let us prove that ˜ X 1 i +1 , . . . , X ˜ r +1 i +1 and ˜ Y 1 i +1 , . . . , Y ˜ r +1 i +1 satisfy (I)-(V). Obsiously, (I) and (V) hold.

3) Spoiler chooses a vertex x i +1 i +1 ∈ X i +1 such that d X i +1 ( x i +1 i +1 , X ˜ 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) &gt; 2 k - -i s +1 . Let ˜ X r +1 i +1 be the subhypergraph of X i +1 with maximum number of vertices such that x i +1 i +1 ∈ ˜ X r +1 i +1 and ˜ X r +1 i +1 ∈ H 2 k - -i s +1 . By Proposition 2 either ˜ X r +1 i +1 is a cyclic 2 k - -i s +1 -extension of ( { x i +1 i +1 } , ∅ ) with 1 /ρ X ( ˜ r +1 i +1 ) = s -1 or 1 /ρ X ˜ ( r +1 i +1 ) = s -1 -1 2 k - -i s +1 + a/b , where a, b ∈ N , a ≤ 2 k - -i s +1 . Note that s -1 -1 2 k - -i s +1 + a/b ≤ s -1 -1 2 k - -i s +2 ≤ s -1 -1 2 k -s +1 &lt; /ρ 1 . Since X i +1 is ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparse, we obtain that ˜ X r +1 i +1 is a cyclic 2 k - -i s +1 -extension of { x i +1 i +1 } and 1 /ρ X ( ˜ r +1 i +1 ) = s -1 . By (IV) | V ( ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 ) | ≤ η ρ ( ) + ( i -1)2 k -s +1 ≤ n 2 ( ρ ) . Therefore, by Proposition 3 there exists a vertex y i +1 i +1 ∈ Y i +1 such that d Y i +1 ( y i +1 i +1 , Y ˜ 1 i +1 ∪ . . . ∪ ˜ Y r i +1 ) = 2 k - -i s +1 + 1 . Since Y i is ( n 1 ( ρ , n ) 2 ( ρ , n ) 3 , n 4 ) -sparse, there exists a subhypergraph ˜ Y r +1 i +1 ⊂ Y i +1 such that ˜ Y r +1 i +1 is an exact ( ˜ X r +1 i +1 , ( { x i +1 i +1 } , ∅ )) -extension of ( { y i +1 i +1 } , ∅ ) and ˜ Y r +1 i +1 is ( K ,K 1 2 ) -maximal in Y i +1 for all ( K ,K 1 2 ) ∈ K ρ .

Show that (II) holds. It is sufficient to show that d X i +1 ( ˜ X r +1 i +1 , X ˜ j i +1 ) &gt; 2 k - -i s +1 and d Y i +1 ( ˜ Y r +1 i +1 , Y ˜ j i +1 ) &gt; 2 k - -i s +1 for any j ∈ { 1 , . . . , r } . Suppose that d X i +1 ( ˜ X r +1 i +1 , X ˜ j i +1 ) ≤ 2 k - -i s +1 . Then there exists a vertex u ∈ V ( ˜ X r +1 i +1 ) such that d X i +1 ( u, X ˜ j i +1 ) ≤ 2 k - -i s +1 . Note that ˜ X r +1 i +1 ∩ ˜ X j i +1 = ∅ , since d X i +1 ( x, X ˜ 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) &gt; 2 k - -i s +1 . Since ˜ X r +1 i +1 is a cyclic 2 k - -i s +1 -extension of ( { x i +1 i +1 } , ∅ ) , ˜ X r +1 i +1 ∩ ˜ X j i +1 = ∅ and d X i +1 ( u, X ˜ j i +1 ) ≤ 2 k - -i s +1 , we obtain that there exists a cyclic 2 k - -i s +2 -extension of ˜ X j i +1 in X i +1 . This is a contradiction. Therefore, d X i +1 ( ˜ X r +1 i +1 , X ˜ j i +1 ) &gt; 2 k - -i s +1 . The inequality d Y i +1 ( ˜ Y r +1 i +1 , Y ˜ j i +1 ) &gt; 2 k - -i s +1 is proved analogously.

Show that (III) holds. It is sufficient to show that there is no cyclic 2 k - -i s +1 -extension of ˜ X r +1 i +1 in X i +1 and there is no cyclic 2 k - -i s +1 -extension of ˜ Y r +1 i +1 in Y i +1 . By the definition of ˜ X r +1 i +1 there is no 2 k - -i s +1 -extension of ˜ X r +1 i +1 in X i +1 . The hypergraph ˜ Y r +1 i +1 does not contain any 2 k - -i s +1 -extension of ˜ Y r +1 i +1 , since ˜ Y r +1 i +1 is ( K ,K 1 2 ) -maximal in Y i +1 for all ( K ,K 1 2 ) ∈ K ρ .

Show that (IV) holds. We have

$$| V ( \tilde { X } _ { i + 1 } ^ { 1 } \cup \dots \cup \tilde { X } _ { i + 1 } ^ { r + 1 } ) | \leq | V ( \tilde { X } _ { i } ^ { 1 } \cup \dots \cup \tilde { X } _ { i } ^ { r } ) | + 2 ^ { k - i - s + 1 } \leq \eta ( \rho ) + i 2 ^ { k - s + 1 },$$

therefore, (IV) holds.

After k -s + 2 rounds we have vertices x 1 k -s +2 , . . . , x k -s +2 k -s +2 ∈ X k -s +2 , y 1 k -s +2 , . . . , y k -s +2 k -s +2 ∈ Y k -s +2 and hypergraphs ˜ X 1 k -s +2 , . . . , X ˜ r k -s +2 , ˜ Y 1 k -s +2 , . . . , Y ˜ r k -s +2 satisfying (I)-(V).

Let us describe the strategy of Duplicator in the ( i +1) -th round, where k -s +2 ≤ i ≤ k -1 . If X i +1 = X k -s +2 , then set ˜ X j i +1 = ˜ X j k -s +2 , ˜ Y j i +1 = ˜ Y j k -s +2 . Otherwise, set ˜ X j i +1 = ˜ Y j k -s +2 , ˜ Y j i +1 = ˜ X j k -s +2 . Let ϕ i +1 : ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 → ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 be an isomorphism such that ϕ i +1 ( ˜ X j i +1 ) = ˜ Y j i +1 for all j ∈ { 1 , . . . , r } and ϕ i +1 ( x l i +1 ) = y l i +1 for all l ∈ { 1 , . . . , k -s + 2 } . If Spoiler chooses a vertex x i +1 i +1 ∈ V ( ˜ X 1 i +1 ∪ . . . ∪ ˜ X r i +1 ) , then Duplicator chooses y i +1 i +1 = ϕ i +1 ( x i +1 i +1 ) . Otherwise, Duplicator chooses an arbitrary vertex y i +1 i +1 / V ∈ ( ˜ Y 1 i +1 ∪ . . . ∪ ˜ Y r i +1 ) .

/negationslash

Let us show that Duplicator wins, i.e., the hypergraphs X k | { x ,...,x 1 k k k } and Y k | { y 1 k ,...,y k k } are isomorphic. Since x , . . . , x 1 k k -s +2 k ∈ V ( ˜ X 1 k ∪ . . . ∪ ˜ X r k ) and y , . . . , y 1 k k -s +2 k ∈ V ( ˜ Y 1 k ∪ . . . ∪ ˜ Y r k ) , the hypergraphs X k | { x ,...,x 1 k k -s +2 k } and Y k | { y 1 k ,...,y k -s +2 k } are isomorphic. Let us show that for any u , . . . , u 1 l ∈ { x k -s +3 k , . . . , x k k } \ V ( ˜ X 1 k ∪ . . . ∪ ˜ X r k ) , where l ≥ 1 , there are no vertices v , . . . , v 1 s -l ∈ V ( ˜ X 1 k ∪ . . . ∪ ˜ X r k ) such that { u , . . . , u 1 l , v 1 , . . . , v s -l } ∈ E X ( k ) . Suppose the contrary. We have s - ≥ l 2 . Let v 1 ∈ ˜ X j 1 k , v 2 ∈ ˜ X j 2 k . If j 1 = j 2 , then the edge { u , . . . , u 1 l , v 1 , . . . , v s -l } gives 1 -extension of ˜ X j 1 k which contradicts (II). If j 1 = j 2 , then the existence of the edge { u , . . . , u 1 l , v 1 , . . . , v s -l } implies that d X k ( ˜ X j 1 k , X ˜ j 2 k ) ≤ 1 which contradicts (III). Therefore, X k | { x ,...,x 1 k k k } has no edge containing at least one vertice from V ( X k ) \ V ( ˜ X 1 k ∪ . . . ∪ ˜ X r k ) (and the same is true for Y k | { y 1 k ,...,y k k } ). Hence X k | { x ,...,x 1 k k k } and Y k | { y 1 k ,...,y k k } are isomorphic.

## Acknowledgements

This work has been supported by the RSF project 16-11-10014.

## References

- [1] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1: 97-115, 1988.
- [2] J.H. Spencer, Ininite spectra in the first order theory of graphs, Combinatorica 10(1): 95-102, 1990.
- [3] M.E. Zhukovskii, Zero-one k-law, Discrete Mathematics, 2012, 312: 1670-1688.
- [4] M.E. Zhukovskii, Extension of the zero-one k-law, Doklady Mathematics, 89(1): 16-19, 2014. (Russian original: Doklady Akademii Nauk, 454(1): 23-26, 2014).
- [5] M.E. Zhukovskii, The largest critical point in the zero-one k -law, Sb. Math., 206(4): 489-509, 2015.
- [6] Spencer, J., Zhukovskii, M. E. Bounded quantifier depth spectra for random graphs. Discrete Mathematics, 339(6), 1651-1664, 2016.
- [7] M. E. Zhukovskii, On infinite spectra of first order properties of random graphs, arXiv:1609.01115
- [8] M.E. Zhukovskii, The spectra of first-order formulae having low quantifier rank, Russian Mathematical Surveys, 70(6): 1176-1178, 2015. (Russian original: Russian Mathematical Surveys, 70(6): 209-210, 2015).

| [9]   | J. H. Spencer, The Strange Logic of Random Graphs, Number 22 in Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.                                        |
|-------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [10]  | M.E. Zhukovskii, A.M. Raigorodskii, Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys (2015), 70(1): 33.                           |
| [11]  | H.D. Ebbinghaus and J. Flum. Finite model theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, second edition, 1999.                                |
| [12]  | A. Matushkin, Zero-one law for random uniform hypergraphs, arXiv:1607.07654.                                                                                        |
| [13]  | S.N. Popova, Infinite spectra of first-order properties for random hypergraphs, Problems of Information Transmission, 54(3): 281-289, 2018.                         |
| [14]  | A.G. Vantsyan, The evolution of random uniform hypergraphs, Probabilistic problems in discrete mathematics, 126-131, Moscov. Inst. Electron. Machinostroenya, 1987. |
| [15]  | S. Janson, T. /suppress L uczak, A. Rucinski, Random Graphs, New York, Wiley, 2000.                                                                                 |
| [16]  | N. Alon and J.H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 2000.                                                                             |
| [17]  | M.E. Zhukovskii, Estimation of the number of maximal extensions in a random graph, Discrete Mathematics and Applications, 22:1, 55-90, 2012.                        |
| [18]  | A. Ehrenfeucht, An application of games to the completness problem for formalized theories, Warszawa, Fund. Math., 49: 121-149, 1960.                               |
Svetlana Popova
Spectrum for first-order properties of random hypergraphs
The notion of spectrum of first-order properties introduced by J. Spencer for
Erdos-Renyi random graph is considered in relation to random uniform
hypergraphs. We study properties of spectrum for first-order formulae with
bounded quantifier depth and estimate the values of minimum and maximum points
of this spectrum. We also consider the set of limit points of the spectrum and
give a bound for its minimum value.