Speaker: Mark Walters, USC.
Title:Iterated Point-Line Configurations Grow Doubly-Exponentially
Abstract: Begin with a set of points P1 = {p1, p2, p3, p4} in the real plane in general position. For each pair of points, construct the line passing through the pair. This will create a set of lines L1 = {l1,l2,l3,l4,l5,l6}. Some of these constructed lines will intersect at points in the plane that do not belong to the set P1. Add these points to the set P1 and note that not all pairs of points of the new set P2 lie on a line in L1, namely some elements of P2 - P1. Add the missing lines to the set L1 to get L2 and iterate in this manner, adding points to Pk followed by adding lines to Lk. Ismailescu and Radoi\v{c}i\'{c} (2003) showed that the limiting set ∪ k=1 ∞ Pk is dense in the plane. We give a lower bound matching the trivial doubly-exponential upper bound on |Pk|, although a substantial gap remains. The proof employs a variant of the Szemer\'edi-Trotter Theorem and an analysis of the ``minimum degree'' of $P_k$.
Speaker: Paul Horn, University of California, San Diego.
Title:The spectral gap of a random subgraph of a graph
Abstract: The spectral gap of the normalized Laplacian of a graph is strongly related to many important graph properties, including the mixing rate of random walks as well as expansion and discrepancy properties. Here we consider a random subgraph H of a given graph G where each edge in G is taken to be in H independently with probability p, and derive bounds on the spectral hap of H in terms of the spectral gap of G. This can be thought of as an extension of earlier work on the Erdos-Renyi G(n,p) model, which effectively treats a special case where the underlying graph is the complete graph Kn.
Speaker: Darren Narayan, Rochester Institute of Technology, currently visiting USC.
Title:Graph Representations and Extremal Sets
Abstract: A graph is said to have a representation modulo n if its vertices can be labeled with distinct integers between 0 and n-1 inclusive. It has been shown that any graph can be represented modulo some positive integer. The representation number is the smallest n such that G has a representation modulo n. We will give representation numbers for various classes of graphs. We will also show connections between these graph representations and the existence of complete families of mutually orthogonal Latin squares. We will also discuss some possible strategies for determining representations using tools from extremal set theory.
Speaker: Richard Anstee, the University of British Columbia, currently visiting USC.
Title: Some progress towards a conjectured bound for forbidden configurations
Abstract: We consider the extremal set theory problem of forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. For a matrix F we say a matrix A has F as a configuration if a submatrix of A is a row and column permutation of F. The forbidden configuration problem assumes F is given and considers how many columns can an m-rowed simple matrix A have if A has no configuration F. In stating a conjectured asymptotic bound on the number of columns as a function of the forbidden configuration, a critical result was obtaining a quadratic bound for the 3x3t configuration consisting of t copies of the identity. More complicated configurations are required to complete all 3-rowed configurations. Establishing the conjecture for all 4-rowed configurations is even more complicated but I'll indicate some modest progress and the proof ideas used.
(Some of the results are joint with Attila Sali.)
Speaker: William Gasarch, University of Maryland
Title: GRID COLORINGS
(Work joint with Steven Fenner, Charles Glover, Brett Jefferson)
Abstract: KNOWN: If you 2-color the lattice points in the plane there will be a square with all four corners the same color. You actually don't need to color ALL the lattice points in the plane--- the proof yields that you need only color an NxN grid where N is ... rather large (1010000000 probably works).
NEW: What if you only want to get a RECTANGLE with all four corners the same color? Then the numbers involved get MUCH smaller. In fact, we have some rather sharp theorems.
We say that a grid is c-colorable if there is a coloring that does not have all four corners the same color. The following is known:
Pinning down 4-colorable and beyond. Either prove O(c^3) is tight or lower it.
Speaker: Josh Cooper, USC.
Title: Symmetric and Asymptotically Symmetric Permutations (part II)
Speaker: Josh Cooper, USC.
Title: Symmetric and Asymptotically Symmetric Permutations
Abstract: R. Graham asked whether random-like permutations can be characterized by their pattern counts on a fixed k number of symbols. This closely analogizes the phenomenon of quasirandomness in other combinatorial objects, and lends itself naturally to a random tensor-product construction. We discuss this problem, answer the question in the negative for k=3, and mention several directions for further research. Joint work with Andrew Petrarca.
Speaker: Lincoln Lu, USC.
Title: An exact result and its application on hypergraph Turan numbers
Abstract: We first prove an exact result for hypergraphs: given r > 2, let p be the smallest prime factor of r-1. If n > (p-1)r and G is an r-uniform hypergraph on [n] such that every r+1 vertices contain 0 or r edges, then G is either empty or the complete star. Then we use it to improve best known bounds for hypergraph Turan numbers. We show that when r ≥ 4 is even.
Speaker: Éva Czabarka, USC.
Title: Diameter of 4-colorable graphs with given minimum degree
Abstract: In 1989, Erdos, Pach, Pollack, and Tuza conjectured the following: Let r, δ ≥ 2 be fixed integers and let G be a connected graph with n vertices and minimum degree δ.
This is joint work with Peter Dankelmann and László Székely.
Speaker: Josh Cooper, USC.
Title: Klee's Measure Problem, Multiobjective Optimization, and Monotone Boolean Functions
Abstract: Klee's Measure Problem is that of determining the measure of the union of n axis-parallel boxes in Rd. Its computational complexity has long been open, with a lower bound of n log n and an upper bound of nd/2 log n. We show that this problem is #P-hard. That is, there is no polynomial time (in d) algorithm for computing it unless P=NP. The proof reduces monotone CNF-SAT, shown to be #P-hard by Valiant in 1979, to a problem in multiobjective optimization -- computation of the so-called ``hypervolume'' of a Pareto front -- which is then reduced to Klee's Measure Problem. We also give a polynomial-time randomized approximation algorithm (an FPRAS) for the hypervolume.
Joint work with Tobias Friedrich of MPI-Saarbr\"ucken.
The seminar is cancelled because it conflicts with Dr. Qi Wang's interview schedule.
Speaker: Richard Anstee, the University of British Columbia, currently visiting USC.
Title: Some Non-simple Forbidden Configurations and Design Theory
Abstract: Let k,l,m,q be given. We let f(m,k,l,q) denote the maximum number of subsets of {1,2,...,m} in a family F so that we cannot find q sets A1,A2,...,Aq in F and k+l elements a1,a2,...,ak+l in {1,2,...,m} so that each of the q sets A_i contains the k elements a1, a2,..., ak and does not contain the l elements ak+1, ak+2,..., ak+l. We are able to compute f(m,1,1,q), f(m,2,1,q) and f(m,2,2,q) exactly for large m. For example, the natural construction for k=2, l=1 is to take all sets of size 0, 1, 2, m and also the sets of size 3 corresponding to a simple triple system of λ=q-2 (which exists by a result of Dehon, 1983) and we are able to show for large m that indeed this yields f(m,2,1,q).
Joint work with Farzin Barekat.