Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2014/Program2/zhukovskii_summary.pdf Дата изменения: Tue Oct 14 11:31:12 2014 Дата индексирования: Sun Apr 10 16:04:34 2016 Кодировка: Поисковые слова: molecular cloud

SUMMARY

Zhukovskii Maksim Evgenievich

We study an asymptotical behaviour of first order properties of the Erd Rґ yi os­ en random graph G(n, p). The random graph obeys the zero-one law if for each firstorder property L either its probability tends to 0 or tends to 1. The random graph obeys the zero-one k -law if for each property L which can be expressed by first-order formula with quantifier depth at most k either its probability tends to 0 or tends to 1. Zero-one laws were proved for different classes of functions p = p(n). The class {p = n- , > 0} is at the top of interest. In 1988 S. Shelah and J.H. Spencer proved that the random graph G(n, n- ) obeys zero-one law if > 0 is irrational. If is rational, 0 < 1 then G(n, n- ) does not obey the zero-one law. Let us denote the set of all first order properties and the set of all first order properties expressed by formulae with quantifier depth at most k by L and Lk respectively. For any L L we consider the set S1 (L) of (0, 1) such that Pn,n- (L) either does not converges or its limit is not zero or one. For any L L we also consider the set S2 (L) of (0, 1) which does not satisfy the following property. There exist {0, 1} and > 0 such that for any n-- < p < n-+ k k equality limn Pn,p (L) = holds. Set S1 = LLk S1 (L), S2 = LLk S2 (L). 1 Recently I proved that if (0, k-2 ) then the random graph G(n, n- ) obeys 1 1 zero-one law. Moreover, k-2 Sk . From this result it follows that the minimal 1 k k number in S1 equals k-2 . I also obtained the maximal number in S1 . Consider set Q of all positive rational numbers with the numerator less than or equal to 2k-1 . I also proved that the random graph G(n, n- ) obeys the zero-one k -law if k = 1- 2k-1 + , (0, )\Q. Moreover, 1- 2k-1 + S1 for any {1, ..., 2k-1 -2}. 1 1 If {1 - 21k , 1 - 2k1 1 } then the random graph G(n, n- ) obeys the zero-one k -law - 1 as well. So, the maximal number in Sk equals 1 - 2k1 2 . - 1 2 J.H. Spencer in 1990 proved that sets Sk and Sk are infinite when k is large 1 2 enough. Moreover, in 1991 he proved that all limit points of Sk and Sk are apk proached only from above (in other words, the set S2 is well-ordered under >). At the present time in our joint work with J.H. Spencer we receive some new results: 2 find the maximal and the minimal numbers in Sk ; estimate the maximal and the 1 2 minimal limit points in Sk and Sk ; for each j {1, 2} estimate the minimal k such j that Sk is infinite. In future, for each j {1, 2} I am going to find the the exact values of the j maximal and the minimal limit points in Sk and find the exact value of the minimal j 1 2 k such that Sk is infinite. Moreover, I want to find the number of values in Sk , Sk j near there minimal and maximal values. In other words, if the sets Sk 0, k-12.5 , j Sk 1 - 2k1 1 , 1 , j {1, 2}, are finite, I'm going to find its power. I want to - prove zero-one k -laws for G(n, n- ) for new sets of rational (especially, for small k ). Finally, I am going to investigate zero-one laws and zero-one k -laws for random uniform hypergraphs (all edges of the complete hypergraph appear in the random graph with probability p mutually independently).

1