UIUC Dept. of Mathematics Seminar Calendar

      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 hypercube
Abstract: 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 loser
Abstract: 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 Rank
Abstract: 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

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 graphs
Abstract: 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)
K_s,t-minors in dense graphs and in (s+t)-chromatic graphs
Abstract: 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 bandwidth
Abstract: 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 Nathanson
Abstract: 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 forests
Abstract: 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 paintability
Abstract: 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 Matchings
Abstract: 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 graphs
Abstract: 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 graphs
Abstract: 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 Theorems
Abstract: 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

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

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 multisets
Abstract: 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 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.