Title:Induced Ramsey numbers of P3 with other graphs
Speaker:Naeem Sheikh
 University of Illinois at Urbana-Champaign
Date:January 25, 2005
Abstract: The induced Ramsey number IR(G,H) equals n if there is a graph F on n vertices such that every 2-colouring of its edges with red and blue results in either a red copy of G as an induced subgraph of F, or an induced blue H, and no graph with fewer than n vertices has this property. The talk will present a few results on induced Ramsey numbers of P3 with other graphs. We prove that IR(P3,G) < |V(G)| + |E(G)| and then show that this bound is sharp when every component of G is a complete graph. We will also show a better (and sharp) bound when G is a complete multipartite graph.

This is joint work with A. Kostochka.



Title:2-Distance colouring of sparse planar graphs with +1 colors
Speaker:Oleg Borodin
 Institute of Mathematics, Novosibirsk, Russia
Date:February 1, 2004
Abstract: A vertex coloring is a 2-distance coloring if every two vertices at distance 1 or 2 have different colours. Clearly, each graph G with maximum degree D needs at least D+1 colors to be 2-distance colored, since it contains a D-star. We consider sufficient conditions, in terms of D and the girth, for a planar graph to be 2-distance (D+1)-colorable.

This is a joint work with A.O.Ivanova, T.K.Neustroeva, and, partly, A.N.Glebov and V.A.Tashkinov.



Title:Generalizations of the Erdös-Ko-Rado Theorem
Speaker:Kyung-Won Hwang
 University of Illinois at Urbana-Champaign
Date:February 8, 2005
Abstract: In 1961, P. Erdös, C. Ko, and R. Rado proved that if F is a k-uniform family of subsets of an n-set, with k< n/2, and every two members of F intersect, then |F| < {n-1 \choose k-1}. Many people generalized this theorem with one size k. We generalize the Erdös-Ko-Rado Theorem allowing several sizes ki.

This is joint work with Zoltán Füredi and Paul M. Weichsel.



Title:On 2-factor unique graphs
Speaker:Ron Gould
 Emory University
Date:February 15, 2005
Abstract: A graph G is 2-factor unique if it has a 2-factor X and every 2-factor of G is isomorphic to X. We consider questions about 2-factor unique graphs, tracing some old results as well as some very new results. A number of open questions will be presented. In particular, we will consider the case when the 2-factor is a hamiltonian cycle; such graphs are 2-factor hamiltonian. The maximum number of edges in such graphs will be determined exactly in both the bipartite and general cases. Further, extremal graphs will be shown, and we will determine when these graphs are unique.


Title:A note on semiantichains and unichain coverings
Speaker:Qi Liu
 University of Illinois at Urbana-Champaign
Date:February 22, 2005
Abstract: Saks and West conjectured that for every direct product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. In this talk we will prove that when both posets have width 2, the conjecture is true.

This is joint work with Douglas West.



Title: On minimum degree implying that a graph is H-linked
Speaker:Gexin Yu
 University of Illinois at Urbana-Champaign
Date:March 1, 2005
Abstract: et H be a fixed multigraph, possibly containing loops, with vertices h1, ... ,hm. A graph G is H-linked if for every choice of distinct v1,...,vm in V(G) there is a subdivision of H in G such that vi is the branch vertex representing hi (for all i). This generalizes the concept of k-linked graphs and other well-known path and cycle properties. In this paper we determine for each H a sharp threshold on minimum degree d(G) of G that forces a sufficiently large graph to be H-linked. That is, if d(G)> kH and n(G)> c(n(H)+e(H)), then G is H-linked.

This is joint work with Ron Gould and Alexandr Kostochka.



Title:Highly connected multicolored subgraphs
Speaker:Noah Prince
 University of Memphis
Date:March 8, 2005
Abstract: We consider the following Ramsey-type question: given an r-colo(u)ring of E(Kn), how large a k-connected subgraph can we find using s colo(u)rs? We solve a conjecture of Bollobás and Gyárfás concerning the case r=2 and s=1 and generalize results of Gyárfás and Füredi for general r with s=1. We study the cases when r and s approach infinity and determine several threshold functions in terms of s.

This is joint work with Henry Liu and Rob Morris.



Title:Extremal Graphs for the Sauer-Spencer Graph Packing Theorem
Speaker:Hemanshu Kaul
 University of Illinois at Urbana-Champaign
Date:March 15, 2005
Abstract: Let G1 and G2 be graphs of order at most n, with maximum degree D1 and D2, respectively. Say that G1 and G2 pack if their vertex sets map injectively into [n] so that the images of the edge sets are disjoint. The study of packings of graphs was started in the 1970s by Sauer and Spencer and by Bollobás and Eldridge. Sauer and Spencer showed that if D1D2 < n/2, then G1 and G2 pack. We extend this a bit by characterizing the graphs with D1 D2 = n/2 that do not pack: if D1 D2 < n/2, then G1 and G2 fail to pack if and only if one of G1 or G2 is a perfect matching and the other either is Kn/2,n/2 with n/2 odd or contains Kn/2+1.

This is joint work with Prof. Kostochka.



Title:2-Bases of Quadruples
Speaker:Zoltán Füredi
 University of Illinois at Urbana-Champaign
Date:March 29, 2005
Abstract: We are concerned with finding `bases' for the family of 4-sets from an n-set. In general, a base for a set system consists of a family of sets such that each set in the set system may be expressed as a union of two (possibly equal) sets from the family. The question is how small a base one can find. This is known exactly in very few cases, even when the set system is a natural one. For example, it is not known even for the power-set itself (the discrete cube).

The aim in this talk is to answer this question for the family of all the sets of size at most 4 from an n-set. In general, let Hn,k be the family of sets of size at most k from an n-set. The question of the smallest base for Hn,k is trivial for k < 2, and for k=3 it turns out to be a question about graphs whose answer follows immediately from Turán's theorem. So, the case k=4 is the first non-trivial case. It boils down to an interesting question about 3-graphs (3-regular hypergraphs), and it is somewhat surprising that it is possible to give an exact answer.

This is joint work with G.O.H. Katona.



Title:Semiregular factorizations of simple graphs, multigraphs, and pseudographs
Speaker:Anthony J. W. Hilton
 University of Reading (England) and Eastern Kentucky University
Date:April 5, 2005
Abstract: A (d,d+1)-graph is a graph whose degrees all lie in the set {d,d+1}. Such a graph is also called semiregular. An (r,r+1)-factor in a graph is a spanning subgraph that is itself an (r,r+1)-graph. A decomposition of a graph into edge-disjoint (r,r+1)-factors is called an (r,r+1)-factorization.

I shall discuss the general question of which graphs have an (r,r+1)-factorization. I shall also consider the question of how many (r,r+1)-factors there can be in an (r,r+1)-factorization of a given graph G.



Title:A cut-and-paste sorting algorithm for permutations
Speaker:Daniel Cranston
 University of Illinois at Urbana-Champaign
Date:April 12, 2005
Abstract: We consider the problem of determining the maximum number of moves required to sort a permutation of [n] using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. Every permutation of [n] can be transformed to the identity in at most \ceiling{2n/3} moves, and some permutations require at least \floor{n/2} moves.

This is joint work with Douglas West and Hal Sudborough.



Title:Partitions and compositions defined by inequalities
Speaker:Carla Savage
 North Carolina State University (Computer Science)
Date:April 19, 2005
Abstract: In this talk we focus on techniques for enumerating nonnegative integer solutions to a set of linear inequalities, with a focus on applications to the theory of partitions and compositions. Examples include plane partitions, lecture hall partitions, Cayley compositions, anti-lecture hall compositions, and Euler-type partition identities.

We propose some elementary techniques which have been surprisingly successful at giving simpler proofs of known results and, so far, modestly successful at giving new results. This includes joint work with Sylvie Corteel, Herbert Wilf, and N.C. State students Will Davis, Erwin D'Souza, Sunyoung Lee, and Daniel Wong.



Title:On the size of a critical degree three graph
Speaker:Mark K. Goldberg
  Rensselaer Polytechnic Institute
Date:April 26, 2005
Abstract: A graph is critical if its edge-chromatic number exceeds the maximum vertex degree and the removal of any edge lowers the edge-chromatic number. It is known that the number m of edges in any critical n-vertex graph with maximum degree 3 is at least 4n/3. For the critical graph obtained by deleting one vertex from the Petersen graph, the bound is an equality. In 1974, Jakobsen conjectured that for all other graphs the bound is strict. This conjecture follows from a remarkable result, generally not well known, published in 1978 in JCT by Jack Hursch Jr.

In our talk, we will present the details of Hursch's result. We will also discuss a conjecture that m > (11n - 3)/ for such graphs.



Title:On k-detour subgraphs of hypercubes
Speaker:Alexandr V. Kostochka
 University of Illinois at Urbana-Champaign
Date:May 3, 2005
Abstract: A spanning subgraph G of a graph H is a k-detour subgraph of H if the distance between any two vertices x and y in G exceeds their distance in H by at most k. Such subgraphs are also called additive k-spanners. We discuss k-detour subgraphs of the n-dimensional cube Qn that have few edges or moderate maximum degree. Let D(k,n) be the minimum possible maximum degree of a k-detour subgraph of Qn. The main result is that if k> 2 and n> 21, then exp(-2k)(n/ ln n) < D(k,n) < 20(n lnln n)/(ln n). On the other hand, for fixed even k> 4 and large n, there is a k-detour subgraph of Qn with average degree at most 2+24-k/2+o(1).

This is joint work with Nana Arizumi and Peter Hamburger.



© Jozef Skokan, 2005