Asymptotically ex(n,C₄) ~ n^3/2/2. Determining the exact value of ex(n,C₄) seems to be hopeless, except in the case n=q²+ q+1. Let G be a quadrilateral-free graph on q²+q+1 vertices, where q \ne 1,7,9,11,13. It was proved (1983, 1996) that then G has at most q(q+1)²/2. The aim of this talk is to sketch the proof, or at least to describe the tools, that here equality holds only for polarity graphs (for q>3).

(Joint work with H. Kierstead.)

A related concept is the tree-depth of a graph. Roughly speaking, this is the minimum height of a rooted forest whose closure contains the graph as an induced subgraph. For a positive integer p, the generalized coloring parameter chi_p(G) is defined to be the minimum number of colors needed to label V(G) so that the number of colors on each subgraph having tree-depth at most p is at least its tree-depth. The main result is that the k-coloring number is bounded on a minor-closed class of graphs if and only if chi_p(G) is bounded on the class. Other chromatic invariants are also bounded in terms of the k-coloring number on minor-closed families. This talk reports on research by Xuding Zhu.

We consider a variation proposed by S. Ramachandran, in which each card is presented along with the degree of the deleted vertex, yielding a "dacard". The degree-associated reconstruction number drn(G) is the minimum number of dacards that determine G. We describe several results on drn(G), including that drn(T)< 2 if T is a caterpillar, with one 6-vertex exception.

In terms of the values of f, there is a natural but technical upper bound k on the maximum number of disjoint bases. We show that \Omega(k/ln f(N)) disjoint bases always exist. We give a randomized algorithm to find such bases and derandomize it using approximate min-wise independent permutations. The proof is simple, and the question was motivated by a couple of special cases in the literature that will be discussed. We also obtain nearly tight results on hardness of approximation for estimating k or the maximum number of disjoint bases. (Joint work with Gruia Calinescu and Jan Vondrak.)

If time permits, I will also present a combinatorial proof of Hardy's Inequality (discrete version, of course). This is joint work with Tim LeSaulnier.

We generalize this game by restricting how Carole may lie. A channel is a set C of strings, where the empty string means that Carole never lies during the game, and the ith bit in a nonempty string tells whether the ith lie is responding 1 when the true answer is 0 or responding 0 when the true answer is 1. In each game, Carole must conform to some allowed lie string. If at some stage no element in the search space satisfies the answers given under any lie string in C, then Carole defaults, having "cheated".

Given C, we determine asymptotically the maximum size search space for which Paul can guarantee finding the distinguished element. We also solve the pathological liar game variant, in which Paul must prevent Carole from lying too much. In both cases we restrict Paul to asking questions in two batches. Our results generalize previous work on an channel with unweighted lies by Dumitriu and Spencer, and on a weighted channel by Cicalese, Deppe, and Mundici. This is joint work with Kathryn Nyman.