Department of

# Mathematics

Seminar Calendar
for Graph Theory and Combinatorics events the year of Monday, November 29, 2004.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
     October 2004          November 2004          December 2004
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             1  2  3  4
3  4  5  6  7  8  9    7  8  9 10 11 12 13    5  6  7  8  9 10 11
10 11 12 13 14 15 16   14 15 16 17 18 19 20   12 13 14 15 16 17 18
17 18 19 20 21 22 23   21 22 23 24 25 26 27   19 20 21 22 23 24 25
24 25 26 27 28 29 30   28 29 30               26 27 28 29 30 31
31


Tuesday, January 27, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, January 27, 2004

#### On strong chromatic index of bipartite graphs

###### Kittikorn Nakprasit (UIUC Math)

Abstract: A strong edge-coloring of a graph G is an edge-coloring in which every color class is an induced matching; that is, if uv and wz have the same color, then the subgraph induced by those four vertices has only those two edges. The strong chromatic index s'(G) is the minimum integer number of colors in a strong edge-coloring of G. Brualdi and Quinn conjectured that for every bipartite graph G, s'(G) is bounded by D1 D2, where D1 and D2 are the maximum degrees among vertices in the two partite sets. We give an affirmative answer for D1=2.

Tuesday, February 3, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, February 3, 2004

#### Bounds on set systems with restricted k-wise intersections

###### Weiting Cao (UIUC Math)

Abstract: Maximizing the size of a family of subsets of an n-element set under some conditions on intersections of its members is a classical theme in extremal set theory. For example, Frankl and Wilson proved that the sum from i=0 to s of n\choose i is an upper bound when the sizes of pairwise intersections are restricted to a set L of s nonnegative integers. Snevily proved their conjecture that n can be replaced with n-1 in the upper bound when L is a set of s positive integers. These bounds hold also when L is viewed as a set of s congruence classes modulo a prime p.

We generalize these bounds by placing the restriction on the intersections of k distinct members of the family. Again let L be a set of s congruence classes modulo a prime p. Let H be a family of subsets of [n] such that the size modulo p of each member of H is not in L, but the size modulo p of every intersection of k distinct members of H is in L. We prove that the sum from i=0 to s of (n-1)\choose i is an upper bound on |H|. This improves an earlier bound by Grolmusz having n in place of n-1. We use the linear algebra method, obtaining the bound from the dimension of a linear space of polynomials. This work is joint with Kyung-Won Huang and Douglas West.

Tuesday, February 10, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, February 10, 2004

#### The best choice problem for partially ordered sets

###### Michal Morayne (Wroclaw University of Technology, Wroclaw, Poland)

Abstract: The classical secretary problem concerns the best strategy in an on-line decision process. The administrator interviews n candidates for a job The candidates are linearly ordered in qualifications, but the administrator sees them in a random permutation and can only compare the relative ranks of the ones seen so far. The aim is to choose the absolute best candidate, but the only one that can be chosen is the currently interviewed one. The optimal strategy is well known and gives the administrator a probability better than 1/e of choosing the best candidate.

The problem has been generalized in various ways. Here we consider the problem with a partial order instead of a linear one. This seems to better approximate real life situations where options need not be linearly ordered. The aim of this talk is to discuss optimal and effective strategies for the partial order generalization of the secretary problem. Such strategies in some specific situations (such as a binary tree order and an unknown order) will be considered. Interesting combinatorial counting problems that arise when looking for such strategies will be discussed.

Tuesday, February 17, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, February 17, 2004

###### Gexin Yu (UIUC Math)

Abstract: We introduce the notion of H-linked graphs, where H is a fixed graph with vertices u1,...,um. A graph G is H-linked if for every choice of vertices v1,...,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing ui (for all i). This generalizes the notions of k-linked and k-ordered graphs.

Given k and n, we determine the least integer d such that, for every graph H with k edges and minimum degree at least two, every n-vertex graph with minimum degree at least d is H-linked. This value D(k,n) appears to equal the least integer d' such that every n-vertex graph with minimum degree at least d' is k-connected. On the way to the proof, we extend a theorem by Kierstead et al on the least integer d" such that every n-vertex graph with minimum degree at least d" is k-ordered.
This is joint work with Alexandr Kostochka.

Tuesday, February 24, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, February 24, 2004

#### On a common feature in certain sequences

###### Sergey Kitaev (University of Kentucky)

Abstract: The Arshon sequence was given in 1937 in connection with the problem of constructing a square-free sequence on a given alphabet, that is a sequence that does not contain any subword of the type XX, where X is any nonempty word over the alphabet. The existence of such sequences, as well as the existence of sequences avoiding other kinds of repetitions, were studied in algebra, discrete analysis, and dynamical systems.

The Dragon curve (the paperfolding sequence) was discovered by physicist John Heighway and described by Martin Gardner in 1978. It is defined as follows: we fold a sheet of paper in half, then fold in half again, and again, etc. and then unfold in such way that each crease created by the folding process is opened out into a 90-degree angle. The "curve" refers to the shape of the partially unfolded paper as seen edge on. The Dragon curve is related to the sigma-sequence used by Evdokimov in 1968 in order to construct chains of maximal length in the n-dimensional unit cube.

The Peano curve was studied by the Italian mathematician Giuseppe Peano in 1890 as an example of a continuous space filling curve. The Peano infinite word is a discrete analog of the Peano curve.

Are there any similarities between the Arshon sequence, the Dragon curve, and the Peano infinite word in terms of combinatorics on words? In this talk, I will answer this question using some recent results.

Tuesday, March 2, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, March 2, 2004

#### An unexpected drop in the circular chromatic number

###### Seog-Jin Kim (UIUC Math)

Abstract: A (k,d)-coloring of a graph G is map from V(G) to the set of congruence classes modulo k so that adjacent vertices are assigned classes differing by at least d. The circular chromatic number of G is the minimum ratio k/d such that G has a (k,d)-coloring. This parameter has become an important subject of study in recent years as a refinement of the ordinary chromatic number, since the chromatic number is always the ceiling of the circular chromatic number.

The chromatic number never declines by more than one when a vertex is deleted, and it was widely thought that the same would hold for the circular chromatic number. In this talk, we present the surprising construction by Xuding Zhu of an infinite family of graphs with circular chromatic number 4 such that deletion of any vertex reduces the circular chromatic number to 8/3.

Tuesday, March 9, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, March 9, 2004

#### Dominating sets in k-majority tournaments

###### Alexandr V. Kostochka (UIUC Math)

Abstract: The k-majority tournament generated by 2k-1 linear orders on a finite set V is the tournament with vertex set V having an edge from v to w if v precedes w in at least k of the orders. Erdös and Moser proved that for some k(n) in O(n/log n), every n-vertex tournament is a k(n)-majority tournament.

Kierstead and Trotter conjectured that for each k, there is a constant F(k) such that every k-majority tournament (with no restriction on the number of vertices) has a dominating set of size at most F(k). They also conjectured that F(2)=3; that is, every tournament generated by majority rule from a set of three linear orders has a dominating set of size 3. In this talk we prove these conjectures and describe some open problems. The result is joint work with G. Brightwell, H. Kierstead, and P. Winkler.

Friday, March 12, 2004

1:00 pm in Altgeld Hall,Friday, March 12, 2004

#### Global Optima Results for the Kauffman \$NK Model

1:00 pm in Altgeld Hall,Friday, March 12, 2004

#### To Be Announced

Tuesday, March 16, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, March 16, 2004

#### Global optima results for the Kauffman NK model

###### Hemanshu Kaul (UIUC Math)

Abstract: Many scenarios in theoretical biology, physics, and business organizations can be modeled as systems with several interacting components that can be in various states. The aim is to maximize a performance measure involving contributions from each component. This measure may depend on both the state of each component and on interactions between components. In 1987, Kauffman and Levin introduced a combinatorial optimization model for such systems, called the Kauffman NK model, where N is the number of components of the system and K measures the interaction between the components. This was proposed to model the evolution of genomes in theoretical biology but has since been applied in other areas as listed above.

Previous research on the NK model has emphasized simulations and analysis of local optima. Here we focus on rigorous results for global optima. We describe a computational setup using a stochastic network model, which leads to applicable strategies for computing bounds on global optima when K is small or is close to N. Recent papers used tools from analysis and probability to obtain bounds on the expected value of the global optima for fixed K and large N. We present bounds when K grows with N, using elementary probabilistic combinatorics and order statistics. We use a `dependency' graph to convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about mutual dependencies among the underlying random variables. If time permits, an alternate upper bound and the analysis for the cases of underlying uniform and normal distributions will be presented. This is joint work with Prof. S.H. Jacobson.

Tuesday, March 30, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, March 30, 2004

#### A hierarchy of randomness for graphs

###### Vera Sos (Hungarian Academy of Science)

Abstract: We formulate four families of problems with the aim of distinguishing different levels of randomness. The first is completely non-random, being the ordinary Ramsey-Turan problem. In the three subsequent problems we formulate randomized variations of it. We show that these four levels form a hierarchy. The problems and results are strongly related to three basic topics in graph theory: extremal graph theory, Ramsey theory, and the theory of random graphs. (Joint work with M. Simonovits.)

Tuesday, April 6, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, April 6, 2004

#### When the greedy algorithm fails

###### Gregory Gutin (Royal Holloway, University of London)

Abstract: We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message of this talk is that the greedy algorithm should be used with great care, since for many optimization problems its usage seems impractical even for generating a starting solution (that will be improved by a local search or another heuristic). (Joint work with J. Bang-Jensen and A. Yeo.)

Tuesday, April 13, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, April 13, 2004

#### Cones over graphs

###### Michael Stiebitz (Technical University of Ilmenau, Germany)

Abstract: The cone Mr(G) over a given graph G is obtained by taking the categorial product of G and a path P of length r+1 with a loop at one end, and then identifying all vertices whose second coordinate is the non-loop end of P.

Some instances of this construction are well known. The cone M1(G) is the graph obtained from G by adding a vertex joined to all of V(G). The cone M2(G) is Mycielski's construction over G. This was invented in 1955 by Mycielski to generate triangle-free k-chromatic graphs for all k >= 2. It is easy to show that chi(M1(G))=chi(G)+1 and chi(M2(G))=chi(G)+1.

Do all cones over a graph G have chromatic number larger than G? For example, is Mr(C2k+1) always 4-chromatic? We show that this question has a topological flavor.

Tuesday, April 20, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, April 20, 2004

#### Extremal functions for graph linkages

###### Paul Wollan (Georgia Institute of Technology)

Abstract: A graph G is k-linked if for any 2k distinct vertices s1,...,sk and t1,...,tk there exist disjoint paths P1,...,Pk such that for each i the endpoints of Pi are si and ti. Bollobás and Thomason showed that connectivity at least 22k suffices to make a graph k-linked. Using a more direct induction argument, we have shown that 18k-connected graphs are k-linked. I will outline the argument and discuss recent improvements leading to a result of Kawarabayashi, Kostochka, and Yu that 12k-connected graphs are k-linked. Along these same lines, we further improved the analysis to show that connectivity at least 10k is sufficient. I will also discuss how the proof method can be used to show an optimal bound in the case k=3 and how the proof method can be used to find extremal functions for more general structures. This is joint work with Robin Thomas.

Tuesday, April 27, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, April 27, 2004

###### Norihide Tokushige (Ryukyu University and Emory University)

Abstract: We present some Erdos-Ko-Rado type problems and partial results concerning the "r-wise t-intersecting" version, the "r-wise intersecting and r-wise union" version, and the "r-wise cross-intersecting" version. One of our main tools is random walks; we show how to use random walks to get upper bounds for the size of multiply intersecting families. This is joint work with Peter Frankl.

Tuesday, May 4, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, May 4, 2004

#### Path-perfection of complete bipartite graphs

###### Weiting Cao (UIUC Math)

Abstract: A graph G is path-perfect if there is a positive integer n such that the edge set E(G) of the graph G can be partitioned into n paths of lengths 1,2,...,n. We prove the conjecture of Fink and Strait: For t <= s, the complete bipartite graph Ks,t is path-perfect if and only if there is a positive integer n such that 2t >= n and n(n+1)=2ts. (This is joint work with Prof. Peter Hamburger.)

Tuesday, August 31, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, August 31, 2004

#### Two topics revisited

###### Alexandr Kostochka (UIUC Math)

Abstract: First topic: Small triangle-free planar graphs that are not 3-list colorable. An example on 119 vertices was reported a year ago. In this talk, two examples on 98 and 97 vertices will be presented. This is joint work with A. Glebov and V. Tashkinov.

Second topic: An extension of Brooks' Theorem. Kittikorn Nakprasit presented last winter our extension of Brooks' Theorem: If G is a KD+1-free graph with maximum degree at most D (where D >= 3), and f is a proper D-coloring of G-v for some v\in V(G), then G has a proper D-coloring f' such that the sizes of all color classes except one are the same. I will discuss some corollaries of this result.

Tuesday, September 7, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, September 7, 2004

#### Results on the pagenumber of k-trees

###### Jennifer Vandenbussche (UIUC Math)

Abstract: A k-page embedding of a graph G is an ordering of V(G) (along the "spine" of a book) together with an assignment of E(G) to k pages such that no two edges on the same page are crossing. The pagenumber of a graph G is the minimum k such that G has a k-page embedding. The class of k-trees is defined inductively: A graph G is a k-tree if it is Kk or is obtained from a k-tree by adding a new vertex adjacent to a k-clique.

It has been proved that the pagenumber of a k-tree is at most k+1, and conjectured that k is in fact a valid upper bound. We present an example of a 3-tree that cannot be embedded in three pages, providing a counterexample to this conjecture. We also present a new class of k-trees for which the conjecture holds and give an algorithm to produce a k-page embedding. (This is joint work with Gexin Yu and Douglas West as part of the summer REG.)

Tuesday, September 14, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, September 14, 2004

#### The number of edge-colorings with no monochromatic cliques

###### Jozsef Balogh (Ohio State University)

Abstract: Let F(n,r,k) denote the maximum number of distinct r-edge-colorings of an n-vertex graph that avoid monochromatic copies of Kk. Erdös and Rothschild conjectured more than 20 years ago that when n is sufficiently large, F(n,2,k)=2tk-1(n), where tk(n) is the maximum number of edges of a Kk+1-free graph with n vertices (determined by Turán's Theorem). This was proved for k=2 by Yuster in 1996.

We prove this conjecture for up to 3 colors and disprove it for larger r. That is, for every fixed k and for n sufficiently large, F(n,2,k)=2tk-1(n) and F(n,3,k)=3tk-1(n). On the other hand, for fixed r>3 and k>2, the function F(n,r,k) is exponentially bigger than rtk-1(n). The proofs use Szemerédi's Regularity Lemma plus additional tools in extremal graph theory and provide an rare example of a precise result proved by the Regularity Lemma. We shall review several other problems that were solved using our methods. (This is joint work with N. Alon, P. Keevash, and B. Sudakov.)

Tuesday, September 21, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, September 21, 2004

#### How to Exchange Items

###### Sujay Sanghavi (UIUC Coordinated Science Lab)

Abstract: This work looks at the exchange of goods in the absence of a divisible commmodity of common value, like money. Each agent comes to the market with one item and a strictly ordered preference list of (a subset of) other items it would be willing to exchange its own item for. All lists are revealed to a central authority, which then makes a recommendation on how the agents should trade so that each agent gets one item.

It is shown that a simple, fast "greedy" algorithm for setting up the exchanges has surprising properties: no group of agents can deviate from the recommendation, or jointly reveal false lists to the centre, to the advantage of all members of the group - EVEN IF other agents in the system are deviating / lying.

Tuesday, September 28, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, September 28, 2004

#### Fire containment on trees and grids

###### Stephen Hartke (UIUC Math -- NOTE change of speaker)

Abstract: We consider a deterministic discrete-time model of fire spread introduced by Hartnell, where the fire spreads to adjacent vertices at each time step. A limited number of firefighters can be deployed per timestep to protect some vertices from catching fire. How should the firefighters be deployed to minimize the total number of burnt vertices? We consider this question for finite trees and for infinite d-dimensional square grids.

Tuesday, October 5, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, October 5, 2004

#### Tree-thickness and caterpillar-thickness of connected graphs

###### Qi Liu (UIUC Math)

Abstract: In 1978, Chung proved that every connected graph G with n vertices decomposes into at most \ceil(n/2) trees. We prove that a connected graph with n vertices and girth g decomposes into at most \floor(n/g)+1 trees, if g >= 5, and this is sharp. We prove weaker results when g=4.

A caterpillar is a tree having a single path incident to all edges. We prove that a connected outplanar graph G with girth 4 decomposes into at most \ceil(3n/8) caterpillars, and this is sharp. This is joint work with Douglas West and Derrick Cheng.

Tuesday, October 12, 2004

3:00 pm in Altgeld Hall,Tuesday, October 12, 2004

#### The structure of pebbling moves and optimal graph pebbling

###### Kevin Milans (UIUC Computer Science)

Abstract: Consider a graph G and a distribution of pebbles to the vertices of G. A pebbling move consists of removing two pebbles from some vertex v and placing one pebble on a neighbor of v. We present a characterization of when a given set of (unordered) pebbling moves may be placed in some order \sigma so that \sigma is a valid sequence of pebbling moves. As a consequence, when designing sequences of pebbling moves, one may focus on choosing which pebbling moves to make as opposed to the order in which to make them.

We also present results on optimal graph pebbling. The optimal pebbling number of a graph G is the minimum k such that there exists a distribution of k pebbles to the vertices of G such that for any vertex v, there exists a sequence of pebbling moves which results in a pebble on v. We show that for any connected n-vertex graph G, the optimal pebbling number of G is at most the ceiling of 2n/3. If time permits, we may give a simplified proof of the well-known results equality holds when G is a path or a cycle. (Joint work with David Bunde, Bryan Clark, Dan Cranston, Douglas West, and Erin Wolf.)

Tuesday, October 19, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, October 19, 2004

#### Large graphs with no long induced path

###### Douglas B. West (UIUC Math)

Abstract: A graph is H-free if it has no induced subgraph isomorphic to H. By analogy with the classical extremal Turan problem for forbidden subgraphs, let ex*(D;H) be the maximum number of edges in an H-free connected graph with maximum degree D. This value is finite if and only if H is a disjoint union of paths. Earlier results include ex*(D;P4)=D2 and the exact computation of ex*(D;2P3). For m >= 6, we improve the known bounds by showing that ex*(D;Pm)\in \Theta(D\ceil(m/2)), with leading coefficient between 1/8 and 1/2 when m is odd and between 1/2 and 2 when m is even. For m=5, we determine the exact value. (Joint work with Myung Chung and Tao Jiang.)

Tuesday, October 26, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, October 26, 2004

#### The Rényi-Ulam pathological liar game with a fixed number of lies

###### Robert Ellis (Texas A&M University)

Abstract: The q-round Rényi-Ulam pathological liar game with k lies on the set [n]:={1,...,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A of [n] and Carole either assigns 1 lie to each element of A or to each element of [n]-A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is equivalent to a covering problem in the discrete hypercube, and it is dual to the original Rényi-Ulam liar game, for which the winning condition is that at most one element has k or fewer lies. We give the exact smallest n for which Paul can win the pathological liar game with 1 or 2 lies, and we show that n is within an absolute constant of the coding theoretic sphere bound when k is fixed. This is already known to hold for the original Renyi-Ulam liar game due to a result of J. Spencer.

Tuesday, November 2, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, November 2, 2004

#### On Graph Coloring: list-coloring, coloring extensions, and graphs on surfaces

###### Joan Hutchinson (Macalester College and UColorado-Denver)

Abstract: We consider solved and unsolved problems on list-coloring, coloring extensions, and their connections. In the latter, parts of a graph are precolored, and one asks when and how the precoloring extends to the whole graph. A precoloring constrains the colors on neighboring vertices and so leads to a list-coloring problem. We consider these problems for all graphs, for planar graphs, and for graphs on surfaces. This talk includes joint work with Mike Albertson of Smith College, Emily Moore of Grinnell College, and Radhika Ramamurthi (UIUC graduate) of CSU San Marcos.

Tuesday, November 9, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, November 9, 2004

#### The Mathematics of Postage: New Fast Algorithms for the Frobenius Problem

###### Stan Wagon (Macalester College, St. Paul, Minnesota)

Abstract: Let A be a finite set of positive integers, viewed as postage stamp denominations. It turns out that when the elements of A have no common factor, there is a largest amount of postage that cannot be expressed using stamps with these denominations; larger values are nonnegative integer combinations of the elements of A. For example, if A = {6, 9, 20} (the Chicken McNugget numbers), then every number beyond 43 can be represented. The greatest nonrepresentable integer is called the "Frobenius number" of A.

The classic Frobenius problem for {a, b, c, ...} has two parts: (1) determine the Frobenius number, and (2) given a target M, find nonnegative coefficients x, y, z, ... such that x a + y b + z c + ... = M. I will show how a shortest-path algorithm for directed weighted graphs leads to a reasonably efficient solution for input sizes less than one million. More advanced techniques lead to a fast solution even when the integers are very large, provided that the size of A is at most 6. (Joint work with Dale Beihoffer, David Einstein, and Albert Nijenhuis.)

Tuesday, November 16, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, November 16, 2004

#### Ramsey results for 3-coloring and odd cycles

###### Miklos Simonovits (Renyi Institute, Hungary, and University of Memphis)

Abstract: For graphs G1,..., Gk, the Ramsey number R(G1,...,Gk) is the minimum integer N such that for any k-coloring of edges of the complete graph KN there exists a color i for which the corresponding color class contains Gi as a subgraph. Bondy and Erdös conjectured that if n is odd, then R(Cn,Cn,Cn)=4n-3. We prove this conjecture and some related stability theorems.

Tuesday, November 30, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, November 30, 2004

#### Finding a monochromatic subgraph or a rainbow path

###### Jeno Lehel (University of Memphis)

Abstract: Let f(G,H) denote the least integer n such that in every coloring of the edges of a clique Kn there is either a monochromatic copy of the graph G or a multicolored (rainbow) copy of the graph H. For particular cases of G or H the mono/rainbow function f relates to the usual Ramsey and local Ramsey numbers. We show that for the paths Pk with k=4 or k=5, f(G,Pk) equals the (k-2)--color diagonal Ramsey number of G. A similar mono/rainbow function defined for complete bipartite graphs will be also mentioned. (Joint work with A. Gyárfás, R.H. Schelp, and P. Balister.)

Tuesday, December 7, 2004

3:00 pm in 241 Altgeld Hall,Tuesday, December 7, 2004

#### Decomposition of products of regular graphs into isomorphic trees

###### Douglas B. West (UIUC Math)

Abstract: Let T be a tree with m edges. Ringel conjectured that the complete graph K2m+1 decomposes into copies of T; such a partition is a T-decomposition. Häggkvist posed the more general conjecture that every 2m-regular graph has a T-decomposition. Graham and Häggkvist conjectured that also every m-regular bipartite graph has a T-decomposition. Later work by Snevily and by Avgustinovitch obtained T-decompositions for various classes of 2m-regular graphs and m-regular bipartite graphs. We extend their ideas to enlarge the families of 2m-regular graphs and m-regular bipartite graphs that are known to have T-decompositions. The new families consist of various cartesian products of regular graphs. (This is joint work with Alexandr Kostochka.)

Tuesday, December 14, 2004

12:00 pm in 241 Altgeld Hall,Tuesday, December 14, 2004

#### How Random is the Human Genome?

###### Peter Winkler (Dartmouth)

Abstract: Now that the human genome is (mostly) sequenced, how do we know when some statistical fact about that random-looking string of 3 billion A's, C's, G's and T's is significant? For example, there are strings of length 11 which appear nowhere in the sequence; does this mean anything?

The speaker will describe an efficient combinatorial approach to problems of this sort, implemented with a group of scientists at Rockefeller University (Andy DeWan, Chad Hayes, Josephine Hoh, Jurg Ott, Tony Parrado, and Richard Sackler).