Joel H. Spencer, Katherine St. John
We give a complete characterization for the limit probabilities of first order sentences over sparse random bit strings at the threshold of adjacency. For strings of length n, we let the probability...
The complexity of random ordered structures (2009)
Joel H. Spencer, Katherine St. John
Replace this file with prentcsmacro.sty for your meeting, or with entcsmacro.sty for your meeting. Both can be
A Wiley-Interscience Publication (2008)
Noga Alon, Joel H. Spencer, John Wiley, To Nurit, Mary Ann
The Probabilistic Method has recently been developed intensively and became one of the most powerful and widely used tools applied in Combinatorics. One of the major reasons for this rapid...
The complexity of random ordered structures (2008)
St. John, Joel H. Spencer, Joel H. Spencer, Katherine St. John
Abstract. We show that for random bit strings, Up(n), with probability, p = 1 2, the first-order quantifier depth D(Up(n)) needed to distinguish non-isomorphic structures is Θ(lg lg n), with high...
The tenacity of zero-one laws (2008)
Joel H. Spencer, Katherine St. John
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...
Brian Borchers, Jan Korst, Simulated Annealing, Thomas L. Magnanti, As Noga Alon, ...
I've compiled this list of books on combinatorial optimization and integer programming as a source of additional reading and project ideas for students in my graduate course in combinatorial...
The tenacity of zero-one laws (2007)
Joel H. Spencer, Katherine St. John
The Ehrenfeucht-Fraisse game is a two-person game of perfect information which is connected to the Zero-One Laws of rst order logic. We give bounds for roughly how quickly the Zero-One Laws converge...
Jerey C. Lagarias, Joel H. Spencer, Jade P. Vinson
Let u n be the number of ways to divide the unit square into dyadic rectangles of area 2 n
A CHARACTERIZATION OF CLIQUE GRAPHS (2005)
Roberts, Fred S., Spencer, Joel H.
A graph-theoretic discussion following up a recent paper in which Hamelink obtains an interesting sufficient condition for a graph to be a clique graph. In the present study related conditions are...
Joel H. Spencer, Katherine St. John
Let U n;p be the random unary predicate and T k the almost sure first-order theory of U n;p under the linear ordering, where k is a positive integer and n \Gamma1=k p(n) n
Joel H. Spencer, Katherine St. John
Let Un,p be the random unary predicate and Tk the almost sure first-order theory of Un,p under the linear ordering, where k is a positive integer and n −1/k ≪ p(n) ≪ n −1/(k+1). For each k,...
Ramsey theory / Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer (1990)
Rothschild, Bruce L, Spencer, Joel H
"A Wiley-Interscience Publication"
Probabilistic methods in combinatorics / by Paul Erdos and Joel Spencer (1974)
Incluye bibliografía e índice