Speaker: Jerry Griggs, USC
Title: "Extending the LYM inequality for antichains of subsets"
Abstract: We shall present recent and continuing work on problems concerning the Boolean lattice B_n of all subsets of an n-element set X. Especially, we shall discuss a joint project with Gyula O. H. Katona concerning the "YBLM Inequality". Better known as LYM, it is a linear inequality satisfied by the parameters fi of any antichain F of subsets of X, where fi denotes the number of subsets in F of size i. However, this necessary condition for the profiles (f0,...,fn) of antichains in Bn is far from sufficient, and we seek inequalities satisfied by profiles of antichains that eliminate some of the profiles satisfying YBLM for which no antichain exists. We build on earlier work of Christian Bey. Our project also relates to the Kruskal-Katona-Lovasz shadow function.
Speaker: Nick Loehr, The College of William and Mary.
Title: The q,t-Catalan Theorem and the q,t-Square Theorem
Abstract: This talk gives an overview of the two theorems featured in the title. The "q,t-Catalan theorem" is one of the crowning achievements of more than a decade of research on diagonal harmonics by Mark Haiman, Jim Haglund, Adriano Garsia, and others. The "q,t-square theorem" is a more recent development that is joint work with Greg Warrington and Mahir Can. These theorems give a surprising unification of seemingly unrelated concepts in various areas: word combinatorics, lattice path combinatorics, representation theory, algebraic geometry, symmetric functions, partition theory, and Macdonald polynomials.
Speaker: Alan Frieze, Carnegie Mellon University.
Title: The Cover Time of Random walks on Random Graphs and Digraph
Abstract: We give asymptotically precise estimates for the expected time taken for a random walk to visit all vertices of a graph, viz. the cover time. We do this for several models of random graphs viz. Gn,p when p is above the connectivity threshold; random r-regular graphs; the giant component of Gn,p when the average degree is a constant larger than 1; the preferential attachment graph. We also consider the random digraph Dn,p. The results are based on a lemma that can most usefully be applied to graphs of "high girth" and for which the random walk is "rapidly mixing" e.g. Ramanujan graphs.
Speaker: Josh Cooper, USC.
Title: Generalized De Bruijn Cycles
Abstract: For a set of integers I, we define a q-ary I-cycle to be a assignment of the symbols 1 through q to the integers modulo q^n so that every word appears on some translate of I. This definition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We address the existence of such cycles, discuss reduced cycles (ones in which the all-zeroes string need not appear), and provide general bounds on the shortest sequence which contains all words on some translate of I. We also prove a variant on recent results concerning decompositions of complete graphs into cycles and employ it to resolve the case of |I| = 2 completely.
Title: Introduction to genome rearrangements
Abstract: Given two genomes, we want to determine the sequence of events required to transform one genome to another. We define the distance of these two genomes as the minimum number of events required. I will mainly talk about the distance computation for the events: Inversion and Transposition.
Speaker: Laszlo Szekely, USC.
Title: Lovasz Local Lemma in the space of random injections
Abstract: The Lovasz Local Lemma is known to have an extension for cases where independence is missing but negative dependencies are under control. We show that this is often the case for random injections, and we provide easy-to-check conditions for the non-trivial task of verifying a negative dependency graph for random injections. As an application, we prove existence results for hypergraph packing and Turan type extremal problems. A more surprising application is that tight asymptotic lower bounds can be obtained for asymptotic enumeration problems using the Lovasz Local Lemma.
This is a joint work with Lincoln Lu.
Speaker: Lincoln Lu, USC.
Title: Color non-uniform hypergraphs red and blue
Abstract: Let f(r)=minH sumF ∈ E(H)2-|F|, where the minimum is taken over all 3-chromatic hypergraphs H with minimum edge cardinality at least r. Erdos-Lovasz (1975) conjectured f(r) is an unbounded function of r. This conjecture was proved by Beck in 1978. Here we show a new proof for this conjecture with a better lower bound f(r) > ln r / (16 ln ln r) for sufficiently large r.
Speaker: Attila Sali, Alfred Renyi Institute of Mathematics, currently visiting USC.
Title: Codes that atain minimum distance in all possible directions
Abstract: Let K be the system of minimal keys in relational database schema R with respect some collection of functional dependencies Σ. Then K is a Sperner system, or antichain, that is for K1 ≠ K2∈ K K1⊄ K2 holds. Armstrong (and independently Demetrovics) proved that for each nonempty Sperner system of attribute sets there exists an instance of the scheme such that if the complete set of functional dependencies are considered that hold in that instance, then eaxactly the given Sperner system is the collection of minimal key sets. However, the constructions use unbounded domains for each attribute. In the study of key systems in higher-order datamodels with counter attributes the case of bounded domains come up naturally. In the present paper we investigate the following problem. Assume that a relational scheme of n attributes is given, where each attribute's domain is of q elements. Furthermore, suppose that the minimal key sets are exactly all the k-element subsets of the set of attributes. Let f(q,k) be the maximum n such that an Armstrong instance with the above properties exists. Considering the records or rows of the Armstrong instance as codewords of length n, the key property means that no two codewords can agree on k or more coordinates, that is the minimum distance is at least n-k+1. The minimal key property tells that for any k-1-set of coordinates there are two codewords that agree exactly there. We give lower and upper bounds for f(q,k). In particular, we show that f(q,k) is bounded by linear functions of k and q, and determine the exact values for special k and q.
Speaker: Josh Cooper, USC.
Title: Random Linear Extensions of Grids
Abstract: A grid poset -- or "grid" for short -- is a product of chains. We ask, what does a random linear extension of a grid look like? This problem generalizes now-classical work on random plane partitions, and has surprising connections with the theory of random Ferrer diagrams, poset order dimension, representability theory in qualitative probability, and conjoint analysis (a subfield of marketing research). We show that the average "jump number," i.e., the number of times that two consecutive elements in a linear extension are incomparable in the poset, is close to its maximum possible value. The techniques employed rely on entropy arguments. We mention several interesting questions about this wide-open area.