tailieunhanh - Báo cáo toán học: "The Tenacity of Zero-One Laws"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The Tenacity of Zero-One Laws. | The Tenacity of Zero-One Laws Joel H. Spencer Courant Institute New York University 251 Mercer Street New York NY 10012 spencer@ Katherine St. John Dept of Math Computer Science Graduate Center Lehman College City University of New York Bronx NY 10468 stjohn@ Submitted 9 March 2000 Revised 6 August 2000 1 Abstract The Ehrenfeucht-Fraisse game is a two-person game of perfect information which is connected to the Zero-One Laws of first order logic. We give bounds for roughly how quickly the Zero-One Laws converge for random bit strings and random circular bit sequences. We measure the tenaciousness of the second player Duplicator in playing the Ehrenfeucht-Fraisse game by bounding the numbers of moves Duplicator can play and win with probability 1 e. We show that for random bit strings and random circular sequences of length n generated with a low probability p n-1 the number of moves Te n is 0 log2 n . For random bit strings and circular sequences with isolated ones n-1 p n-1 2 Te n ơ min log2 np log2 np2 . For n-1 2 p and 1 p n-1 2 we show that Te n O log n for random circular sequences where log n has the usual definition-the least number of times you iteratively apply the logarithm to get a value less than one. 2 Introduction In this paper we examine the Ehrenfeucht-Fraisse game and the length of such games over random structures for which a Zero-One Law holds. Assume Mn is a random structure on n elements. For example it could be the binary tree with n leaves under uniform probability the random graph of Erdos and Renyi 4 or the random bit string on n bits. In a general setting a random structure defined for all n and fixing positive e we define the tenacity function Te n equal to the maximal k so that if n1 n2 n then Duplicator wins this k-move Ehrenfeucht-Fraisse game played on independent structures of size n1 and n2 with probability at least 1 e. A Zero-One Law holds if for every first THE ELECTRONIC JOURNAL OF COMBINATORICS 8 no. 2