Seminars & Events for Discrete Mathematics Seminar

December 6, 2007
2:15pm - 4:15pm
Critical triangle-free graphs with lots of edges

How close are the triangle-free graphs to the bipartite graphs? The different ways of asking this question give different answers. For example: on the one hand, triangle-free graphs can have arbitrarily large chromatic number; on the other, natural constructions to demonstrate this fact are typically very sparse. One type of question with this theme is the recently solved question of Erdos and Simonovits, which asks about triangle-free graphs with large chromatic number and large minimum degree.

Speaker: Wesley Pegden, Rutgers University
Location:
Fine Hall 224
February 7, 2008
2:15pm - 4:15pm
The circular chromatic index of graphs of high girth

Colorings of graphs form a prominent topic in graph theory. Several relaxations of usual colorings have been introduced and intensively studied. In this talk, we focus on circular colorings. A proper circular k-coloring, for a real $k\ge 1$, is a coloring by real numbers from the interval $[0,k)$ such that the difference modulo $k$ of the colors $c_1$ and $c_2$ assigned to adjacent vertices is at least one, i.e., $1\le |c_1-c_2|\le k-1$. It is easy to observe that the chromatic number of a graph is always the ceiling of its circular chromatic number.

Speaker: Daniel Král', Charles University, Prague
Location:
Fine Hall 314
February 14, 2008
2:15pm - 4:15pm
Ramsey numbers of sparse graphs and hypergraphs

The Ramsey number $r(G)$ of a graph $G$ is the minimum $N$ such that every 2-coloring of the edges of the complete graph on $N$ vertices contains a monochromatic copy of $G$. Determining or estimating Ramsey numbers is one of the central problem in Ramsey theory. Besides the complete graph, the next most classical topic in this area concerns the Ramsey number of sparse graphs. The study of these Ramsey numbers was initiated by Burr and Erdos in 1975, and this topic has since placed a central role in graph Ramsey theory. In this talk we will discuss recent progress in this area. Joint work with Benny Sudakov.

Speaker: Jakob Fox, Princeton University
Location:
Fine Hall 314
February 22, 2008
2:15pm - 4:15pm
Isomorphic uniform convexity in metric spaces

In 1985 Bourgain gave a discrete metric characterization of when a normed space admits an equivalent uniformly convex norm: this happens if and only if the space does not contain arbitrarily large complete binary trees with low distortion. Bourgain's theorem was the first successful step in a research program that was inspired by a theorem of Ribe from 1976, which suggested that certain linear properties of normed spaces are actually metric properties in disguise. In this talk we will revisit Bourgain's solution in a quantitative way: we will obtain a metric characterization of the degree to which a norm is uniformly convex. It turns out that this question exhibits unexpected subtleties and surprising differences from the linear theory of normed spaces and from the theory of metric type and cotype.

Speaker: Assaf Naor, Courant Institute, NYU
Location:
Fine Hall 214
February 28, 2008
2:15pm - 4:15pm
Run time bounds for a model related to sieving

The following problem is very close to one arising in factorization algorithms.

Generate random numbers in the interval $[1,N]$ until some subset has a product which is a square. How long does this take (and how can you tell when you're done)?

Crude analogies suggest that this stopping time has a very sharp threshold. We prove upper and lower bounds that are within a factor of $4/\pi$ and conjecture that our upper bound is asymptotically sharp. Joint work with Andrew Granville, Ernie Croot and Prasad Tetali.

Speaker: Robin Pemantle, Tel-Aviv University and IAS
Location:
Fine Hall 314
March 6, 2008
2:15pm - 4:15pm
Star-coloring planar graphs with high girth

A star-coloring is a proper vertex-coloring such that the graph induced by the union of any 2 color classes is a star-forest. Equivalently, it is a proper vertex-coloring with no 2-colored $P_4$. Star-coloring has been studied extensively, even for planar graphs. However, little is known about improved upper bounds for planar graphs with large girth. We prove that a planar graph with girth at least 13 has star-chromatic number at most 4. We use the discharging method to prove a structural lemma about planar graphs with girth at least 13. It is then straightforward to construct the 4-star-coloring using this lemma. This is joint work with Craig Timmons and Andre Kundgen of Cal State, San Marcos.

Speaker: Dan Cranston, Rutgers University and Bell Labs
Location:
Fine Hall 314
March 13, 2008
2:15pm - 4:15pm
Sumsets in finite fields and Cayley sum graphs

I will sketch a proof of the fact that for a prime $p$, every complement of a set of roughly $\sqrt{p}$ elements of the finite field $Z_p$ is a sumset, that is, is of the form $A+A$, whereas there are complements of sets of size roughly $p^{2/3}$ which are not sumsets. This improves estimates of Green and Gowers, and can also be used to settle a recent problem of Nathanson. The proofs combine probabilistic arguments with properties of Cayley sum graphs derived from their eigenvalues.

Speaker: Noga Alon, Tel-Aviv University and IAS
Location:
Fine Hall 314
April 3, 2008
2:15pm - 4:15pm
Points Surrounding the Origin
Speaker: János Pach, Courant Institute, NYU
Location:
Fine Hall 314
April 10, 2008
2:15pm - 4:15pm
Averaging Points Two at a Time

In 2006 Brendan McKay asked the following on sci.math.research: We have n points in a disk centered at the centroid of the points. We successively replace the two furthest points from each other by two copies of their average. (After each move we still have n points with the same centroid. How many moves are necessary to guarantee that all points lie in the concentric disk of half the radius?

This really is the wrong question: it turns out that the situation is easier to study of we use a general Euclidean space and look at the rate of decay of the diameter in terms of number of moves. We get sharp asymptotic upper and lower bounds on the maximum diameter after certain numbers of moves. This involves interesting geometrical configurations and simple linear-programming arguments.

Speaker: David Moulton, IDA-CCR
Location:
Fine Hall 314
April 17, 2008
2:15pm - 4:15pm
The Finite Field Kakeya Problem

If V is a vector space over the field with q elements, a (finite field) Kakeya set is a subset of V containing a line in every direction. The main problem is to determine how large such a set is forced to be. Recently, Zeev Dvir gave a simple proof of the correct order of magnitude of Kakeya sets by introducing a nice technique from algebraic geometry. This new idea has provided a great deal of excitement. In this talk, I'll survey what is known about the problem (relatively little given that it is 10 years old), and then discuss some of the low-hanging combinatorial fruit in the case where V has dimension 2.

Speaker: Xander Faber, Columbia University
Location:
Fine Hall 314
April 25, 2008
2:15pm - 4:15pm
An Elegant and Insightful Direct Combinatorial Proof of the Arithmetical Identity 4+5=2+7

There are no trivial theorems, only trivial mathematicians (those who believe that there exist trivial theorems). Being a non-trivial mathematician myself, I will present a new, elegant, and very insightful direct combinatorial proof of the seemingly (to most people) "trivial" arithmetical theorem that states that four plus five equals two plus seven. More important, the methodology should extend to give insightful direct combinatorial proofs of even deeper identities, like (4+6+200+6+50)+(3+10+30+5)=300+4+10.

Speaker: Doron Zeilberger, Rutgers University
Location:
Fine Hall 110
May 1, 2008
2:15pm - 4:15pm
The structure of bullfree graphs

The bull is a graph consisting of a triangle and two disjoint pendant edges. Obvious examples of bullfree graphs are graphs with no triangle, or graphs with no stable set of size three. But there are others (for example, substituting one bullfree graph into another produces a bullfree graph). It turns out, however, that one can explicitly describe all bullfree graphs that cannot be constructed from smaller ones by substitutions. In this talk we will discuss this construction. We will also mention the connection with the Erdos-Hajnal conjecture.

Speaker: Maria Chudnovsky, Columbia University and Clay Mathematics Institute (CMI)
Location:
Fine Hall 314