UIUC Dept. of Mathematics Seminar Calendar

      July 2009             August 2009           September 2009   
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
           1  2  3  4                      1          1  2  3  4  5
  5  6  7  8  9 10 11    2  3  4  5  6  7  8    6  7  8  9 10 11 12
 12 13 14 15 16 17 18    9 10 11 12 13 14 15   13 14 15 16 17 18 19
 19 20 21 22 23 24 25   16 17 18 19 20 21 22   20 21 22 23 24 25 26
 26 27 28 29 30 31      23 24 25 26 27 28 29   27 28 29 30         
                        30 31

Tuesday, September 1, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 1, 2009

Del

Edit

Copy

Submitted by west.

Jozsef Balogh (UIUC Math and University of California-San Diego)
Hamiltonicity of random geometric graphs
Abstract: We prove that, in the Gilbert model for a random geometric graph, almost every graph becomes Hamiltonian exactly when it first becomes 2-connected. This proves a conjecture of Penrose. We also show that in the k-nearest neighbour model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle. (This is joint work with B. Bollobas, M. Krivelevich, T. Muller, and M. Walters.)

Tuesday, September 8, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 8, 2009

Del

Edit

Copy

Submitted by west.

Douglas B. West (UIUC Math)
Degree lists for graphs
Abstract: A list of nonnegative integers is graphic if it is the list of vertex degrees of a graph (no loops or multiple edges). Many characterizations of graphic lists are known, the most famous being that of Erdős and Gallai: a list d in nonincreasing order is graphic if and only if certain obviously necessary conditions hold, which are that the list has even sum and that the Erdős-Gallai Condition ∑_1≤i≤kd_i ≤ k(k-1)+∑_k+1≤i≤nmin{k,d_i} holds for every k. We present a new short proof of this characterization (Tripathi-Venugopalan-West) and a new characterization (Isaak-West), which states that d is graphic if and only if for all disjoint sets I and J of indices, ∑_i∈Id_i+∑_j∈J(n-1-d_j) ≥ |I| |J|. The talk is elementary, requiring no more background than knowing what a graph is.

Tuesday, September 15, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 15, 2009

Del

Edit

Copy

Submitted by west.

Frank Bernhart (visitor)
Four Color Problem - Unfinished Business
Abstract: The Four Color Conjecture (4CC) was settled using the classical approach of Kempe and G.D. Birkhoff, aided by computers and some ideas of Heesch. Within this narrow focus there are still a number of loose ends and odd facts. We will give a brief survey of ideas and methods that seem to deserve further exploration. The flattening equations of chromial theory is one such area, the use of open sets and splicing to study reduction is another. Somewhere near the midpoint of the these two approaches is the linear program of the N-ring, a problem of finding all the extreme points of a finite bounded polytope. In the mix lies a hint or two that the massive use of computers in the 4CC proof may one day give way to recursive techniques.

Tuesday, September 22, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 22, 2009

Del

Edit

Copy

Submitted by west.

John Lenz (UIUC Math)
Complete Minors, Independent Sets, and Chordal Graphs
Abstract: The Hadwiger number h(G) of a graph G is the maximum t such that K_t is a minor of G. Hadwiger's Conjecture from 1943 states that h(G) ≥ χ(G). Hadwiger's Conjecture for chromatic number 4 was proved by Dirac, the case χ(G)=5 was shown equivalent to the Four Color Theorem by Wagner, and the case χ(G)=6 was shown equivalent to the Four Color Theorem by Robertson et al. Hadwiger's Conjecture for χ(G) ≥ 7 remains open. Since every color class is an independent set, χ(G)α(G) ≥ |V(G)|. Thus Hadwiger's Conjecture implies that h(G) ≥ |V(G)|/α(G). We will discuss lower bounds on h(G) in terms of α(G), such as our bound h(G) ≥ |V(G)|/(2α(G)-clog(α(G))), where c is a particular constant. (This is joint work with Hehui Wu and Jozsef Balogh.)

Tuesday, September 29, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 29, 2009

Del

Edit

Copy

Submitted by west.

Jozsef Balogh (University of Illinois and University of California-San Diego)
The Typical Structure of Graphs without Given Excluded Subgraphs
Abstract: Let L be a finite family of graphs. We describe the typical structure of graphs having no subgraph in L, which we call L-free graphs. This further improves our earlier results on the Erdős-Frankl-Rödl theorem. Let p(L) = min_L∈L χ(L)-1. We prove that the structure of almost all graph L-free graphs is very similar to the Turán graph T_n,p, where "similarity" is measured in terms of graph-theoretic parameters of L. Some more recent developments, including extensions for induced containment, bipartite graphs, and hypergraphs will be discussed as well. This work is partially joint work with Alon, Bollobás, Butterfield, Morris, Mubayi, Samotij, and Simonovits.

Tuesday, October 6, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 6, 2009

Del

Edit

Copy

Submitted by west.

Kevin Milans (UIUC Math)
Acyclic sets in k-majority tournaments
Abstract: Given a set S of permutations of a ground set X, the majority digraph of S is the directed graph on X where there is an edge from u to v when a majority of the permutations in S rank u above v. For odd k, a k-majority tournament is a tournament that arises as the majority digraph of a set of k permutations. Alon, Brightwell, Kierstead, Kostochka, and Winkler proved that for some constant c, every k-majority tournament contains a dominating set of size at most cklogk.

We study the maximum size of an acyclic set of vertices in k-majority tournaments. Every n-vertex 3-majority tournament contains an acyclic set of size n^1/2; we present a family of 3-majority tournaments that have no acyclic sets of size larger than 2n^1/2. We show that every n-vertex 5-majority tournament contains an acyclic set of size n^1/4. For general k, every k-majority tournament contains an acyclic set of n^f(k), where f(k) = 3^-(k-1)/2. This is joint work with Dan Schreiber and Douglas B. West.

Tuesday, October 13, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 13, 2009

Del

Edit

Copy

Submitted by west.

Dominic Searles (UIUC Math)
Comparative probability orders and the flip relation
Abstract: A comparative probability order is a linear order on the subsets of a finite set X, starting with ∅, such that whenever A precedes B and C∩(A∪B) = ∅, also A∪C precedes B∪C. These orders have been used to study betting behaviour, where an agent believes some events are more likely than others and bets accordingly.

Nonempty disjoint sets A and B that are consecutive in a c.p.o are flippable if for every C such that C∩(A∪B)=∅, the sets A∪C and B∪C are also consecutive. Exchanging the two sets in a flippable pair (and the pairs A∪C and B∪C such that C∩(A∪B)=∅) yields an "adjacent" comparative probability order. We will describe representations of comparative probability orders such as discrete cones and geometric polytopes, explain what the flip relation represents in these contexts, and discuss a conjecture about the maximum number of neighbours (under flipping) a comparative probability order may have.

Tuesday, October 20, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 20, 2009

Del

Edit

Copy

Submitted by west.

Paul Wenger (UIUC Math)
Uniquely H-saturated graphs
Abstract: For a fixed graph H, a graph G is uniquely H-saturated if G does not contain H as a subgraph, but the addition to G of any missing edge completes exactly one copy of H in G. We examine uniquely H-saturated graphs when H is a path or a small cycle. In particular, we prove that there are only nine uniquely C₄-saturated graphs, all of which have at most nine vertices. Doing so includes an algebraic proof using eigenvalues of graphs that there is only one such graph with girth 5. This is joint work with Joshua Cooper, Timothy LeSaulnier and Douglas B. West.

Tuesday, October 27, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 27, 2009

Del

Edit

Copy

Submitted by west.

Suil O (UIUC Math)
Matchings, edge-connectivity and eigenvalues in regular graphs
Abstract: The matching number of a graph is the maximum size of a matching in it. We previously characterized the graphs having the smallest maximum number among connected (2k+1)-regular graphs with n vertices; the extremal graphs have cut-edges. In this talk, we prove a lower bound for the maximum matching in a t-edge-connected r-regular graph with n vertices, for t≥ 2 and r≥ 4; various special cases were obtained earlier. We also characterize the graphs achieving equality.

We also study the relationship between eigenvalues and matchings in t-edge-connected r-regular graphs. We give a condition on anappropriate eigenvalue that guarantees a lower bound on the matching number in a t-edge-connected r-regular graph; this generalizes a recent result of Cioaba, Gregory, and Haemers.

Tuesday, November 3, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, November 3, 2009

Del

Edit

Copy

Submitted by west.

Timothy LeSaulnier (Department of Mathematics, University of Illinois)
Rainbow matchings in edge-colored graphs
Abstract: The color degree of a vertex v in an edge-colored graph is the number of distinct colors appearing on edges incident to v. A rainbow subgraph is a subgraph whose edges receive distinct colors. Wang and Li proved that every edge-colored graph with minimum color degree at least k contains a rainbow matching of size at least ⌈(5k-3)/12⌉. They conjectured that in fact there must be a rainbow matching of size at least ⌈k/2⌉. Toward this conjecture, we prove that every edge-colored graph with minimum color degree k contains a rainbow matching of size at least ⌊k/2⌋. In addition, we prove the full conjecture for triangle-free graphs and show that if a properly edge-colored graph G with minimum color degree k does not contain a rainbow matching of size ⌈k/2⌉, then G is a complete graph minus a matching. (This is joint work with Christopher Stocker, Paul Wenger, and Douglas B. West.)

Tuesday, November 10, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, November 10, 2009

Del

Edit

Copy

Submitted by west.

Douglas B. West (Department of Mathematics, University of Illinois)
Decomposition of sparse graphs
Abstract: The maximum average degree of a graph is the maximum, over all subgraphs, of the average vertex degree in the subgraph. Let k be a nonnegative integer, and let m_k=4(k²+4k+3)/(k²+6k+6). We prove that every graph with maximum average degree less than m_k decomposes into a forest and a subgraph with maximum degree at most k. The proof is by the discharging method. The result is joint work with Mickael Montassier, Arnaud Pecher, Andre Raspaud, and Xuding Zhu.

The motivation for our result is its application to the misnamed parameter game coloring number, written col_g(G). Alice and Bob alternately choose vertices, producing an ordering. The value of col_g(G) is 1+d, where Alice can guarantee that every vertex has at most d earlier neighbors in the ordering and cannot guarantee fewer. Faigle et al. proved that col_g(T)≤ 4 when T is a forest, and Zhu proved that col_g(G)≤ col_g(G₁)+Δ(G₂) when G decomposes into G₁ and G₂. Hence our result implies that every graph with maximum average degree less than m_k has game coloring number at most 4+k.

Tuesday, November 17, 2009

Tuesday, December 1, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, December 1, 2009

Del

Edit

Copy

Submitted by west.

John Lenz (UIUC Math)
The Density Hales-Jewett Theorem
Abstract: The Hales-Jewett Theorem asserts that for every r and k there exists n such that every r-coloring of the n-dimensional grid [k]ⁿ contains a monochromatic line. This result generalizes van der Waerden's Theorem. van der Waerden's Theorem has a famous density version, conjectured by Erdős and Turán in 1936 and proved by Szemerédi in 1975. The Hales-Jewett Theorem has a density version as well, proved by Furstenberg and Katznelson in 1991 using techniques from ergodic theory. A recent paper by the polymath1 project [1] provides the first combinatorial proof of the density Hales-Jewett Theorem. The proof is surprisingly simple: it avoids using the Regularity Lemma, the Fourier transform, or Szemeredi's Theorem.
[1] - http://michaelnielsen.org/polymath1/index.php?title=Main_Page

Tuesday, December 8, 2009

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, December 8, 2009

Del

Edit

Copy

Submitted by west.

Kevin G. Milans (UIUC Math)
Degree Ramsey numbers of graphs
Abstract: In Ramsey theory, we study when every partition of a large structure yields a part with additional structure. For example, Van der Waerden's Theorem states that every s-coloring of the integers contains arbitrarily long monochromatic arithmetic progressions, and the Hales-Jewett Theorem guarantees that every game of tic-tac-toe in high dimensions has a winner. Ramsey's Theorem implies that for any target graph G, every s-coloring of the edges of some sufficiently large host graph contains a monochromatic copy of G. In Ramsey's Theorem, the host graph is dense (in fact complete). We explore conditions under which the host graph can be sparse and still force a monochromatic G.

A graph H arrows a graph G if every 2-edge-coloring of H contains a monochromatic copy of G. The degree Ramsey number of G is the minimum k such that some graph with maximum degree k arrows G. Burr, Erdős, and Lovász found the degree Ramsey number for stars and complete graphs. We establish the degree Ramsey number exactly for double stars and for C₄, the cycle on four vertices. We prove that the degree Ramsey number of the cycle C_n is at most 108 when n is even and at most 3890 in general. Consequently, there are very sparse graphs that arrow large cycles. We present a family of graphs in which the degree Ramsey number of G is bounded by a function of the maximum degree of G and ask which graph families have this property. This is joint work with Tao Jiang, Bill Kinnersley, and Douglas B. West.

Tuesday, January 26, 2010

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, January 26, 2010

Del

Edit

Copy

Submitted by west.

Alexandr Kostochka (UIUC Math)
A stability theorem on fractional covering of triangles by edges
Abstract: Let ν(G) denote the maximum number of edge-disjoint triangles in a graph G, and let τ*(G) denote the minimum total weight of a fractional covering of its triangles by edges. Trivially, τ*(G)≥ν(G). Krivelevich proved that τ*(G)≤2ν(G) for every graph G. Sharpness is shown by the complete graph K₄, since ν(K₄)=1 and τ*(K₄)=2. We refine this result by showing that if τ*(G)≥2ν(G)-x, then G contains ν(G)-⌊10x⌋ edge-disjoint copies of K₄ plus ⌊10x⌋ additional edge-disjoint triangles. These subgraphs witness that τ*(G)≥2ν(G)-⌊10x⌋. Our proof also yields τ*(G)≤ 1.8ν(G) for each K₄-free graph G. This is joint work with P. Haxell and S. Thomassé.

Tuesday, February 2, 2010

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, February 2, 2010

Del

Edit

Copy

Submitted by west.

Paul Wenger (UIUC Math)
Cycle Saturation in Graphs
Abstract: Given two graphs G and H, we say that G is H-saturated if G does not contain H but the addition of any edge to G completes a copy of H. In this talk we consider this notion when H is a cycle, along with a natural generalization for a family of cycles. In particular, we asymptotically determine the minimum number of edges in n-vertex graphs that are saturated with respect to having a cycle of length at least k. We also study whether nontrivial examples exist in which the addition of any edge completes exactly one cycle of length k. This is joint work with Joshua Cooper, Michael Ferrara, Michael Jacobson, John Lenz, Timothy LeSaulnier, Kevin Milans, Craig Tennenhouse, and Douglas B. West.

Tuesday, February 9, 2010