Joel Spencer

A covering design, or covering, is a family of k-subsets, called blocks, chosen from a v-set, such that each t-subset is contained in at least one of the blocks. The number of blocks is the covering's size}, and the minimum size of such a covering is denoted by C. It is easy to see that a covering must contain at least / blocks, and in 1985 R\"odl [European J. Combin. 5, 69-78] proved a long-standing conjecture of Erd\H{o}s and Hanani [Publ. Math. Debrecen 10, 10-13] that for fixed k and t, coverings of size / ) exist. An earlier paper by the first three authors [J. Combin. Des. 3, 269-284] gave new methods for constructing good coverings, and gave tables of upper bounds on C for small v, k, and t. The present paper shows that two of those constructions are asymptotically optimal: For fixed k and t, the size of the coverings constructed matches R\"odl's bound. The paper also makes the o error bound explicit, and gives some evidence for a much stronger bound.

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 119–145] of D)=log1/pn+O.

This Master of Arts thesis is in two parts: a novel, An Anarchy of Man, and an exegesis which places the novel in relation to philosophical concerns about the self and the way those concerns are portrayed in selected works of Western literature. The novel is set in Canberra and Sydney and tells the story of the relationship between two characters: Joe and Gin. It explores the way we in the modern Western world think about ourselves and those around us. Chapter One considers the view of the self in the work of the philosopher Rene Descartes and explores how this view is portrayed in three contemporary Australia novels, and in An Anarchy of Man. Chapter Two examines post-Cartesian views of the self, especially those in the work of the philosopher Ludwig Wittgenstein, and then considers the way the self is portrayed in Proust's Remembrance of Things Past, and in my own An Anarchy of Man. Chapter Three examines postmodern conceptions of the self and considers how these conceptions are portrayed in the work of the contemporary American novelist Don DeLillo and in my own An Anarchy of Man.

We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L ) denote the minimum length of such a sentence. We define the succinctness function s ) to be the minimum L ) over all graphs on n vertices.We prove that s and q may be so small that for no general recursive function f we can have f)≥n for all n. However, for the function q*=maxi≤nq, which is the least nondecreasing function bounding q from above, we have q*=)log*n, where log*n equals the minimum number of iterations of the binary logarithm sufficient to lower n to 1 or below.We show an upper bound q