Seminars and Colloquia by Series

Friday, September 9, 2011 - 15:05 , Location: Skiles 005 , Laszlo Vegh , School of Computer Science, Georgia Tech , , Organizer: Prasad Tetali
The generalized flow model is a classical and widely applicable extension of network flows, where on every arc, the flow leaving the arc is a linear function of the flow entering the arc. In the talk, I will investigate a nonlinear extension of this model, with the flow leaving an arc being a concave function of the entering flow. I exhibit the first combinatorial polynomial time algorithm for solving corresponding optimization problems. This model turns out to be a common framework for solving several market equilibrium problems, such as linear Fisher markets, and immediately enables to extend them to more general settings. I will also give a survey on generalized flow algorithms and previous nonlinear flow models.
Friday, May 6, 2011 - 15:05 , Location: Skiles 006 , Amanda Pascoe Streib , Georgia Tech , Organizer: Prasad Tetali
Colloids are mixtures of molecules  well-studied in material science that are not well-understood mathematically.  Physicists model colloids as a system of two types of tiles (type A and type B) embedded on a region of the plane, where no two tiles can overlap.  It is conjectured that at high density, the type A tiles tend to separate out and form large "clusters".   To verify this conjecture, we need methods for counting these configurations directly or efficient algorithms for sampling.  Local sampling algorithms are known to be inefficient. However, we provide the first rigorous analysis of a global "DK Algorithm" introduced by Dress and Krauth.  We also examine the clustering effect directly via a combinatorial argument. We prove for a certain class of colloid models that at high density the configurations are likely to exhibit clustering, whereas at low density the tiles are all well-distributed. Joint work with Sarah Miracle and Dana Randall.
Friday, April 29, 2011 - 15:05 , Location: Skiles 006 , Will Perkins , Courant Institute, NYU , , Organizer: Prasad Tetali
The Bohman-Frieze process is a simple modification of the Erdős-Rényi random  graph that adds dependence between the edges biased in favor of joining  isolated vertices. We present new results on the phase transition of the  Bohman-Frieze process and show that qualitatively it belongs to the same  class as the Erdős-Rényi process. The results include the size and structure  of small components in the barely sub- and supercritical time periods. We  will also mention a class of random graph processes that seems to exhibit  markedly different critical behavior.
Friday, April 22, 2011 - 15:05 , Location: Skiles 006 , Elena Grigorescu , College of Computing, Georgia Tech , Organizer: Xingxing Yu
In the Property Testing model an algorithm is required to distinguish between the case that an object has a property or is far from having the property. Recently, there has been a lot of interest in understanding which properties of Boolean functions admit testers making only a constant number of queries, and a common theme investigated in this context is linear invariance. A series of gradual results has led to a conjectured characterization of all testable linear invariant properties. Some of these results consider properties where the query upper bounds are towers of exponentials of large height dependent on the distance parameter. A natural question suggested by these bounds is whether there are non-trivial families with testers making only a polynomial number of queries in the distance parameter.In this talk I will focus on a particular linear-invariant property where this is indeed the case: odd-cycle freeness.Informally, a Boolean function fon n variables is odd-cycle free if there is no x_1, x_2, .., x_2k+1 satisfying f(x_i)=1 and sum_i x_i = 0.This property is the Boolean function analogue of bipartiteness in the dense graph model. I will discuss two testing algorithms for this property: the first relies on graph eigenvalues considerations and the second on Fourier analytic techniques. I will also mention several related open problems. Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra, Asaf Shapira
Friday, April 15, 2011 - 15:00 , Location: Skiles 006 , Nathan Reading , North Carolina State University , Organizer: Christine Heitsch
A rectangulation is a tiling of a rectangle by rectangles.  The rectangulation is called generic if no four of its rectangles share a corner.  We will consider the problem of counting generic rectangulations (with n rectangles) up to combinatorial equivalence. This talk will present and explain an initial step in the enumeration: the fact that generic rectangulations are in bijection with permutations that avoid a certain set of patterns.  I'll give background information on rectangulations and pattern avoidance. Then I'll make the connection between generic rectangulations and pattern avoiding permutations, which draws on earlier work with Shirley Law on "diagonal" rectangulations. I'll also comment on two theories that led to this result and its proof: the lattice theory of the weak order on permutations and the theory of combinatorial Hopf algebras.
Friday, April 1, 2011 - 15:05 , Location: Skiles 006 , Sangjune Lee , Emory University , Organizer: Xingxing Yu
A set~$A$ of integers is a \textit{Sidon set} if all thesums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$, aredistinct.  In the 1940s, Chowla, Erd\H{o}s and Tur\'an determinedasymptotically the maximum possible size of a Sidon set contained in$[n]=\{0,1,\dots,n-1\}$.  We study Sidon sets contained in sparserandom sets of integers, replacing the `dense environment'~$[n]$ by asparse, random subset~$R$ of~$[n]$.Let~$R=[n]_m$ be a uniformly chosen, random $m$-element subsetof~$[n]$.  Let~$F([n]_m)=\max\{|S|\colon S\subset[n]_m\hbox{  Sidon}\}$.  An abridged version of our results states as follows.Fix a constant~$0\leq a\leq1$ and suppose~$m=m(n)=(1+o(1))n^a$.  Thenthere is a constant $b=b(a)$ for which~$F([n]_m)=n^{b+o(1)}$ almostsurely.  The function~$b=b(a)$ is a continuous, piecewise linearfunction of~$a$, not differentiable at two points:~$a=1/3$and~$a=2/3$; between those two points, the function~$b=b(a)$ isconstant.
Friday, March 4, 2011 - 15:05 , Location: Skiles 006 , Martin Loebl , Charles University, Prague, Czech Republic , Organizer: Robin Thomas
The Ising problem on finite graphs is usually treated by a reduction to the dimer problem. Is this a wise thing to do? I will show two (if time allows) recent results indicating that the Ising problem allows better mathematical analysis than the dimer problem. Joint partly with Gregor Masbaum and partly with Petr Somberg.
Friday, February 25, 2011 - 15:05 , Location: Skiles 006 , Hehui Wu , University of Illinois at Urbana-Champaign , Organizer: Xingxing Yu
The Chv\'atal--Erd\H{o}s Theorem states that every graph whose connectivityis at least its independence number has a spanning cycle.  In 1976, Fouquet andJolivet conjectured an extension: If $G$ is an $n$-vertex $k$-connectedgraph with independence number $a$, and $a \ge k$, then $G$ has a cycle of lengthat least $\frac{k(n+a-k)}{a}$.  We prove this conjecture. This is joint work with Suil O and Douglas B. West.
Friday, February 18, 2011 - 15:05 , Location: Skiles 006 , Ernie Croot , School of Math. Georgia Tech. , Organizer: Xingxing Yu
Fix a subset A of the group of integers mod N.  In this talkI will discuss joint work with Izabella Laba, Olof Sisask and myselfon the length of the longest arithmetic progression in the sumset A+Ain terms of the density of the set A.  The bounds we develop improve uponthe best that was previously known, due to Ben Green.
Friday, February 11, 2011 - 15:05 , Location: Skiles 006 , Kevin Costello , School of Mathematics, Georgia Tech , Organizer: Xingxing Yu
We consider the question of coloring the first n integers with two colors in such a way as to avoid copies of a given arithmetic configuration (such as 3 term arithmetic progressions, or solutions to x+y=z+w). We know from results of Van der Waerden and others that avoiding such configurations completely is a hopeless task if n is sufficiently large, so instead we look at the question of finding colorings with comparatively few monochromatic copies of the configuration. At the very least, can we do significantly better than just closing our eyes and coloring randomly? I will discuss some partial answers, experimental results, and conjectured answers to these questions for certain configurations based on joint work with Steven Butler and Ron Graham.