We generalize these bounds by placing the restriction on the intersections of k distinct members of the family. Again let L be a set of s congruence classes modulo a prime p. Let H be a family of subsets of [n] such that the size modulo p of each member of H is not in L, but the size modulo p of every intersection of k distinct members of $H$ is in L. We prove that |H|<(k-1)\sum_{i=0}^s {n-1\choose i}. This improves an earlier bound by Grolmusz having n in place of n-1. We use the linear algebra method, obtaining the bound from the dimension of a subspace of a linear space of polynomials. This is joint work with Kyung-Won Huang and Douglas West.

The problem has been generalized in various ways. Here we consider the problem with a partial order instead of a linear one. This seems to better approximate real life situations where options need not be linearly ordered. The aim of this talk is to discuss optimal and effective strategies for the partial order generalization of the secretary problem. Such strategies in some specific situations (such as a binary tree order and an unknown order) will be considered. Interesting combinatorial counting problems that arise when looking for such strategies will be discussed.

Given k and n, we determine the least integer d such that, for every graph H with k edges and minimum degree at least two, every n-vertex graph with minimum degree at least d is H-linked. This value D(k,n) appears to equal the least integer d' such that every n-vertex graph with minimum degree at least d' is k-connected. On the way to the proof, we extend a theorem by Kierstead et al. on the least integer d'' such that every n-vertex graph with minimum degree at least d'' is k-ordered.

This is joint work with Alexandr Kostochka.

The Peano curve was studied by the Italian mathematician Giuseppe Peano in 1890 as an example of a continuous space filling curve. The Peano infinite word is a discrete analog of the Peano curve.

Are there any similarities between the Arshon sequence, the Dragon curve, and the Peano infinite word in terms of combinatorics on words? In this talk, I will answer this question using some recent results.

The chromatic number never declines by more than one when a vertex is deleted, and it was widely thought that the same would hold for the circular chromatic number. In this talk, we present the surprising construction by Xuding Zhu of an infinite family of graphs with circular chromatic number 4 such that deletion of any vertex reduces the circular chromatic number to 8/3.

Kierstead and Trotter conjectured that for each k, there is a constant F(k) such that every k-majority tournament (with no restriction on the number of vertices) has a dominating set of size at most F(k). They also conjectured that F(2)=3; that is, every tournament generated by majority rule from a set of three linear orders has a dominating set of size 3. In this talk we prove these conjectures and describe some open problems.

The result is joint work with G. Brightwell, H. Kierstead, and P. Winkler.

Previous research on the NK model has emphasized simulations and analysis of local optima. Here we focus on rigorous results for global optima. We describe a computational setup using a stochastic network model, which leads to applicable strategies for computing bounds on global optima when K is small or is close to N. Recent papers used tools from analysis and probability to obtain bounds on the expected value of the global optima for fixed K and large N. We present bounds when K grows with N, using elementary probabilistic combinatorics and order statistics. We use a `dependency' graph to convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about mutual dependencies among the underlying random variables. If time permits, an alternate upper bound and the analysis for the cases of underlying uniform and normal distributions will be presented.

This is joint work with Prof. S.H. Jacobson.

Some instances of this construction are well known. The cone M₁(G) is the graph obtained from G by adding a vertex joined to all of V(G). The cone M₂(G) is Mycielski's construction over G. This was invented in 1955 by Mycielski to generate triangle-free k-chromatic graphs for all k> 2. It is easy to show that \chi(M₁(G))=\chi(G)+1 and \chi(M₂(G))=\chi(G)+1.

We ask whether all cones over a graph G have chromatic number larger than G? For example, is M_r(C_2l+1) always 4-chromatic? We show that this question has a topological flavor.

This is joint work with Peter Frankl.

This is joint work with Prof. Peter Hamburger.