UIUC Dept. of Mathematics Seminar Calendar

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

Tuesday, August 28, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, August 28, 2012

Del

Edit

Copy

Submitted by lidicky.

Zoltán Füredi [email] (UIUC and Renyi Institute, Budapest, Hungary)
Optimal Multivalued Shattering
Abstract: We have found an extension of the celebrated Sauer, Perles and Shelah, Vapnik and Chervonenkis result concerning Vapnik-Chervonenkis dimension of 0-1 sequences to $k$-ary codes. This is a joint work with A. Sali.

Tuesday, September 4, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 4, 2012

Del

Edit

Copy

Submitted by lidicky.

Derrick Stolee [email] (UIUC)
Uniquely $K_r$-Saturated Cayley Graphs
Abstract: A graph is uniquely $H$-saturated if it contains no copy of $H$ but adding any missing edge creates exactly one copy of $H$. In the case of $H$ being a complete graph, very little is known about which graphs are uniquely $K_r$-saturated. The only two infinite families previously known are books and the complements of odd cycles. In this talk, we will discuss two new infinite families of uniquely $K_r$-saturated graphs which are complements of Cayley graphs with small generator sets. One of these proofs is the first example of using discharging to bound the clique number of a graph. This is joint work with Stephen G. Hartke.

Tuesday, September 11, 2012

Tuesday, September 18, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 18, 2012

Del

Edit

Copy

Submitted by lidicky.

Matthew Yancey [email] (UIUC Math)
Color-Critical Graphs With Few Edges
Abstract: A graph $G$ is $k$-critical if it has chromatic number $k$, but every proper subgraph of $G$ is $(k-1)$-colorable. Let $f_k(n)$ denote the minimum number of edges in an $n$-vertex $k$-critical graph. We give a bound on $f_k(n)$ that is exact for every $n=1\,({\rm mod }\, k-1)$. It is also exact for $k=4$ and every $n\geq 6$. The result improves the classical bounds by Gallai and Dirac and subsequent bounds by Krivelevich and Kostochka and Stiebitz. It establishes the asymptotics of $f_k(n)$ for every fixed $k$. We also present some applications of the result, in particular, a simple proof of the Grotzsch Theorem that every triangle-free planar graph is $3$-colorable. This is joint work with Alexandr Kostochka.

Tuesday, September 25, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, September 25, 2012

Del

Edit

Copy

Submitted by lidicky.

Cory Palmer [email] (UIUC Math)
On the tree-packing conjecture
Abstract: The tree packing conjecture of Gyárfás states that any set of $n-1$ trees on $n,n-1,\dots, 2$ vertices pack into $K_n$. For large $n$ we prove that $t=\frac{1}{4}n^{1/3}$ trees on $n,n-1,\dots, n-t+1$ vertices pack into $K_n$ as long as each tree has maximum degree at least $n^{2/3}$. This complements a corollary of a Theorem of Komlós, Sárközy and Szemerédi that for large $n$ we can pack $t=\omega(\log n)$ trees of maximum degree at most $\frac{n}{3t}$ into $K_n$. Furthermore, we show that $t=\frac{1}{10}n^{1/4}$ trees on $n,n-1,\dots, n-t+1$ vertices pack into $K_{n+1}$ (for $n$ large enough). This is joint work with Jószef Balogh.

Tuesday, October 2, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 2, 2012

Del

Edit

Copy

Submitted by lidicky.

Elyse Yeager [email] (UIUC Math)
A Refinement of the Corrádi-Hajnal Theorem
Abstract: In 1963, Corrádi and Hajnal proved the following result: If a graph $G$ has $|V(G)| \geq 3k$ and $\delta(G) \geq 2k$ for some $k$, then $G$ has $k$ vertex-disjoint cycles. Clearly, the bound $n \geq 3k$ is sharp. The minimum degree is also sharp, as evidenced by the join of $K_{2k-1}$ and an independent set. Enomoto and Wang independently proved that the theorem still holds if the weaker requirement $\sigma_2(G) \geq 4k-1$ replaces $\delta(G) \geq 2k$. Using the method from Enomoto's paper, we prove the following: If a graph $G$ has $|V(G)| \geq 3k+1$ and $\sigma_2(G) \geq 4k-2$ and $G$ does not have $k$ disjoint cycles, then $\alpha(G) \geq |V(G)|-2k+1$. This is joint work with Hal Kierstead and Alexandr Kostochka.

Tuesday, October 9, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 9, 2012

Del

Edit

Copy

Submitted by lidicky.

Hal Kierstead [email] (Arizona State University)
On directed versions of the Corrádi-Hajnal Corollary
Abstract: For $k\in \mathbb N$, the Corrádi-Hajnal Corollary states that every graph $G$ on $3k$ vertices with minimum degree $\delta(G)\ge2k$ has a $C_3$-factor, i.e., a partitioning of the vertex set so that each part induces the $3$-cycle $C_3$. I will discuss directed versions of the Corr\'adi-Hajnal Corollary in terms of both minimum total degree $\delta_t(\overrightarrow G):=\min_{v\in V}(deg^-(v)+deg^+(v))$ and minimum semidegree $\delta_0(\overrightarrow G):=\min_{v\in V}\{deg^-(v),deg^+(v)\}$.

Tuesday, October 16, 2012

Tuesday, October 23, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 23, 2012

Del

Edit

Copy

Submitted by lidicky.

John Lenz [email] (University of Illinois at Chicago)
Quasirandom Hypergraphs
Abstract: Quasirandom or pseudorandom graphs, first studied by Thomason and shortly thereafter by Chung-Graham-Wilson, are graphs which behave like the random graph. Quasirandom graphs have many diverse applications throughout combinatorics and computer science and have emerged as an interesting object of study in their own right. In this talk, I will give an overview of our recent work on hypergraph quasirandomness and discuss as an application a polynomial-time strong refutation algorithm for random k-SAT. Joint work with Dhruv Mubayi.

Tuesday, October 30, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, October 30, 2012

Del

Edit

Copy

Submitted by lidicky.

József Balogh [email] (UIUC Math)
Phase transitions in Ramsey-Turán theory
Abstract: Let $f(n)$ be a function and $L$ a graph. Denote by $RT(L, f(n))$ the infimum of $c$ such that an $L$-free graph on $n$ vertices with independence number at most $f(n)$ could have at most $(c+o(1))n^2$ edges. Erdős and Sós asked for the largest function $f(n)$ such that $RT(K_5,f(n))=0$. Using the Dependent Random Choice Lemma, we answer this question by proving that $RT(K_5,o\left(\sqrt{n\log n}\right))=0$. It was known that $RT(K_5, c\sqrt{n\log n})=1/4$ for $c>1$, hence our result is best possible up to a constant factor. Using the Hypergraph Dependent Random Choice Lemma, we extend our result to other cliques. Additionally, we propose many questions: if variants of the Bollobás-Erdős graph exist to give lower bound on $RT(K_t, f(n))$ for various pairs of $t$ and $f(n)$. Partially joint work with Ping Hu and Miklos Simonovits.

Tuesday, November 6, 2012

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

Del

Edit

Copy

Submitted by lidicky.

Theodore Molla [email] (Arizona State University)
Extending the Hajnal-Szemerédi Theorem to directed graphs
Abstract: In 1963 Corrádi and Hajnal proved that if $G$ is a graph on $3k$ vertices with $\delta(G) \ge 2k$ then $G$ has a $K_3$ factor, that is, $k$ vertex disjoint copies of the $3$ vertex clique. An equivalent form of the Hajnal-Szemerédi Theorem states that if $G$ is a graph on $sk$ vertices and $\delta(G) \ge (s-1)k$ then $G$ has a $K_s$ factor. We will explore extensions of these results to directed graphs. For a directed graph $D$, let $\delta_{t}(D):= \min_{v \in V(D)}\{ d^+(v) + d^-(v) \}$ where $d^+(v)$ and $d^-(v)$ are the out-degree and in-degree of the vertex $v$ respectively and call an oriented $K_s$ without directed cycles a transitive $s$-tournament. Analogous to Corrádi and Hajnal's result, we will show that if $D$ is a directed graph on $3k$ vertices and $\delta_{t}(D) \ge 4k - 1$ then $D$ contains a transitive $3$-tournament factor. It is then natural to ask if this can be generalized to transitive $s$-tournament factors. We conjecture that if $|D| = sk$ and $\delta_{t}(D) \ge 2(s-1)k - 1$ then $D$ has a transitive $s$-tournament factor. We will discuss a proof of this conjecture for graphs of large order. The proof uses the probabilistic absorbing technique in a manner similar to Levitt, Sárközy and Szemerédi. This is joint work with Andrzej Czygrinow and H.A. Kierstead.

Tuesday, November 13, 2012

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

Del

Edit

Copy

Submitted by lidicky.

Paul Horn [email] (Harvard University)
Isomorphic subgraphs in graphs and hypergraphs
Abstract: We show that any $k$-uniform hypergraph with $n$ edges contains two isomorphic edge disjoint subgraphs of size $\tilde{\Omega}(n^{2/(k+1)})$ for $k=4,5$ and $6$. This is best possible up to a logarithmic factor due to a upper bound construction of Erdős, Pach, and Pyber who show there exist $k$-uniform hypergraphs with $n$ edges and with no two edge disjoint isomorphic subgraphs with size larger than $\tilde{O}(n^{2/(k+1)})$. Furthermore, our result extends results Erdős, Pach and Pyber who also established the lower bound for $k=2$ (ie. for graphs), and of Gould and Rödl who established the result for $k=3$. In this talk, we'll discuss some of the main ideas of the proof, which is probabilistic, and the obstructions which prevent us from establishing the result for higher values of $k$. We'll also briefly talk about the a connected version of this problem on both graphs and uniform hypergraphs.

Tuesday, November 27, 2012

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

Del

Edit

Copy

Submitted by lidicky.

Alexandr Kostochka [email] (UIUC Math)
Hypergraph Ramsey Numbers: Triangles versus Cliques
Abstract: It is known that the order of magnitude of the graph Ramsey numbers $R(3,t)$ is $t^2/\log t$. We consider an analogue of this problem for uniform hypergraphs. A triangle is a hypergraph consisting of edges $e,f,g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$. For all $r \ge 2$, let $R(3,K_t^r)$ be the smallest positive integer $n$ such that in every red-blue coloring of the edges of the complete $r$-uniform hypergraph $K_n^r$, there exists a red triangle or a blue $K_t^r$. We determine up to a logarithmic factor the order of magnitude of $R(3,K_t^r)$ for all $r\ge 3$: $ c_1 (t/\log t)^{3/2} \leq R(3,K_t^r) \leq c_2 t^{3/2}$. When $r=3$, we improve the lower bound to $c_1 t^{3/2}(\log t)^{-3/4}$. This is joint work with D. Mubayi and J. Verstraete.

Tuesday, December 4, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, December 4, 2012

Del

Edit

Copy

Submitted by lidicky.

Ágnes Tóth [email] (Budapest University of Technology and Economics)
The asymptotic value of the independence ratio for categorical graph power
Abstract: The independence ratio $i(G)$ of a graph $G$ is the ratio of the independence number and the number of vertices. The $k$th categorical power of $G$, the graph $G^{\times k}$, is defined on the $k$-length sequences over the vertices of $G$, and two such sequences are connected iff their elements form an edge in $G$ at every coordinate. The ultimate categorical independence ratio of a graph $G$ is defined by Brown, Nowakowski and Rall as the limit of $i(G^{\times k})$ as $k$ approaches infinity. Let $a(G)=\max\{\frac{|U|}{|U|+|N_G(U)|}\}$, where the maximum is taken on every independent set $U$ of $G$, and $N_G(U)$ denotes the neighborhood of $U$ in $G$. Alon and Lubetzy proposed the question whether $A(G)=a(G)$ if $a(G)\le \frac{1}{2}$, and $A(G)=1$ otherwise. In the talk, we will answer this question affirmatively. During the proof we exploit an idea of Zhu that he used on the way when proving the fractional version of Hedetniemi's conjecture. We will also talk about some other open problems related to $A(G)$ which are immediately settled by this result.

Thursday, December 6, 2012

Tuesday, December 11, 2012

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, December 11, 2012

Del

Edit

Copy

Submitted by lidicky.

Jiří Fiala [email] (Charles University)
The k-in-a-path problem for claw-free graphs
Abstract: The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. When k is part of the input, then this problems is NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs. Joint work with Marcin Kaminski, Bernard Lidicky and Daniel Paulusma.

Tuesday, January 15, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, January 15, 2013

Del

Edit

Copy

Submitted by lidicky.

Michael Ferrara [email] (University of Colorado Denver)
Some Extremal Results on Potentially H-Graphic Sequences
Abstract: A nonnegative integer sequence $\pi$ is graphic if there is some (simple) graph $G$ such that $\pi$ is the degree sequence of $G$. In this case we say that $G$ realizes or is a realization of $\pi$. Given a graph $H$, a graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains $H$ as a subgraph. In 1991, Erdős, Jacobson and Lehel posed the following question: Determine the minimum integer $\sigma(H, n)$ such that every $n$-term graphic sequence with sum at least $\sigma(H, n)$ is potentially $H$-graphic. As the sum of the terms of $\pi$ is twice the number of edges in any realization of $\pi$, the Erdős-Jacobson-Lehel problem can be viewed as a potential degree sequence relaxation of the Turán problem. While the exact value of $\sigma(H,n)$ has been determined for a number of specific classes of graphs, very little is known about the parameter for arbitrary $H$. We determine $\sigma(H,n)$ asymptotically for all $H$, thereby providing an Erdős-Stone-Simonovits-type theorem for the Erdős-Jacobson-Lehel problem. We will also discuss some results, based on the above, that describe the structure (or perhaps more appropriately, "shape") of degree sequences that are not potentially $H$-graphic.

Tuesday, January 22, 2013

Tuesday, February 5, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, February 5, 2013

Del

Edit

Copy

Submitted by lidicky.

Derrick Stolee [email] (UIUC Math)
A Branch-And-Cut Strategy for the Manickam-Miklós-Singhi Conjecture
Abstract: The Manickam-Miklós-Singhi Conjecture states that when $n \geq 4k$, every multiset of $n$ real numbers with nonnegative total sum has at least $\binom{n-1}{k-1}$ $k$-subsets with nonnegative sum. We develop a branch-and-cut strategy using a linear programming formulation to show that verifying the conjecture for fixed values of $k$ is a finite problem. To improve our search, we develop a zero-error randomized propagation algorithm. Using implementations of these algorithms, we verify a stronger form of the conjecture for all $k$ at most 7. (joint with Stephen G. Hartke)

Tuesday, February 12, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, February 12, 2013

Del

Edit

Copy

Submitted by lidicky.

Gregory Puleo [email] (UIUC Math)
Tuza's Conjecture and Discharging
Abstract: Suppose I wish to make a graph $G$ triangle-free by removing a small number of edges. An obvious obstruction is the presence of a large set of edge-disjoint triangles, since I must remove one edge from each triangle. On the other hand, removing all the edges in a maximal set of edge-disjoint triangles clearly makes $G$ triangle-free. Tuza's conjecture states that the true number of edges that must be removed is somewhere between these extremes: if $\tau(G)$ is the number of edges that must be removed to make $G$ triangle-free and $\nu(G)$ is the maximum number of edge-disjoint triangles in $G$, then Tuza's conjecture states that $\tau(G) \leq 2\nu(G)$. Using the method of discharging, we show that Tuza's conjecture holds whenever $\text{Mad}(G) < 6 + \epsilon$, where $\epsilon > 0$. This subsumes several earlier results and represents the first application of discharging to this problem.

Tuesday, February 19, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, February 19, 2013

Del

Edit

Copy

Submitted by lidicky.

Sogol Jahanbekam [email] (UIUC Math)
Rainbow Spanning Subgraphs in Edge-Colored Complete Graphs
Abstract: For integers $n$ and $t$, let $r(n,t)$ be the maximum number of colors in an edge-coloring of the complete graph $K_n$ that does not contain $t$ edge-disjoint rainbow spanning trees. Let $s(n,t)$ be the maximum number of colors in an edge-coloring of $K_n$ containing no rainbow spanning subgraph with diameter at most $t$. We determine $r(n,t)$ whenever $n>2t+\sqrt{6t-\frac{23}{4}}+\frac52$ and when $n=2t$. We also determine $s(n,t)$ for all pair $n$ and $t$. This is joint work with D. B. West.

Tuesday, February 26, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, February 26, 2013

Del

Edit

Copy

Submitted by lidicky.

Bernard Lidicky [email] (UIUC Math)
Short proofs of coloring theorems on planar graphs
Abstract: A recent lower bound on the number of edges in a $k$-critical $n$-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar triangle-free graph is 3-colorable. In this talk we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grünbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. It turns out that the family ${\cal P}_4$ of $4$-critical plane graphs with exactly four triangles is infinite. Moreover, Thomas and Walls showed that even the family ${\cal P}'_4$ of graphs in ${\cal P}_4$ with no 4-faces is infinite by constructing an infinite series of graphs in ${\cal P}'_4$. We describe graphs in ${\cal P}'_4$. This is joint work with O. V. Borodin, A. Kostochka and M. Yancey.

Tuesday, March 5, 2013

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

Del

Edit

Copy

Submitted by lidicky.

Ilkyoo Choi [email] (UIUC Math)
The list version of Borodin-Kostochka Conjecture for graphs with large maximum degree
Abstract: : Brooks' Theorem states that for a graph $G$ with maximum degree $\Delta(G)$ at least $3$, the chromatic number is at most $\Delta(G)$ when the clique number is at most $\Delta(G)$. Vizing proved that the list chromatic number is also at most $\Delta(G)$ under the same conditions. Borodin and Kostochka conjectured that a graph $G$ with maximum degree at least $9$ must be $(\Delta(G)-1)$-colorable when the clique number is at most $\Delta(G)-1$; this was proven for graphs with maximum degree at least $10^{14}$ by Reed. In this paper, we prove an analogous result for the list chromatic number; namely, we prove that a graph $G$ with $\Delta(G)\geq 10^{20}$ is $(\Delta(G)-1)$-choosable when the clique number is at most $\Delta(G)-1$. This is joint work with H. A. Kierstead, L. Rabern, and B. Reed.

Tuesday, March 12, 2013

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

Del

Edit

Copy

Submitted by lidicky.

Jonathan Cutler [email] (Montclair State University)
Extremal problems for homomorphisms
Abstract: Fix a (small) graph $H$ with, perhaps, loops. A natural extremal question arises when one asks which graphs $G$ with $n$ vertices and $m$ edges maximize the number of homomorphisms from $G$ to $H$. Linial and Wilf asked the question when $H=K_q$, where homomorphisms from $G$ to $K_q$ correspond to proper $q$-colorings of $G$. We focus on the question for various other image graphs $H$. It is a corollary of the Kruskal-Katona theorem that the number of independent sets in a graph with $n$ vertices and $m$ edges is maximized by the lex graph, where the edges form an initial segment in the lexicographic ordering. This corresponds to the homomorphism problem when the image graph consists of two adjacent vertices, one of which is looped. In this talk, we will present some results for other image graphs and give the basic ideas of the proofs, which involve a compression that yields, in some cases, an extremal graph that is a threshold graph. This is joint work with Jamie Radcliffe from the University of Nebraska-Lincoln.

Tuesday, March 26, 2013

Graph Theory and Combinatorics
1:00 pm in 241 Altgeld Hall, Tuesday, March 26, 2013

Del

Edit

Copy

Submitted by lidicky.

Jaehoon Kim [email] (UIUC Math)
Saturation Number of Ramsey-Minimal Graphs for Matchings
Abstract: For a family $\mathcal{F}$ of graphs, $G$ is $\mathcal{F}$-saturated if $G$ contains no member of $\mathcal{F}$ and $G+e$ contains a member of $\mathcal{F}$ for any non-edge $e$ of $G$. $sat(n,\mathcal{F})$ is the minimum number of edges in an $\mathcal{F}$-saturated graph. A graph $G$ is $(H_1.H_2,\cdots,H_k)$-Ramsey minimal if there exists an edge-coloring of $G$ with $k$ colors such that $G$ does not contain monochromatic $H_i$ with $i$th color, but there is no such edge-coloring of $G+e$ with $k$ colors for any non-edge $e$ of $G$. $R_{min}(H_1,H_2,\cdots,H_k)$ denote the family of $(H_1,H_2,\cdots,H_k)$-Ramsey-minimal graphs. We prove that $sat(n,R_{min}(m_1K_2, m_2K_2,\cdots,m_kK_2))=3(m_1+m_2+\cdots m_k-k)$ holds for $n\geq 3(m_1+m_2+\cdots m_k-k)$. Also we found unique extremal graph for the case when $m_i\geq 3$ for at least one $i$, and we characterize extremal graphs for the case when all $m_i\leq 2$. This is joint work with Mike Ferrara and Elyse Yeager.

Tuesday, April 2, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, April 2, 2013

Del

Edit

Copy

Submitted by lidicky.

Bernard Lidicky [email] (UIUC Math)
3-coloring planar graphs with 4 triangles
Abstract: A celebrated theorem by Grötzsch states that every triangle-free planar graph is 3-colorable. The theorem can be strengthened in several ways. One of them is theorem of Grünbaum-Axenov stating that every planar graph with at most three triangles is 3-colorable. It is best possible since not all planar graphs with four triangles are 3-colorable. For example $K_4$. In this talk, we discuss 3-colorability of planar graphs with four triangles. In particular, we describe 4-critical planar graphs with four triangles. This is joint work with O. V. Borodin, A. Dvořák, A. Kostochka, and M. Yancey

Tuesday, April 9, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, April 9, 2013

Del

Edit

Copy

Submitted by lidicky.

Anastasios Sidiropoulos [email] (UIUC CS)
Approximation algorithms for Euler genus and related problems
Abstract: The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard [Thomassen 1989, 1993], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(sqrt(n))-approximation is known [Chen, Kanchi, and Kanevsky, 1997] even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g^O(1) * log^O(1) n. Combined with the upper bound from [Chen, Kanchi, and Kanevsky, 1997], our result also implies a O(n^(1/2 - alpha)-approximation, for some constant alpha>0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT^O(1) * log^O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is shorter and simpler compared to the long and difficult proof in the recent (80 pages long) breakthrough by [Chuzhoy 2011], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown. Joint work with Chandra Chekuri.

Tuesday, April 16, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, April 16, 2013

Del

Edit

Copy

Submitted by lidicky.

Derrick Stolee [email] (UIUC Math)
Ordered Ramsey Theory and Track Representations of Graphs
Abstract: We introduce an ordered version of Ramsey numbers for hypergraphs using linearly ordered vertex sets. In this model, we obtain bounds on the ordered Ramsey numbers of the k-uniform hypergraph whose edge set consists of the sets of k consecutive vertices in the linear order on the vertex set. The upper and lower bounds are towers of the same height. We apply these bounds to study the minimum number of interval graphs whose union is the line graph of the n-vertex complete graph, proving the conjecture of Heldt, Knauer, and Ueckerdt that this number grows with n. In fact, the growth rate is between O( log log n / log log log n) and O(log log n). (Joint work with Kevin Milans and Doug West.)

Tuesday, April 23, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, April 23, 2013

Del

Edit

Copy

Submitted by lidicky.

André Raspaud [email] (Bordeaux University, France)
Improper coloring, a relaxation of Steinberg conjecture and (i,j,k)-coloring
Abstract: A graph $G$ is $(d_1,\ldots,d_k)$-colorable if the vertex set of $G$ can be partitioned into subsets $V_1,\ldots,V_k$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i\leq k$. This notion generalizes those of proper $k$-coloring (when $d_1=\ldots=d_k=0)$ and $d$-improper $k$-coloring (when $d_1=\ldots=d_k=d\ge1)$. In this talk we will give a quick survey of the $(i,j)$-coloring. We will also present a relaxation of the Steinberg Conjecture and results concerning the $(i,j,k)$-coloring with $i+j+k=3$.

Tuesday, April 30, 2013

Graph Theory and Combinatorics
3:00 pm in 241 Altgeld Hall, Tuesday, April 30, 2013

Del

Edit

Copy

Submitted by lidicky.

Cory Palmer [email] (UIUC Math)
Edge-weightings and the chromatic number
Abstract: Let $G$ be a graph with edge set $E(G)$. A $k$-edge-weighting of $G$ is a mapping $\phi : E(G) \rightarrow \{1,2,\dots, k\}$. If we introduce additional conditions to a $k$-edge-weighting we discover many interesting graph parameters. For example, if we require that any two incident edges receive different weights we have a proper edge-coloring. Another well-known example is to require that for any pair of adjacent vertices the sum of weights on their incident edges must be different. We say that a $k$-edge-weighting $\phi$ is neighbor-distinguishing if every pair of adjacent vertices have distinct sets of weights on their incident edges. For a given graph $G$ we want to determine the minimum $k$ such that a vertex-distinguishing $k$-edge-weighting exists. In this talk we will find bounds on this parameter in terms of the chromatic number of $G$. We will also survey a number of interesting related (and often very open) graph parameters.

Friday, May 24, 2013

Graph Theory and Combinatorics seminar
1:00 pm in Altgeld Hall 241, Friday, May 24, 2013

Del

Edit

Copy

Submitted by lidicky.

Jan Volec [email] (University of Warwick)
Applications of Entropy Compression Method to graph colorings
Abstract: In 2009, Moser found a simple but ingenious so called ``Entropy compression'' argument that he used to design a polynomial-time algorithm for a special case of the Lovász Local Lemma (LLL). Although this technique differs from the one later used in the Moser-Tardos algorithm for the general version of LLL, it turned out to be useful for a various of different applications in combinatorics. I will give a brief introduction to the method itself and then I will talk about some applications for graph coloring problems.