Speaker: Wei-Tian Li, USC.
Title: An overview of Sum Query problems
Abstract: We discuss applications of combinatorial arguments to maximize the usability of a statistical database under the control of the mechanism Audit Expert. The goal is to maximize the number of SUM queries from a database of real numbers without compromising it. Direct connections emerge between such database query models and problems that concern maximizing, over all choices of n nonzero elements, the number of the 2n subset sums over all index sets belonging to some specified target set T. We survey the connections between some number theory problems and the above problems, and their extensions to higher dimensions.
Speaker: Paul Kainen, Georgetown University.
Title: The New Four Color Problem
Abstract: The Four-Color Map Theorem was proved over 30 years ago using computer-implemented calculations to verify a large number of particular cases. Several improvements have since appeared but still no short, conceptual proof of this theorem is known. The talk will sketch the history of the problem and provide a variety of rather different formulations such as the propagation of physical torque. A new problem is proposed for quantum computation.
Speaker: Balazs Patkos, University of Memphis.
Title: Intersection Theorems Subsets vs Subspaces
Abstract: The celebrated theorem of Erdos, Ko and Rado on intersecting families of sets was published in 1961. Since then, many researchers have been attracted to this area of extremal combinatorics. The q-analogue of the EKR-theorem (i.e. when subsets are replaced by subspaces of a vector space) was first obtained by Hsieh in 1977. In this talk, I would like to compare the main results known for intersecting families of subsets and of subsets with emphasis on some recently obtained theorems for subspaces including the q-analogue of the Lovasz-version of the Kruskal-Katona theorem.
Speaker: Yubo Zou, USC.
Title: GRAPH THEORY AND RAINBOW SMELT
Abstract: Graph theory has been applied to ecological science in several ways, such as landscape connectivity (Bunn et al, 2000; Urban and Keitt, 2001; D'Eon et al, 2002) and population graphs (Dyer and Nason, 2004). Here we compare the difference of distinct approaches of applying graph theory in ecological research and introduce a new scale of measurement (index of coincidence) that emphasizes the genetic difference of sample populations. We conduct the analysis of rainbow smelt from Newfoundland coastal locations based on the landscape connectivity, population graph and index of coincidence, and the index of coincidence distinguishes meta populations. At the end, we study the genetic difference based on each individual.
Speaker: Csaba Biro, USC.
Title: On-line algorithms on posets: dimension
Abstract: A realizer of a poset P is a set of its linear extensions such that that their intersection is equal to P. We will introduce the problem of building realizers in an on-line manner. The minimum number of linear extensions that the best algorithm would use is the on-line dimension of posets. The main topic will be a detailed proof of a theorem by Kierstead, McNulty and Trotter, which gives a sufficient condition for the on-line dimension of a class of posets to be finite.
Attendance of the previous Combinatorics Seminar is not necessary to understand this one.
Speaker: Csaba Biro, USC.
Title: On-line algorithms on posets: chain partitioning
Abstract: Finding the chain partition of a partially ordered set is an easy job. The problem becomes much more interesting if we need to do it on-line. Consider the following problem: An adversary gives us the poset point by point, in each step only revealing the relationship of the current point with the previous ones. After every point, we have to assign that point irrevocably to a chain. Kierstead found an algorithm in 1981 that does the job using (5w-1)/4 chains, where w is the width of the poset. The main focus of this talk is a detailed presentation of Kierstead's proof. We will also discuss some related results, in particular a lower bound for the number of chains that any on-line algorithm must use.
Speaker: Lincoln Lu, USC.
Title: On Meyniel's conjecture of the cop number
Abstract: Meyniel conjectured the cop number c(G) of any connected graph G on n vertices is at most Cn1/2 for some constant C. In this talk, we prove Meyniel's conjecture in special cases that G has diameter at most 2 or G is bipartite graph with diameter at most 3. For general connected graphs, we prove c(G) = O( n 2-(1-o(1)) (log2 n)1/2), improving the best previously known upper-bound O(n / ln n) due to Chiniforooshan.
(Joint work with Xing Peng)
Speaker: Josh Cooper, USC.
Title: The Discrepancy of the Lexicographically Least de Bruijn Cycle
Abstract: A (binary) de Bruijn cycle of order $n$ is a cyclic binary word of length 2n so that every binary word of length n appears as a subword exactly once. There are many constructions for de Bruijn cycles, but one stands out for its extraordinary properties. The lexicographically-least de Bruijn cycle, sometimes called the Ford sequence, is also the de Bruijn cycle generated by the "greedy" algorithm, the cycle generated by a linear-shift feedback register of minimum weight, and the string of all Lyndon words of length dividing n arranged in lexicographic order. It is not hard to see that the Ford sequence is very "unbalanced" in the sense that there is an excess of 0's near the beginning and an excess of 1's near the end. It is possible to quantify this intuition by defining the discrepancy of a sequence to be the maximum, over all initial segments, of the difference between the number of 0's and 1's. We show that the discrepancy has order 2n log n/n, answering a question of Ron Graham.
Speaker: Eva Czabarka, USC.
Title: Minimizing the number episodes on a species tree - an extension of Gallai's theorem on intervals
Abstract: In 1996 Guigo et al. posed the following problem: for a given species tree and a number of gene trees, what is the minimum number of duplication episodes, where several genes can undergo duplication together to generate the observed situation (gene order is neglected, but duplication of genes could have happened only on segments associated with particular genes on the species tree). We study two versions of this problem, one of which was solved recently by Bansal and Eulenstein. We provide min-max theorems for both versions that generalize Gallai's archetypal min-max theorem on intervals. These theorems lead naturally to algorithms that find a feasible placement of the optimal number of episodes on the species tree.
This is joint work with L.A. Szekely and T.J. Vision.
Speaker: Yiting Yang, USC graduate student.
Title: On the expectation and variance of the reversal distance
Abstract: A reversal on a signed permutation is an operation that reverses the order and change the signs of the elements in a certain segment of the permutation. Given two signed permutations on the same elements set, the reversal distance is the minimum number of reversals needed to transform one into the other. We give a pair of well-matched lower and upper bounds for the expectation of reversal distance under the hypothesis of random permutations. We also provide an upper bound for the variance of reversal distance, which gives information on the distribution of reversal distance.
(Joint work with Laszlo Szekely)