Seminar Calendar
for Graph Theory and Combinatorics events the year of Monday, July 16, 2012.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
      June 2012              July 2012             August 2012
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2    1  2  3  4  5  6  7             1  2  3  4
3  4  5  6  7  8  9    8  9 10 11 12 13 14    5  6  7  8  9 10 11
10 11 12 13 14 15 16   15 16 17 18 19 20 21   12 13 14 15 16 17 18
17 18 19 20 21 22 23   22 23 24 25 26 27 28   19 20 21 22 23 24 25
24 25 26 27 28 29 30   29 30 31               26 27 28 29 30 31



Tuesday, January 24, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 24, 2012
 Del Edit Copy
Submitted by west.
 Ping Hu (UIUC Math)Upper bounds on the size of $4$- and $6$-cycle-free subgraphs of the hypercubeAbstract: Erdős proposed the problem of determining ex$_Q(n;C_{2t})$, i.e. determining the maximum number of edges that a subgraph of the $n$-dimensional hypercube containing no $2t$-cycle can have. We modify slightly Razborov's flag algebra machinery to be suitable for the hypercube. We use this modified method to show that the maximum number of edges in a subgraph of the $n$-dimensional hypercube containing no $4$-cycle is at most $0.6068$ times the number of edges in the hypercube. For subgraphs containing no $6$-cycle, we improve the upper bound on the proportion of edges from $\sqrt{2}-1$ to $0.3755$. (Joint work with Jozsef Balogh, Bernard Lidicky, and Hong Liu.)

Tuesday, January 31, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 31, 2012
 Del Edit Copy
Submitted by west.
 Jozsef Balogh (UIUC Math)The biggest loserAbstract: An important trend in Combinatorics in recent years has been the formulation and proof of various `sparse analogues' of classical extremal results in Graph Theory and Additive Combinatorics. Due to the recent breakthroughs of Conlon and Gowers, and Schacht, many such theorems, e.g., the theorems of Turán and Erdős and Stone in extremal graph theory, and the theorem of Szemerédi on arithmetic progressions, are now known to extend to sparse random sets. I give a survey on the recent developments. (Joint work with Robert Morris and Wojtek Samotij.)

Tuesday, February 7, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 7, 2012
 Del Edit Copy
Submitted by west.
 Robert Jamison (UIUC Math and Clemson University)Sum-Tolerance Graphs with Eutactic RankAbstract: This talk will focus on certain classes of rank-tolerance graphs that generalize the co-threshold-tolerance (co-TT) graphs introduced by Monma, Reed, and Trotter. In a rank-tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance, which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance. This study is motivated by the class SP of sum-product graphs, introduced by Golumbic and RJ, where the tolerance coupling function is the sum of the two tolerances and and the rank coupling function is the product of the two ranks. Many properties of sum-product graphs remain valid when product is replaced by a general eutactic function --- one that satisfies a certain convexity condition. The class of eutactic functions is quite broad. For example, it includes all symmetric polynomials (in two variables) with positive coefficients. We show that SP strictly contains co-TT as well as all complete bipartite graphs $K_{2,n}$, and we survey a number of other results. My advisor Victor Klee vowed as graduate student that he would avoid formulae involving binomial coefficients. I vowed that I would never get involved with multidimensional calculus. In the talk I will explain (briefly) why we were both wrong.

Tuesday, February 14, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 14, 2012
 Del Edit Copy
Submitted by west.
 Gexin Yu (College of William and Mary)Degree bounds on coloring graphs equitably and defectivelyAbstract: A graph has an equitable, defective $k$-coloring (an ED-$k$-coloring) if there is a $k$-coloring of $V(G)$ that is 1-defective (every vertex shares its color with at most one neighbor) and equitable (the sizes of color classes differ by at most one). We prove an analogue of the Hajnal-Szemerédi Theorem: Every graph with maximum degree $D$ can be ED-$k$-colored for $k\ge D$. When the maximum degree is large, we prove that far fewer colors suffice.

Tuesday, February 21, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 21, 2012
 Del Edit Copy
Submitted by west.
 Jozef Skokan (London School of Economics)Monochromatic cycles in 2-edge-colored graphsAbstract: The Ramsey number $r(H)$ of a graph $H$ is the smallest integer $n$ such that every 2-coloring of the edges of the complete graph on $n$ vertices contains a monochromatic copy of $H$. Schelp conjectured that if $H$ is a path or a cycle and $G$ is any graph on $r(H)$ vertices with minimum degree larger than $3r(H)/4$, then every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. In this talk, we shall discuss the ideas in our proof of the conjecture for long paths and cycles. (Joint work with B. Bollobas, F. Benevides, T. Luczak, A. Scott, and M. White.)

Tuesday, February 28, 2012

Graph Theory and Combinatorics
3:00 pm   in Altgeld Hall,  Tuesday, February 28, 2012
 Del Edit Copy
Submitted by west.
 Alexandr Kostochka (Department of Mathematics, University of Illinois at Urbana-Champaign)Ks,t-minors in dense graphs and in (s+t)-chromatic graphsAbstract: We refine two known results on the existence of $K_{s,t}$-minors in graphs. First we prove that if $(t/\log_2 t)\ge 1000s$, then every graph $G$ with average degree at least $t+8s\log_2 s$ has a $K^*_{s,t}$-minor, where $K^*_{s,t}$ is the graph obtained from $K_{s,t}$ by adding the edges of a complete graph on the first partite set. This result refines a result by Kühn and Osthus and is joint work with N. Prince. It was proved earlier that for sufficiently large $t$ in terms of $s$, every graph with chromatic number $s+t$ has a $K^*_{s,t}$-minor. In particular, with $t_0(s) = \max\{4^{15s^2+s},(240s\log_2{s})^{8s\log_2{s}+1}\}$, the conclusion holds when $t>t_0(s)$. This result confirmed a special case of a conjecture by Woodall and Seymour. We show that the conclusion holds already for much smaller $t$, namely, for $t>C(s\log s)^3$.

Tuesday, March 6, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 6, 2012
 Del Edit Copy
Submitted by west.
 Andrew Treglown (Charles University, Prague)Embedding spanning bipartite graphs of small bandwidthAbstract: A graph $H$ on $n$ vertices has bandwidth at most $b$ if there exists a labelling of the vertices of $H$ by the numbers $1,\ldots,n$ such that $|i-j|\le b$ for every edge $ij$ of $H$. Boettcher, Schacht, and Taraz gave a condition on the minimum degree of a graph $G$ on $n$ vertices to ensure that $G$ contains every $r$-chromatic graph $H$ on $n$ vertices having bounded degree and bandwidth $o(n)$, thereby proving a conjecture of Bollobás and Komlós. We strengthen this result in the case where $H$ is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph $G$ on $n$ vertices that forces $G$ to contain every bipartite graph $H$ on $n$ vertices having bounded degree and bandwidth $o(n)$. This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on $G$ is relaxed to a certain robust expansion property. (Joint work with Fiachra Knox.)

Tuesday, March 13, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 13, 2012
 Del Edit Copy
Submitted by west.
 Jeffrey Paul Wheeler (University of Pittsburgh)The Polynomial Method of Alon, Ruzsa, and NathansonAbstract: We will explore a particular method of tackling problems in Additive Combinatorics, namely the Polynomial Method of Noga Alon, Imre Ruzsa, and Melvyn Nathanson.  Additive Combinatorics can be described as the study of additive structures of sets.   This area is attractive in that it has numerous connections with other areas of mathematics, including Number Theory, Ergodic Theory, Graph Theory, Finite Geometry, and Group Theory and has drawn the attention of many good mathematicians, including Fields Medalist Terence Tao (2006).

Tuesday, March 27, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 27, 2012
 Del Edit Copy
Submitted by west.
 Cory Palmer (UIUC Math)Turan numbers for forestsAbstract: The Turán number of a graph $H$, written $ex(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$ as a subgraph. The Erdős-Stone-Simonovits Theorem computes $ex(n,H)$ asymptotically for graphs of chromatic number at least 3. For bipartite graphs much is still unknown. Of particular interest is the Turán number for trees (this is the Erdős-Sós conjecture). We will concentrate our attention on the Turán number of forests. Bushaw and Kettle determined the Turán number of a forest made up of copies of a path of a fixed length. We generalize their result by finding the Turán number for a forest composed of arbitrary length paths. We also determine the Turán number for a forest made up of arbitrary size stars. In both cases we characterize the extremal graphs. (Joint work with Hong Liu and Bernard Lidicky.)

Tuesday, April 3, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 3, 2012
 Del Edit Copy
Submitted by west.
 Thomas Mahoney (UIUC Math)Extending graph choosability results to paintabilityAbstract: Introduced independently by Schauz and by Zhu, the Marker-Remover game is an on-line version of list coloring. The resulting graph parameter, paintability, is at least the list chromatic number (also known as "choosability"). We strengthen several choosability results to paintability. We study paintability of joins with complete or empty graphs. We determine upper and lower bounds on the paintability of complete bipartite graphs. We characterize 3-paint-critical graphs and show that claw-free perfect graphs with $\omega(G)\le3$ have paintability equal to chromatic number. Finally, we introduce and study sum-paintability, the analogue of sum-choosability.

Tuesday, April 10, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 10, 2012
 Del Edit Copy
Submitted by west.
 Robert E. Jamison (UIUC and Clemson University)Convexity Partition Numbers and MatchingsAbstract: In 1921 Radon showed that any $d+2$ points in ${\mathbb R}^d$ can be partitioned into two parts so that the convex hulls of the parts have nonempty intersection. In 1966 Tverberg generalized Radon's theorem to partitions into $m$ parts. These notions carry over naturally to any abstract space with a notion of convex hull. For such a space, the $m$-th partition number is the smallest integer $p_m$ such that any $p_m$ points can be partitioned into $m$ parts with the convex hulls of the parts having nonempty intersection. Radon's theorem for $m=2$ and Tverberg's theorem in general yield $p_m = (m-1)(d+1)+1$ for ordinary convexity on ${\mathbb R}^d$. Calder conjectured that Euclidean convexity is the extremal case: $p_m \le (m-1)(p_2-1)+1$ for any abstract convexity space. Eckhoff popularized this, now known as the Partition Conjecture. In 1981 Jamison used matchings in graphs to prove the Partition Conjecture for a class of convexities including partially ordered sets, trees, certain semilattices, and related structures. The purpose of this talk is to solicit improvements of Jamison's matching results that yield additional bounds on partition numbers.

Tuesday, April 17, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 17, 2012
 Del Edit Copy
Submitted by west.
 Frank R. Bernhart (visitor, Department of Mathematics, University of Illinois at Urbana-Champaign)Enumeration of special classes of outerplanar graphsAbstract: Arrange $n$ vertices equally spaced on a circle, labeled in counterclockwise order. Join some pairs by edges, drawn as chords without crossings. This general class has many interesting subfamilies, some of which can be counted using basic methods of enumeration, especially Lagrange Inversion. Catalan numbers and their generalizations arise frequently. We consider several such families: (1) Polygons with $n$ sides and $r$ diagonals whose bounded regions have $k$ sides. (2) Trees (no crossings allowed!). (3) Graphs where every component is a triangle (requiring components to be edges yields a familiar family counted by the Catalan numbers). (4) Every component is a vertex, an edge, or a cycle (plus subfamilies defined by forbidding isolated vertices or by forbidding edges joining consecutive points). Finally, we also consider supplementing these techniques by Burnside's Lemma when drawings are considered to be equivalent under rotation and reflection, yielding for example an enumeration of maximal outerplanar graphs.

Tuesday, April 24, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 24, 2012
 Del Edit Copy
Submitted by west.
 Mohsen Jamaali (Sharif University (Iran))On harmonious coloring of graphsAbstract: Let $G$ be a simple graph, and let $\Delta(G)$ denote the maximum degree of $G$. A harmonious coloring of $G$ is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number $h(G)$ is the least number of colors in such a coloring. In this talk, with a constraint on $\Delta(G)$, we determine the exact value of $h(G)$ when $G$ is a tree. Furthermore, some bounds on $h(G)$ are obtained in general for trees and for bipartite graphs. An analogous concept of harmonious edge coloring is introduced, and some results on the harmonious edge-chromatic number are proved.

Tuesday, May 1, 2012

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, May 1, 2012
 Del Edit Copy
Submitted by west.
 Christian Altomare (The Ohio State University)Antimatroid minors: The Graph Minor Theorem, Laver's Theorem, and Forbidden Antimatroid Minor TheoremsAbstract: This talk is designed to be accessible and (hopefully) of interest to graph theorists and logicians. The Graph Minor Theorem says that every minor closed property of finite graphs has a finite forbidden minor description. (One version of) Laver's Theorem states the same is true for suborder closed properties of countable total orders. A notion of minor for antimatroids, thought of as "combinatorial proof systems", specializes to graph minor and total order embeddability for those respective objects. This allows a conjectural unification of these two seemingly quite distinct theorems. We discuss this unification and antimatroid minor theorems as well.

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 ShatteringAbstract: 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 GraphsAbstract: 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

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, September 11, 2012
 Del Edit Copy
Submitted by lidicky.
 Bernard Lidicky   [email] (UIUC Math)Peeling the GridAbstract: Consider the set of points formed by the $n\times n$ grid, and the process that in each iteration removes from the point set the vertices of its convex-hull. Here, we prove that the number of iterations of this process is $O(n^{4/3})$; that is, the number of convex layers of the $n\times n$ grid is $\Theta(n^{4/3})$. This is joint work with Sariel Har-Peled.

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 EdgesAbstract: 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 conjectureAbstract: 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 TheoremAbstract: 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 CorollaryAbstract: 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

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, October 16, 2012
 Del Edit Copy
Submitted by lidicky.
 Hong Liu (UIUC Math)Multicolor Ramsey Numbers for Triple SystemAbstract: We consider some general results on multicolor Ramsey number for three-uniform hypergraphs, as well as Ramsey numbers for specific hypergraphs. All of this work is very preliminary and we are just at the stage of exploring the general problem. This is joint work with Maria Axenovich, Roman Glebov, Dhruv Mubayi and András Gyárfás

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 HypergraphsAbstract: 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 theoryAbstract: 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 graphsAbstract: 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 hypergraphsAbstract: 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 CliquesAbstract: 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 powerAbstract: 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

Graph Theory and Combinatorics
3:00 pm   in 147 Altgeld Hall,  Thursday, December 6, 2012
 Del Edit Copy
Submitted by lidicky.
 Dániel Gerbner   [email] (Alfréd Rényi Institute of Mathematics)An analogue of the Erdős-Ko-Rado theorem for multisetsAbstract: We are given a finite underlying set $X$. A multiset is an analogue of a subset, but elements can appear more than once. We consider multisets where the sum of the multiplicities is $k$. A family of multisets is called $t$-intersecting if every two members of the family have intersection of size at least $t$. We determine the maximum cardinality of $t$-intersecting families of multisets in case $2k-t \le |X|$. Joint work with Zoltán Füredi and Máte Vizer.

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 graphsAbstract: 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.