UIUC Dept. of Mathematics Seminar Calendar

     October 2009          November 2009          December 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    1  2  3  4  5  6  7          1  2  3  4  5
  4  5  6  7  8  9 10    8  9 10 11 12 13 14    6  7  8  9 10 11 12
 11 12 13 14 15 16 17   15 16 17 18 19 20 21   13 14 15 16 17 18 19
 18 19 20 21 22 23 24   22 23 24 25 26 27 28   20 21 22 23 24 25 26
 25 26 27 28 29 30 31   29 30                  27 28 29 30 31

Tuesday, January 27, 2009

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

Del

Edit

Copy

Submitted by west.

Douglas B. West (UIUC Math)
On the 1,2-Conjecture and its list analogue
Abstract: Label the edges of a graph with integers, and let the color of a vertex be the sum of the labels on its incident edges. The 1,2,3-Conjecture of Karoński, Łuczak, and Thomason states that the edges of any graph having no isolated edge can be labeled from {1,2,3} so that adjacent vertices have different colors. When labels are also given to vertices, and the vertex color sum the labels on the vertex and its incident edges, the 1,2-Conjecture of Przybyło and Woźniak states that labels in {1,2} suffice for every graph.

This talk will report on recent results about these conjectures heard (not proved) by the speaker at a workshop this month in Taiwan. Toward the 1,2-Conjecture, Kalkowski proved that it suffices to have labels in {1,2} for vertices and labels in {1,2,3} for edges. Toward the 1,2,3-Conjecture, Kalkowski, Karoński, and Pfender proved that labels in {1,2,3,4,5} suffice.

Meanwhile, Wong, Yang, and Zhu proposed a stronger list analogue of the 1,2-Conjecture. They conjecture that if each vertex and edge is assigned a list of two integers, then it is possible to choose labels from the lists so that the sums are distinct at adjacent vertices. They have proved this for trees, for complements of linear forests, for complete bipartite graphs, etc.

Tuesday, February 3, 2009

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

Del

Edit

Copy

Submitted by west.

Nitish Korula (Department of Computer Science, University of Illinois)
Preserving element-connectivity and packing Steiner trees
Abstract: Given an undirected graph G and a set of terminals T in V(G), the local element-connectivity of two terminals u, v ∈ T is the maximum number of u,v-paths that pairwise share no edges and no non-terminals. The local element-connectivity is at least the local edge-connectivity and at most the local vertex-connectivity. Element-connectivity can help bridge the gap between edge- and vertex-connectivity problems, particularly in algorithmic contexts. We show that a graph reduction operation of Hind and Oellerman preserves local element-connectivity for all pairs of terminals; repeated use of it leads to a bipartite graph with the same local element-connectivities. We apply element-connectivity and the reduction operation to packing of Steiner trees, where a Steiner tree for a set of terminals T is a subtree of G that spans T.

Nash-Williams and Tutte gave proofs that every 2k-edge-connected graph contains k edge-disjoint spanning trees. Lap Chi Lau proved that if a set of terminals T in G is pairwise 24k-edge-connected, then G contains k edge-disjoint Steiner trees for T; 24k was improved to 8.5k by West and Wu. We consider the problem of packing vertex-disjoint Steiner trees, meaning that each tree contains the terminal set T, but trees do not share non-terminal vertices. The element-connectivity is an obvious upper bound on the number of disjoint Steiner trees, but O(k) element-connectivity does not guarantee k disjoint Steiner trees; O(k log n) element-connectivity may be needed, and it is always sufficient. In planar graphs, we show that (5k+5)-element-connectivity suffices to pack k vertex-disjoint Steiner trees. Similar results also apply to packing Steiner trees in graphs of bounded genus or bounded treewidth.

Tuesday, February 10, 2009

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

Del

Edit

Copy

Submitted by west.

Wojciech Samotij (Department of Mathematics, University of Illinois)
Counting graphs without a fixed subgraph
Abstract: A graph is H-free if it has no subgraph isomorphic to H. Denote by f_n(H) the number of (labeled) H-free graphs on a fixed set of n vertices. Since every subgraph of an H-free graph is also H-free, immediately f_n(H)≥ 2^ex(n,H), where ex(n,H) is the maximum number of edges in an H-free graph with n vertices. Erdős conjectured that when H contains a cycle, this trivial lower bound is in a sense tight; that is, f_n(H) = 2^{(1+o(1))ex(n,H)}.

This conjecture initiated a series of deep and interesting results in the topic of counting graphs without a fixed subgraph. This talk will give an overview of the current progress in the asymptotic study of H-free graphs, focusing on the (seemingly harder) case of bipartite H.

Tuesday, February 17, 2009

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

Del

Edit

Copy

Submitted by west.

Kevin Milans (Department of Mathematics, University of Illinois)
Toward a conjecture on removing cycles in triangle-free digraphs
Abstract: Let G be a digraph obtained from a tournament by deleting k edges. Chudnovsky, Seymour, and Sullivan proved that if G does not contain a directed triangle, then it is possible to obtain an acyclic subdigraph of G by removing an additional k edges. They conjectured that in fact an acyclic subdigraph can be obtained by removing at most k/2 additional edges; if true, this would be tight. Recently, Dunkum, Hamburger, and Pór improved the CSS result by showing that it suffices to remove 0.88k additional edges.

We provide an introduction to the problem and outline the proofs of Chudnovsky et. al. and Dunkum et. al. using a common framework.

Tuesday, February 24, 2009

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

Del

Edit

Copy

Submitted by west.

Ida Kantor (UIUC Math)
Sum choice number of complete bipartite graphs
Abstract: An integer valued function f defined on the vertices of a graph G is called a choice function if, whenever lists of sizes f(v) are assigned to the vertices, we can choose a proper coloring of G using only the colors in the lists. The sum choice number sc(G) is the minimum of ∑ f(v) taken over all choice functions. The investigation of sum choice number for complete bipartite graphs is particularly appealing because it leads to interesting problems about hypergraph covering. Berliner, Bostelmann, Brualdi and Deaett determined sc(K_2,q) for all q, and Isaak and Heinold settled sc(K_3,q). We prove that, for all a≥ 4 and for q large compared to a, sc(K_a,q)-2q is within a multiplicative constant of a√(q log a). This is joint work with Z. Furedi.

Tuesday, March 3, 2009

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

Del

Edit

Copy

Submitted by west.

Mohit Kumbhat (UIUC Math)
Choosability with separation of complete graphs
Abstract: Given a graph G, a k-uniform list assignment assigns a list of k available colors to each vertex. Let χ_l(G,c) be the minimum k such that one can choose a proper coloring of G from any k-uniform list assignment such that |L(u)∩ L(v)|≤ c for all uv∈ E(G). Kratochvíl et al. asked for the limit as n -> ∞ of χ_l(K_n,c)/√(cn), if it exists. We prove that the limit exists and equals 1. We also find the exact value of χ_l(K_n,c) for infinitely many values of n. This is joint work with Prof Füredi and Prof Kostochka.

Tuesday, March 10, 2009

Tuesday, March 17, 2009

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

Del

Edit

Copy

Submitted by west.

Hal Schenck (UIUC Math)
Graphs, hyperplane arrangements, and algebra
Abstract: Associated to a simple graph G with vertex set V is a hyperplane arrangement A, which is a finite set of hyperplanes in the vector space K^|V| (typically K is the complex or real numbers). Each edge (i,j) of G gives rise to a hyperplane, defined by the vanishing of the linear form x_i-x_j. I'll spend the first half of the talk describing examples and the basic translation between graph-theoretic concepts and the analogous concepts in algebraic geometry. In the second part I'll describe two basic algebraic objects associated to arrangements, as well as several open conjectures about these objects.

Tuesday, March 31, 2009

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

Del

Edit

Copy

Submitted by west.

Tao Jiang (Miami University (Ohio))
Compact topological cliques in sparse graphs
Abstract: We give the details of a result presented at the Urbana AMS meeting. Let ε be a positive number with ε≤.5. Kostochka and Pyber (1988) answered a question of Erdős by showing that for large n, every n-vertex graph with at least 4^t²n^1+ε edges contains a subdivision of K_t in which each edge of K_t is subdivided at most clog(t/ε) times, where c is an absolute constant. We prove a complementary (and in some sense stronger) result by simplifying the dependence on t. For each t and sufficiently large n, we show that every n-vertex graph with at least a(t) n^1+ε edges contains a subdivision of K_t in which each edge of K_t is subdivided at most clog (1/ε)/ε times, where c is an absolute constant and a(t) depends only on t. The constraint on the number of times each edge is subdivided depends only on ε and not on t.

Tuesday, April 14, 2009

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

Del

Edit

Copy

Submitted by west.

Bela Csaba (Western Kentucky University)
Tight bounds on embedding bounded-degree trees in dense graphs
Abstract: In 1978 the following conjecture was raised by Bollobás: Given c>0, if T is an n-vertex tree of bounded degree and G is an n-vertex graph such that the minimum degree of G is at least (1/2+c)n and n is sufficiently large, then T is a spanning tree of G. The conjecture was proved by Komlós, Sárkőzy and Szemerédi in 1995. Later they also showed a stronger result, in which the maximum degree in T may be as large as c'n/log n for some positive constant c'. Both proofs used the Regularity Lemma - Blow-up Lemma method.

Recently, in joint work with Endre Szemerédi, Ian Levitt, and Judit Nagy-György, we managed to eliminate the use of the Regularity Lemma and proved the following stronger form of the Bollobás conjecture. If T is an n-vertex tree with constant maximum degree K, and G is an n-vertex graph having minimum degree n/2+4K⁴log n, then T is a spanning tree of G when n is sufficiently large. We also showed that the Clog n additive term is inevitable when T is a complete ternary tree and G has a special structure. In the talk we will survey tree embedding results and conjectures, and we will discuss some features of the proof.

Tuesday, April 21, 2009

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

Del

Edit

Copy

Submitted by west.

Paul Wenger (UIUC Math)
Acquisition Parameters in Graphs
Abstract: Let G be a graph with weight 1 on each vertex. When a vertex u has a neighbor v whose weight is at least that on u, an acquisition move transfers all weight from u to v. The acquisition number of G, written a(G) and introduced by Lampert and Slater in 1995, is the minimum number of vertices with positive weight after a sequence of acquisition moves. We introduce two variations. Partial acquisition moves transfer unit amounts of weight, and continuous acquisition moves transfer arbitrary positive amounts. The partial and continuous acquisition numbers a_p(G) and a_c(G), respectively, are the minimum number of vertices with positive weight after a sequence of moves in these models. We explore these three parameters, proving that they are equal on paths and cycles while differing greatly on other families of graphs.

Tuesday, April 28, 2009

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

Del

Edit

Copy

Submitted by west.

Wojciech Samotij (UIUC Math)
Bounded degree trees in sparse random graphs
Abstract: A remarkable result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to guarantee containing all small trees with bounded maximum degree. We show that under slightly stronger assumptions on the expansion rate, their technique allows one to find arbitrarily large trees with bounded maximum degree. As a corollary, we prove that graph in a certain family of expanding graphs, which includes very sparse random graphs, contains all almost spanning bounded degree trees. This improves a recent tree embedding result of Alon, Krivelevich and Sudakov. This work is joint with Jozsef Balogh (UIUC) and Bela Csaba (Western Kentucky University).

Tuesday, May 5, 2009

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

Del

Edit

Copy

Submitted by west.

Jozsef Balogh (UIUC Math)
Counting graphs without a fixed subgraph
Abstract: A graph is H-free if it has no subgraph isomorphic to H. Denote by f_n(H) the number of (labeled) H-free graphs on a fixed set of n vertices. Since every subgraph of an H-free graph is also H-free, immediately f_n(H)≥ 2^ex(n,H), where ex(n,H) is the maximum number of edges in an H-free graph with n vertices. Erdős conjectured that when H contains a cycle, this trivial lower bound is in a sense tight; that is, f_n(H) = 2^{(1+o(1))ex(n,H)}.

Tuesday, May 19, 2009

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

Del

Edit

Copy

Submitted by west.

Ryan R. Martin (Iowa State University)
Expected value of the minimum rank of a random graph
Abstract: We associate a symmetric real matrix, M, with a graph, G, if mij is nonzero whenever distinct vertices vi and vj are adjacent and is zero whenever distinct vertices vi and vj are nonadjacent. The diagonal is unrestricted. The minimum rank of G, denoted mr(G), is the minimum of the ranks of all matrices associated with G. We obtain bounds for mr(G(n, p)) for fixed p and n sufficiently large. We use concentration results for graph parameters, bounds on the number of zero patterns of polynomials with bounded degree, and faithful orthogonal representations of graphs by vectors. This work is joint with Tracy Hall, Leslie Hogben, and Bryan Shader.

Tuesday, September 1, 2009

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