Seminars and Colloquia by Series

Cycles in sparse graphs

Series
Combinatorics Seminar
Time
Friday, November 12, 2010 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jacques Verstraete – University of California, San Diego

Please Note: **PLEASE NOTE SPECIAL TIME**

Let C(G) denote the set of lengths of cycles in a graph G. In this talk I shall present the recent proofs of two conjectures of P. Erdos on cycles in sparse graphs. In particular, we show that if G is a graph of average degree d containing no cycle of length less than g, then as d -> \infty then |C(G)| = \Omega(d^{\lfloor (g - 1)/2 \rfloor}). The proof is then adapted to give partial results on three further conjectures of Erdos on cycles in graphs with large chromatic number. Specifically, Erd\H{o}s conjectured that a triangle-free graph of chromatic number k contains cycles of at least k^{2 - o(1)} different lengths as k \rightarrow \infty. We define the {\em independence ratio} of a graph G by \iota(G) := \sup_{X \subset V(G)} \frac{|X|}{\alpha(X)}, where \alpha(X) is the independence number of the subgraph of G induced by X. We show that if G is a triangle free graph and \iota(G) \geq k, then |C(G)| = \Omega(k^2 \log k). This result is sharp in view of Kim's probabilistic construction of triangle-free graphs with small independence number. A number of salient open problems will be presented in conclusion. This work is in part joint with B. Sudakov. Abstract

Fractional perfect matchings in hypergraphs

Series
Combinatorics Seminar
Time
Friday, November 5, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Andrzej Rucinski – A. Mickiewicz University and Emory University
A perfect matching in a $k$-uniform hypergraph $H=(V,E)$ on $n$ vertices is a set of$n/k$ disjoint edges of $H$, whilea fractional perfect matching in $H$ is a function $w:E --> [0,1]$ such that for each $v\in V$ we have $\sum_{e\ni v} w(e) = 1.$ Given $n \ge 3$ and $3\le k\le n$, let $m$ be the smallest integer suchthat whenever the minimum vertex degree in $H$ satisfies $\delta(H)\ge m$ then $H$ contains aperfect matching, and let $m^*$ be defined analogously with respect to fractional perfectmatchings. Clearly, $m^*\le m$.We prove that for large $n$, $m\sim m^*$, and suggest an approach to determine $m^*$, andconsequently $m$, utilizing the Farkas Lemma. This is a joint work with Vojta Rodl.

Decimations of l-sequences and permutations of even residues mod p

Series
Combinatorics Seminar
Time
Friday, October 29, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Todd Cochrane – Math, Kansas State University
\ell-sequences are periodic binary sequences {a_i} that arise from Feedback with Carry Shift Registers and in many other ways. A decimation of {a_i} is a sequence of the form {a_{di}}. Goresky and Klapper conjectured that for any prime p>13 and any \ell-sequence based on p, every pair of allowable decimations of {a_i} is cyclically distinct. If true this would yield large families of binary sequences with ideal arithmetic cross correlations. The conjecture is essentially equivalent to the statement that if p>13 then the mapping x \to Ax^d on \mathbb Z/(p) with (d,p-1)=1, p \nmid A, permutes the even residues only if it is the identity mapping. We will report on the progress towards resolving this conjecture, focussing on our joint work with Bourgain, Paulhus and Pinner.

Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance

Series
Combinatorics Seminar
Time
Thursday, October 28, 2010 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Peter L.Erdos – Alfred Renyi Inst. of Mathematics, Budapest
In this talk we will report a short and transparent solution for the covering cost of white--grey trees which play a crucial role in the algorithm of Bergeron et al. to compute the rearrangement distance between two multi-chromosomal genomes in linear time (Theor. Comput. Sci., 410:5300-5316, 2009). In the process it introduces a new center notion for trees, which seems to be interesting on its own.

The Graph Removal Lemma

Series
Combinatorics Seminar
Time
Wednesday, October 20, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Jacob Fox – Math, MIT
Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

Binary subtrees with few path labels

Series
Combinatorics Seminar
Time
Thursday, October 14, 2010 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Kevin Milans – University of South Carolina
A rooted tree is _k-ary_ if all non-leaves have k children; it is_complete_ if all leaves have the same distance from the root. Let T bethe complete ternary tree of depth n. If each edge in T is labeled 0 or1, then the labels along the edges of a path from the root to a leafform a "path label" in {0,1}^n. Let f(n) be the maximum, over all{0,1}-edge-labeled complete ternary trees T with depth n, of the minimumnumber of distinct path labels on a complete binary subtree of depth nin T.The problem of bounding f(n) arose in studying a problem incomputability theory, where it was hoped that f(n)/2^n tends to 0 as ngrows. This is true; we show that f(n)/2^n is O(2^{-c \sqrt(n)}) forsome positive constant c. From below, we show that f(n) >= (1.548)^nfor sufficiently large n. This is joint work with Rod Downey, NoamGreenberg, and Carl Jockusch.

Long cycles in 3-connected graphs with bounded degrees

Series
Combinatorics Seminar
Time
Friday, October 8, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Guantao Chen – Department of Mathematics and Statistics, Georgia State University
In 1993 Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d \ge 4 then G has a cycle of length \Omega(n^{\log_{d-1} 2}). In this talk, I will report progresses on this conjecture and related problems.

Crossings and nestings of two edges in set partitions

Series
Combinatorics Seminar
Time
Friday, September 24, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Svetlana Poznanovikj – SoM, Georgia Tech
A set partition of [n] can be represented graphically by drawing n dots on a horizontal line and connecting the points in a same block by arcs. Crossings and nestings are then pairs of arcs that cross or nest. Let G be an abelian group, and \alpha, \beta \in G. In this talk I will look at the distribution of the statistic s_{\alpha, \beta} = \alpha * cr + \beta * ne on subtrees of the tree of all set partitions and present a result which says that the distribution of s_{\alpha, \beta} on a subtree is determined by its distribution on the first two levels.

Diamond-free Families

Series
Combinatorics Seminar
Time
Friday, September 17, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jerry Griggs, Carolina Distinguished Professor and Chair – Mathematics, University of South Carolina
Given a finite poset $P$, we consider the largest size ${\rm La}(n,P)$ of a family of subsets of $[n]:=\{1,\ldots,n\}$ that contains no  subposet $HP.  Sperner's Theorem (1928) gives that ${\rm La}(n,P_2)= {n\choose{\lfloor n/2\rfloor}}$,  where $P_2$ is the two-element chain.    This problem has been studied intensively in recent years, and it is conjectured that $\pi(P):=  \lim_{n\rightarrow\infty} {\rm La}(n,P)/{n\choose{\lfloor n/2\rfloor}}$  exists for general posets $P$, and, moreover, it is an integer. For $k\ge2$ let $D_k$ denote the $k$-diamond poset $\{A< B_1,\ldots,B_k < C\}$. We study the average number of times a random full chain meets a $P$-free family, called the Lubell function, and use it for $P=D_k$ to determine  $\pi(D_k)$ for infinitely many values $k$.  A stubborn open problem is to show that $\pi(D_2)=2$; here we prove $\pi(D_2)<2.273$ (if it exists).    This is joint work with Wei-Tian Li and Linyuan Lu of University of South Carolina.

On randomizing two derandomized greedy algorithms

Series
Combinatorics Seminar
Time
Friday, September 10, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Kevin Costello – SoM, Georgia Tech
Many of the simplest and easiest implemented approximation algorithms can be thought of as derandomizations of the naive random algorithm.  Here we consider the question of whether performing the algorithm on a random reordering of the variables provides an improvement in the worst case expected performance. (1) For Johnson's algorithm for Maximum Satisfiability, we show this is indeed the case: While in the worst case Johnson's algorithm only provides a 2/3 approximation, the additional randomization step guarantees a 2/3+c approximation for some positive c. (2) For the greedy algorithm for MAX-CUT, we show to the contrary that the randomized version does NOT provide a 1/2+c approximation for any c on general graphs. This is in contrast to a result of Mathieu and Schudy showing it provides a 1-epsilon approximation on dense graphs. Joint with Asaf Shapira and Prasad Tetali.

Pages