Speaker: Richard Anstee, University of British Columbia.
Title: Some Error Theorems for Matchings.
Abstract: In joint work with Aldred, Locke and Tseng we consider some graphs which have lots of perfect matchings and consider situations where we can disturb the graph, for example by deleting some vertices, and still have a perfect matching. In the two dimensional 2mx2m grid graph, if the deleted vertices are about square root of m apart and the bipartition is respected (the same number of vertices are deleted from each side of the bipartition) then the resulting graph has a perfect matching. We consider the d-dimensional grid graph as well as the triangular grid. We also consider matching extendability in grid graphs, corresponding to deleting vertices in adjacent pairs.
Speaker: Prasad Tetali, Georgia Institute of Technology.
Title: A Near Optimal Bound for Pollard's Rho to Solve Discrete Log
Abstract: We analyze the classical Pollard's Rho algorithm for finding the
discrete logarithm in a cyclic group G. We prove that, with high
probability, a collision occurs and the discrete logarithm is
potentially found in O(\sqrt|G|log |G| log log |G|}) steps, not
far from the widely conjectured value of Θ(\sqrt{|G|}). This
improves upon a recent result of Miller--Venkatesan which showed an
upper bound of O(\sqrt{|G|} log^3 |G|).
Our proof is based on analyzing an appropriate nonreversible, non-lazy
random walk on a discrete cycle of (odd) length |G|, and showing
that the mixing time of the corresponding walk is O(log |G| log
log |G|). We also observe that the standard mixing time of the
corresponding walk is O(log |G| log log |G|). We also observe
that the standard methods using functional-analytic constants
(spectral gap, logarithmic Sobolev etc.), combinatorial comparison or
standard coupling arguments fall short here and will at best offer a
bound of O(log^2 |G|).
Joint work with Jeong Han Kim (Yonsei University, Korea)
and Ravi Montenegro (University of Massachussetts, Lowell).
Speaker: Kelly Kross, USC.
Title: A symmetric chain decomposition for the necklace poset
Abstract: Define by Nk the quotient poset of the Boolean lattice, B_n, under the relation "equivalence under rotation." Griggs, Killian, and Savage proved that "Np" is a symmetric chain order for prime p. In this talk, we settle the question of whether this poset is a symmetric chain order for all k by providing an algorithm that produces a symmetric chain decomposition. We accomplish this by modifying the idea of parenthesis matching from Greene and Kleitman. This allows us to take appropriate "middles" of the chains of a subset of the Greene-Kleitman SCD for Bn.
Speaker: Attila Sali, Alfred Renyi Institute of Mathematics, currently visiting USC.
Title: SPT(q,k,n)-Codes
Abstract:
We consider q-ary codes of length n with property
1. C has minimum Hamming-distance at least n-k+1.
2.For any set of k-1 coordinates there exist two codewords
that agree exactly there.
A k-1-set of coordinate can be considered as a 'direction', so in
C the minimum distance is attained in all
directions. Such a code C is called sphere-packing type
code of parameters (q,k,n), or SPT(q,k,n)-code for short. For
example, the rows
of the k+1 X k+1 identity matrix form an SPT(2,k,k+1)-code.
Definition
Let q>1 and k>1 be given natural numbers. Let f(q,k) be the
maximum n such that there exists an SPT(q,k,n)-code.
New bounds on f(q,k) are proven. Upper bound employs spherical codes, the
lower bound is probabilistic construction using Lov\'asz Local Lemma.
This is joint work with Laszlo Szekely.
Speaker: Drago Bokal, University of Walterloo.
Title: On the crossing numbers of Cartesian products with trees
Abstract: Beineke and Ringeisen investigated the crossing numbers of Cartesian products of small graphs with cycles and established the crossing numbers of the Cartesian product of Cn ⊗ G where G is any simple graph of order four, except the 3-star, K1,3. Jendrol and Scerbova closed this gap and also obtained the crossing number of Pm ⊗ K1,3. They conjectured the general result for Pm ⊗C K1,n, which was proven for n = 4 by Klesc. We prove their conjecture in a slightly more general setting: by combining the result of Asano about the crossing number of K1,3,n with a new operation on graphs, the zip product, we establish the crossing number of T ⊗C K1,n where T is any tree of maximum degree three and n ≥ 3 is any integer. We supplement this result by the crossing number of T ⊗ K1,3 for any tree T, the crossing number of Pm⊗C W n for any m≥1, n≥3, and some other exact results and bounds.
Speaker: Drago Bokal, University of Walterloo.
Title: Computing quadratic entropy in evolutionary trees
Abstract: Evolutionary trees are rooted trees with all leaves at the same distance from the root. They are used to represent evolutionary history of living species of organisms. The concept of distinctness or originality of some species within a given evolutionary tree is of particular interest to environmentalists and biologists, especially in the context of prioritizing efforts for preservation of endangered species. Quadratic entropy is a particular measure of distinctness, which can be computed using quadratic programming for any kind of objects whose pairwise disparity is given by some matrix. In the talk, we will present a linear time algorithm that computes quadratic entropy for distances coming from an evolutionaty tree of species.
Speaker: Yi Zhao, Georgia State University.
Title: Codegree problems for projective geometries
Abstract:
The codegree density γ(F) of an r-graph F is the largest
number γ such that there are F-free r-graphs G on n
vertices such that every set of r-1 vertices is contained in
at least (γ-o(1))n edges. For general projective
geometries we obtain the upper bound gamma(PG(m, q)) ≤ 1-1/m.
We show that equality holds whenever m=2 and q is odd, and whenever
m=3 and q is 2 or 3.
Joint work with Peter Keevash.
Speaker: Rigoberto Florez, USC Sumter.
Title: A construction of a projective plane in algebraic matroids.
Abstract: A matroid is a generalization of the dependence and independence of a
finite set of vectors. There are no linear relations, only dependent and
independent sets. This structure is present in several different
subjects of mathematics. For example in graphs, vectors, projective
planes and transcendental extension of
fields (algebraic matroids).
In this talk, we define the harmonic matroid. We discuss how to
construct a projective plane of order prime in any harmonic matroid
without using the axioms of projective geometry.
Speaker: Attila Sali, Alfred Renyi Institute of Mathematics, currently visiting USC.
Title: Color critical hypergraphs and forbidden configurations
Abstract: The present paper gives sharpenings of Sauer's bound on forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k by l (0,1)-matrix (the forbidden configuration). Assume A is an m by n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. It is known that forb(m,F)=O(mk) for any F, and Sauer's bond states that forb(m,F)=O(mk-1}) for simple F. We give sufficient condition for non-simple F to have the same bound using linear algebra methods. forb(m,F) for families of forbidden configurations is also discussed.
Speaker: Lincoln Lu, USC.
Title: Using Lovasz Local Lemma in the Space of Random Matchings
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 matchings,
and we provide easy-to-check conditions for the non-trivial task of
verifying a negative dependency graph for random matchings.
This gives an alternative probabilistic tool for random permutations,
random injections, random regular graphs, and the configuration model
for random graphs of given fixed degree sequence.
This talk is complementary to Szekely's talk last semester. We focus
on new directions and provide those proofs left out by last talk.
(This is a joint work with Laszlo Szekely.)
Speaker: Josh Cooper, USC.
Title: WHERE DO POWER LAWS COME FROM: A MODEL-FREE ETIOLOGY
Abstract: We offer a much sought-after answer to the question, "Where do power laws come from?" which makes no reference to any particular model. Many random graph models have been studied in the past few years that give plausible growth processes for real-world massive graphs, and which provably yield power law degree sequences with high probability. However, there are so many different processes that produce power law degree distributions "in nature" that it is hard to see how even a large collection of parametric models could account for all the observed behaviors. Furthermore, many of the currently proposed models are not robust, in the sense that small perturbations of the growth rules cause the power law to disappear. We offer an alternative explanation that is inherently "model-free." In particular, we give a natural, rigorous definition of the oft-used term "scale-free" and show that it actually characterizes power law degree distributions. Since it is easy to see that massive graphs are generally scale-free in this sense, the resulting ubiquity of power laws is a consequence. We also find as a consequence a multitude of open questions ripe for study: scale-free hypergraphs and estimators for distributional exponents, for example.
Joint work with Lincoln Lu.