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)
Speaker: Mark Walters, USC graduate student.
Title: Characterization of Iterated Point-Line Intersections
Abstract:Let IRP denote the Ismailescu/Radoicic plane found by iterated point-line intersections in the real projective plane. We analyze the relationship between Pappus' Theorem and Desargues' Theorem in projective geometry and give a result that characterizes IRP in terms of Pappus. We also analyze the growth rate of iterated point-line intersections in the free projective plane, which serves as an upper bound for the analogous growth rate in IRP. We provide proof that the lower bound is asymptotic to the trivial upper bound, which pins down this growth rate. Joint work with Joshua Cooper.
Speaker: Csaba Biro, USC.
Title: Segment Orders
Abstract: Farhad Shahroki introduced two classes of partially ordered sets, which are defined using specific straight line segments in the Euclidean plane. Both classes are natural generalizations of interval containment orders and interval orders. We prove several properties of the classes, and---inspired by the observation that the classes seem to be very similar---we focus on the question whether they are distinct. We prove that the question is equivalent to a stretchability question of pseudoline arrangements and we also prove several facts about hypothetical continuous universal functions between the classes.
This is joint work with William T. Trotter.
Speaker: Joshua Cooper, USC.
Title: Monochromatic Boxes in Colored Grids
Abstract: Abstract: A d-dimensional grid is a set of the form R = [a1] X ... X [ad]. A d-dimensional box is a set of the form {b1,c1} X ... X {bd,cd}. When a grid is c-colored, must it admit a monochromatic box? If so, we say that R is c-guaranteed. This question is a relaxation of one attack on bounding the van der Waerden numbers, and also arises as a natural hypergraph Ramsey problem (viz. the Ramsey numbers of hyperoctahedra). We give conditions on the a_i for R to be c-guaranteed that are asymptotically tight, and analyze the set of minimally c-guaranteed grids. Joint work with Stephen Fenner and Semmy Purewal.
Speaker: Michael Mossinghoff, Davidson College, currently visiting USC.
Title: Extremal problems for polygons with fixed diameter
Abstract: Among convex polygons with unit diameter and a fixed number of sides n, the regular n-gon achieves neither the maximal area nor the maximal perimeter when n > 4 is even. We describe how to construct better polygons in both problems, and discuss some recent work on counting the number of different convex n-gons with unit diameter that achieve the optimal perimeter.
Speaker: Lincoln Lu, USC.
Title: The giant component in a random subgraph of a given graph
Abstract: We consider a random subgraph Gp of a host graph G formed by retaining each edge of G with probability p. We address the question of determining the critical value p (as a function of G) for which a giant component emerge. Suppose G satisfies some (mild) conditions depending on its spectral gap and higher moments of its degree sequence. We define the second order average degree d to be d = Σv dv2 / (Σv dv) where dv denotes the degree of v. We prove that for any ε > 0, if p > (1 + ε)/d then almost surely the percolated subgraph Gp has a giant component. In the other direction, if p < (1-ε) / d then almost surely the percolated subgraph Gp contains no giant component.
Speaker: Paul Horn, UCSD.
Title: Independent dominating sets in graphs of girth 5.
Abstract: A classical result in probabilistic combinatorics is that if G is a graph on n vertices with minimum degree \delta then G contains a dominating set of size of at most n log(δ + 1) / (δ+1). Here, under the further assumptions that G is of girth at least 5 and, is d-regular we show that, effectively, such a dominating set can be taken to be independent. That is, we show that every n-vertex d-regular graph of girth 5 contains an independent dominating set of size (n log d)/d + O(n/d) as d go to infinity. We further give examples showing that the girth requirement is necessary and that regularity is necessary in the sense that if G has minimum degree δ, the smallest independent set may be much larger than (n \log δ)/δ. This is joint work with A. Harutyunyan, and J. Verstraete.
Speaker: Josh Cooper, USC.
Title: Pythagorean Triple Regularity and Triple Systems with the Sum Property
Abstract: We consider the following question : Is there a coloring of the naturals with finitely many colors so that no Pythagorean triple (the three edge lengths of an integer-sided right triangle) is monochromatic? It is not even known if it is possible to 2-color the naturals under this condition. We discuss some small progress, including a proof that a class of triple systems that includes the Pythagorean triple system (those with the ``sum property'') do not contain any Steiner triple systems (STS's). Since STS's are a natural choice of certificate to seek in proving that the Pythagorean triple system cannot be 2-colored, this suggests other routes of attack are necessary.
(Joint work with Chris Poirel.)
Speaker: Csaba Biro, USC.
Title: Correlation and height sequences in posets
Abstract: In this talk, we investigate the height sequence of an element of a partially ordered set. Let x be an element of the partially ordered set P. Then hi(x) is the number of linear extensions of P in which x is in the i-th lowest position. The sequence {hi(x)} is called the height sequence of x in P. Stanley proved in 1981 that the height sequence is log-concave, but no combinatorial proof has been found, and Stanley's proof does not reveal anything about the deeper structure of the height sequence. We motivate the research with an application and we provide a combinatorial proof of two special cases of Stanley's theorem.
(Joint work with William T. Trotter.)
Speaker: Lincoln Lu, USC.
Title: Diameter of random spanning trees in a given graph
Abstract: We show that a random spanning tree formed in a general graph G (such as a power law graph) has diameter much larger than the diameter of G. We show, with high probability the diameter of a random spanning tree of G is shown to be between c\sqrt{n} and c'\sqrt{n}log (n), where c and c' depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of log(n).
(Joint work with Fan Chung and Paul Horn.)