Premium
Improved boolean formulas for the Ramsey graphs
Author(s) -
Savický Petr
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060404
Subject(s) - mathematics , combinatorics , discrete mathematics , ramsey's theorem , property (philosophy) , exponential function , probabilistic logic , graph , statistics , mathematical analysis , philosophy , epistemology
In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well‐known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd 2 log d , where d is a polynomial in n , and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1} n of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log 2 d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.