Algorithms Time: Tuesday, 14:00 - 16:00 Organizer: Paulo Feofiloff

The largest and smallest components of combinatorial objects (14:00 - 15:00) Presenter:  Bruce Richmond It is elementary that the integer n can be factored into its prime factors which we presently call components. A polynomial over a finite field can be factored into its irreducible factors which we refer to as components. A permutation can be factored into its cycles which we call also call components. The polynomials are an example of an additive number system as introduced by J.\ Knopfmacher. The integers and cycles are examples of multiplicative number systems again introduced by J.\ Knopfmacher. The book by S. Burris contains a more recent discussion of these topics than Knopfmacher's. There is a natural size associated with each of these objects. We can talk of the smallest component therefore. Let b_{n}(c_{n}) denote the number of objects (components) of size n. Let b_{n,m} denote the number of objects of size n having smallest component of size \ge m. Our Theorem 1 gives conditions under which the quantity b_{n,m}/b_{n} is asymptotically equivalent to the probability that the integer n\le N has smallest prime factor >= m as N \rightarrow \infty. The Buchstab function \omega(.) is defined as the solution to the differential-difference equation u\omega(u) & = & 1+\int_{2}^{u}\omega(u-1)\du, u\ge2 u\omega(u) & = & 1 \mbox{ if } 1\le u <2. Our first result is Theorem 1 Suppose \frac{c_{n}}{n!}\sim \frac{1}{n\rho^{n}},\;\;\;\frac{b_{n}}{n!}\sim \frac{1}{\rho^{n}} for labeled objects and c_{n} \sim \frac{\rho^{-n}}{n}, b_{n} \sim \rho^{-n} for unlabeled objects. Then uniformly for 2 <= m <= n b_{n,m}\sim \frac{b_{n }(\omega(n/m)+O(\frac{1}{m^{2}}))}{m}. Remark 1: Frequently the hypothesis of Theorem 1 is established using the singularity analysis of Flajolet and Odlyzko. See Flajolet and Soria for many examples. Remark 2: Panario and Richmond derive Theorem 1 using singularity analysis. The present proof produces the result in a simpler and much more direct way. In particular the Buchstab function is not derived in the form of the inverse of its Laplace transform. Our present derivation is a close analogue of the proof of the result for integers free of small factors presented by Tenenbaum. We give all the details because the proof is not too long and we wish to highlight the similarities between the combinatorics and the number theory. What do random polynomials over finite fields look like? (15:00 - 16:00) Presenter:  Daniel Panario In this talk we survey old and new results about random univariate polynomials over finite fields. We are interested in three aspects: (1) the decomposition of a random polynomial in terms of its irreducible factors, (2) the use of random polynomials in algorithms, and (3) the average-case analysis of algorithms that use polynomials over finite fields. We show a methodology that can be systematically employed to study the most important features of these problems. This framework has two basic components: generating functions to express the properties of interest, and asymptotic analysis when exact estimations are not possible. This generic methodology naturally relates finite fields and their applications to combinatorics and analytic number theory.

Computational biology Time: Monday, 16:30 - 18:00 Organizer: Marie-France Sagot and Yoshiko Wakabayashi

Bases of repetead motifs with don't cares (17:00 - 18:00) Presenter:  Marie-France Sagot The notion of a basis of repeated motifs with don't cares in an input string of n symbols drawn over an alphabet~A was initially introduced in 2000 by L. Parida and co-workers. The don't care is a special symbol matching any symbol of A. The notion of a basis of motifs corresponds to the algebraic one of a set of generators for all motifs with don't cares appearing at least q times in the string, for a given integer~q greater than one. Besides its elegance, the notion could be of great practical usefulness if the basis is of small size as in general there can be an exponential number of repeated motifs with don't cares. We investigate the problem of determining the basis of repeated motifs with don't cares in an input string. New upper and lower bounds on the problem are given. A notion of basis that is provably smaller than (and contained in) previously defined ones is introduced. Such basis can be computed in less time and space, and is still able to generate the same set of motifs. Unfortunately, it is possible to prove that the number of motifs in all the bases that have been defined so far grows exponentially with~q, a point that went unnoticed in earlier work. A polynomial-time algorithm can therefore also exist only for fixed q. Joint work with Maxime Crochemore [Institut Gaspard Monge, University of Marne-la-Vallée, France] and with Roberto Grossi and Nadia Pisanti [Department of Computer Science, University of Pisa, Italy]. References A. Apostolico and L. Parida, Compression and the wheel of fortune, In Data Compression Conference (DCC), 2003. L. Parida, I. Rigoutsos, A. Floratos, D. Platt, and Y. Gao, Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm In SIAM Symposium on Discrete Algorithms (SODA), 2000. J. Pelfrene, S. Abdeddaïm, and J. Alexandre, Extracting approximate patterns. In Combinatorial Pattern Matching (CPM), 2003. N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot, A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum. In Mathematical Foundations of Computer Science (MFCS), 2003.

Computational biology Time: Tuesday, 11:00 - 12:30 Organizer: Marie-France Sagot and Yoshiko Wakabayashi

Efficient secondary structure prediction (11:00 - 11:30) Presenter:  Katia S. Guimarães We will present a simple and efficient neural network model for protein secondary structure prediction. Combining only three neural networks, an average Q3 accuracy prediction by residues of 75,93% is achieved. This value is better than the best results reported on the same test and training database, CB396, using the same validation method. For a second database, RS126, an average Q3 accuracy of 74,13% is attained, which is better than each individual method, being defeated only by CONSENSUS, a rather intrincate engine, which is a combination of several methods. We will also discuss the use of Principal Components Analysis (PCA) to try to avoid the "curse of dimensionality", which led to results almost as good as the previouly mentioned, and still beating all predictors different from CONSENSUS. Joint work with Jeane C.B. de Melo and George D.C. Cavalcanti. References Combining few NNs for Effective Secondary Structure Prediction K. Guimaraes, J. Melo, G. Cavalcanti 3rd. IEEE Symp. on Bioinformatics and Bioengineering - BIBE 2003. Bethesda, USA, March/2003. PCA Feature Extraction for Protein Secondary Prediction Jeane melo, George Cavalcanti, and Katia Guimarães Internl. Joint Confer. on Neural Networks - IJCNN'03, Portland, EUA, July/2003. A sparse dynamic programming algorithm for alignment with inversions (11:30 - 12:00) Presenter:  Alair Pereira do Lago Alignment of sequences is widely used for sequence comparisons and, in its model, only biological events like mutations, insertions and deletions are considered. It admits a dynamic programming algorithm and has become a fundamental tool for DNA and protein evolutive studies. Other biological events like inversions are not automatically detected by the usual alignment algorithms and some alternative approaches have been tried in order to include inversions or other kind of rearrangements. We will discuss some of these approaches that include inversions to the comparison studies and we will show a dynamic programming algorithm for one of them. We will also present a sparse dynamic programming implementation of this algorithm that compacts the tables involved.

Computational biology Time: Wednesday, 11:00 - 12:30 Organizer: Marie-France Sagot and Yoshiko Wakabayashi

Haplotypes analysis: finding blocks and founders (11:00 - 11:30) Presenter:  Esko Ukkonen The talk discusses algorithms for finding so-called haplotype blocks as well as the problem of constructing founder sequences and recombination points for a given set of haplotypes. Discussion (11:30 - 12:00) Presenter:  Esko Ukkonen

Computational biology Time: Thursday, 16:30 - 18:00 Organizer: Marie-France Sagot and Yoshiko Wakabayashi

Approximation algorithms for measuring distances between phylogenetic trees (16:30 - 17:00) Presenter:  Estela M. Rodrigues There are various techniques for reconstructing phylogenetic trees from data, and in this context the problem of determining how distant two such trees are from each other arises naturally. Various metrics for measuring the distance between two phylogenies have been defined. Another way of comparing two trees T and U is to compute the so called {\em maximum agreement forest} of these trees. Informally, the number of components of an agreement forest tells how many edges from each of T and U need to be cut so that the resulting forests agree, after performing all forced edge contractions. This problem is NP-hard even when the input trees have maximum degree~2. Hein, Jiang, Wang and Zhang presented in 1996 an approximation algorithm for it, claimed to have performance ratio 3. We show that the performance ratio of Hein's algorithm is~4, and we also present two new 3-approximation algorithms for this problem. We mention how one of these 3-approximation algorithms can be generalized to a (d+1)-approximation algorithm for trees with bounded degree d >= 2. Finally, we report on some computational experiments comparing the performance of the algorithms presented in this paper. This is joint work with M.-F. Sagot and Y. Wakabayashi

Combinatorial optimization Time: Monday, 11:00 - 12:30 Organizer: Cristina Fernandes and Yoshiko Wakabayashi

The datapath merging problem in the design of reconfigurable systems (11:00 - 11:30) Presenter:  Cid Carvalho de Souza In this talk we discuss the problem of merging circuit datapaths in the design of reconfigurable systems. We show that this problem can be formulated in terms of a graph optimization problem and belongs to NP-hard. The focus of our work is on the development of an Integer Programming model capable to provide good dual bounds for the problem and, hopefully, to prove optimality of some solutions for real-world instances. To this end, we propose an Integer Programming model and present some valid inequalities that can be added to tighten the linear relaxation and used as cutting planes in a branch-and-cut type algorithm. Preliminary computational results on real instances arising from multimedia applications are reported. These results give an indication that, under certain circumstances, it might be reasonable to try to solve the problem exactly via Integer Programming techniques. This is joint work with André Lima, Nahri Moreano and Guido Araújo. Integer Program Reformulation for Robust Branch-and-Cut-and-Price (11:30 - 12:00) Presenter:  Marcus Poggi Since cut and column generation were established as two of the most important techniques in integer programming, researchers have looked for ways of combining them into a robust branch-and-cut-and-price algorithm. Here, ``robust'' means that neither branching nor the addition of cuts should change the structure of the pricing subproblems. In the last few years, several researchers independently noted that cuts expressed in terms of variables from a suitable original formulation could be added to the master problem without disturbing the pricing. This fact is still little known outside the "column generation community" and its consequences on integer programming are just beginning to be explored. This work intends to be a detailed analysis of how to reformulate an integer program in order to build an efficient robust branch-and-cut-and-price. In particular, we propose an alternative master problem that can be quite advantageous in some situations. Another key issue addressed is how to avoid the pitfalls that arise from variable symmetries in the original formulations of many problems. We present extensive computational experiments on the capacitated minimum spanning tree, capacitated vehicle routing, and generalized assignment problems. Remarkable results on benchmark instances from the literature clearly attest the power of combining cut and column generation. This is joint work with Eduardo Uchoa. A Randomized Approximation for the Quality of Service Steiner Tree Problem (12:00 - 12:30) Presenter:  Cristina G. Fernandes The QoS Steiner Tree Problem asks for the most cost-efficient way to multicast multimedia to a heterogeneous collection of users with different consumption rates. We assume that the cost of using a link is not constant but rather depends on the maximum bandwidth routed through the link. Formally, given a graph with costs on the edges, a source vertex, a set of terminal vertices, each one with a bandwidth requirement, the goal is to find a Steiner tree containing the source, and the cheapest assignment of bandwidth to each of its edges so that each source-to-terminal path has bandwidth at least as large as the bandwidth required by the terminal. We present a randomized primal-dual approximation algorithm that achieves a ratio of 4.311 for the problem. This is joint work with Gruia Calinescu.

Combinatorial optimization Time: Tuesday, 16:30 - 18:00 Organizer: Cristina Fernandes and Yoshiko Wakabayashi

Recent advances in cutting plane theory (17:00 - 18:00) Presenter:  Gérard Cornuéjols In this talk, we survey several classical cutting planes for mixed integer programs. In particular, we discuss the relation between split cuts, Gomory mixed integer cuts and intersection cuts. These connections are then used to generate better cutting planes This is joint work with Kent Andersen and Yanjun Li.

Combinatorial optimization Time: Thursday, 14:00 - 16:00 Organizer: Cristina Fernandes and Yoshiko Wakabayashi

Approximation algorithms for packing problems with orthogonal rotations (14:00 - 14:30) Presenter:  Flávio K. Miyazawa We consider packing problems in which orthogonal rotations are allowed. No significant approximation results have appeared in the literature in which orthogonal rotations are considered. We show a technique that leads to approximation algorithms with improved bounds. We consider the strip packing, the two-dimensional bin packing, the three-dimensional strip packing, and the three-dimensional bin packing problems. For these problems we give algorithms with asymptotic performance bounds 1.613, 2.64, 2.76 and 4.89, respectively. To our knowledge, these bounds are the best known for these problems. This is joint work with Yoshiko Wakabayashi. Problem session (14:30 - 15:30) Presenter:  Gérard Cornuéjols

Discrete mathematics Time: Monday, 14:00 - 16:00 Organizer: Manoel Lemos and Sostenes Lins

Two Results on Tilings of Quadriculated Annuli (14:00 - 14:30) Presenter:  Nicolau Corção Saldanha Tilings of a quadriculated annulus A are counted according to volume (in the formal variable q) and flux (in p). The generating function \Phi_A(p,q) is such that, for q = -1, the non-zero roots in p are roots of unity and for q > 0, real negative. Telling Knots Apart: Counting Colorings and Algorithms for Implementing It (14:30 - 15:00) Presenter:  Pedro Lopes Knot diagrams are networks of arcs obtained by projecting knots onto planes and consistently breaking the lines that go under at crossings. If two knot diagrams are related by the so-called Reidemeister moves then the corresponding knots are deformable into each other (and vice versa). The knot quandle of a given knot is presented by regarding arcs as generators and reading specific relations at the crossings; it is a knot invariant since the defining axioms of quandles are modelled on the three Reidemeister moves. This presentation is not very useful on its own. In this way we count homomorphisms from the knot quandles to a fixed quandle in order to tell knots apart. These homomorphisms are the so-called colorings. In this talk we will develop these ideas and explain how to set up algorithms for counting colorings of knots. Permutation Binomials over Finite Fields (15:00 - 15:30) Presenter:  Daniel Panario A polynomial f over a finite field \fq is called a permutation polynomial if the mapping $f \colon \fq \rightarrow \fq permutes the elements of \fq. Many results about permutation polynomials have appeared in the literature since Hermite. In the last 20 years there has been a revival in the interest for permutation polynomials, in part due to their cryptographic applications. For example, the RC6 block cipher uses a permutation polynomial modulo 2^w, where w is the word size of the machine. We give a characterization of permutation polynomials over finite fields \fq based on their coefficients. Using this characterization we provide the form and number of binomial permutations over \fq where q=2p+1 and p is a prime (that is, Sophie Germain primes). This gives a partial answer to the well-known open problem asking the number of binomial permutations over any finite field \fq. We comment on similar results for other finite fields. This is joint work with Ariane Masuda and Steven Wang.

Discrete mathematics Time: Tuesday, 11:00 - 12:30 Organizer: Manoel Lemos and Sóstenes Lins

Recouplings in Gems and PL-Manifold (11:00 - 11:30) Presenter:  Sóstenes Lins A recoupler R is a special pair of edges with the same color in a bipartite n-gem G. The recoupling of R is the interchange of its two edges by a new pair having the same ends and the same color so as to preserve bipartiteness. A recoupling maintains the induced orientable PL-manifold. A {\em blob} in an n-gem is an n-dipole. A blob {\em creation} or {\em cancellation} is the creation/cancellation of the n-dipole and, therefore, maintains the induced PL-manifold. We prove the following result: if G and H are gems with the same number of vertices inducing the same n-manifold, then there is an integer \alpha(G,H) such that G^\alpha and H^\alpha are linked by a finite number of recouplings, where G^\alpha and H^\alpha are respectively G and H with \alpha blobs put in arbitrary places. In consequence, it is enough to establish a bound for \alpha(G,H) in order to produce an algorithm to move from G and H by \alpha blob creations, followed by a finite number of recouplings followed by \alpha blob cancellations. Deciding whether some word antichains are finite (11:30 - 12:00) Presenter:  Arnaldo Mandel We consider antichains of words related to antichains of nonnegative integer vectors. Words are ordered by divisibility, and vectors by componentwise comparison. Fix an alphabet \X on \(n\) letters, and associate to each word \(w\) its Parikh vector \(\pi(w)\) in \(\N^n\), describing the number of occurences of each letter. Given an antichain \(C\subseteq\N^n\), denote by \(\pi^\geq(C)\) the set of words \(w\) such that \(\pi(w)\geq v\) for some \(v\in C\). The antichains we look at are J= the minimal words of \(\pi^\geq(C)\). S= the minimal sorted words of \(\pi^\geq(C)\). We try to find out whether each is finite, or if some reordering the letters renders \(S\) finite. These questions are decidable if \(C\) is given in any reasonable way. If \(C\) is given by a list of members, some of these questions afford good characterizations, and can be answered in polynomial time. One question includes the recognition of a slight generalization of comparability graphs, and is NP-complete. If \(C\) is given by a polyhedral type description, all our questions turn out to be NP-complete. This is a join work with Ed Green and Cristina G. Fernandes Measures of pseudorandomness for finite sequences: minimum and typical values (12:00 - 12:30) Presenter: Carlos Gustavo T. de A. Moreira Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences E_N in {-1,1}^N in order to measure their `level of randomness'. These parameters, the normality measure \cN(E_N) , the well-distribution measure W(E_N) , and the correlation measure C_k(E_N) of order~ k , focus on different combinatorial aspects of~ _N . In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among these parameters and their minimal possible value, (ii) estimated \cN(E_N), W(E_N), and C_k(E_N) for certain explicitly constructed sequences E_N suggested to have a `pseudorandom nature', and (iii) investigated the value of these parameters for genuinely random sequences E_N . In this talk, we report on recent work in the direction of~(iii) above. We shall discuss some results that show that, for typical E_N in {-1,1}^N , both W(E_N) and \cN(E_N) are of order sqrt(N) , while C_k(E_N) is of order \sqrt(N log(N\choose k)) for any given 2 <= k <= N/4. We shall also prove a lower bound for the correlation measure C_k(E_N) for arbitrary sequences E_N , which, in particular, gives that min_{E_N}C_k(E_N)\geq c_k\sqrt N for some c_k>0 for any constant even k . This is joint work with N. Alon (TAU, Tel Aviv), Y. Kohayakawa (USP, São Paulo), C. Mauduit (IML, Luminy), and V. Rödl (Emory, Atlanta).

Discrete mathematics Time: Wednesday, 11:00 - 12:30 Organizer: Manoel Lemos and Sostenes Lins

Quantum Entanglement and Topological Entanglement (11:00 - 11:30) Presenter:  Louis H. Kauffman This talk explores, via the structure of braiding operators, the relationship between entanglement of quantum states and topological measures of entanglement such as linking numbers and knot polynomials. We will discuss the relationship of this theme with issues in quantum computation.

Lattices as Set Systems (11:30 - 12:00) Presenter:  Dwight Duffus We outline two constructions related to the union-closed set system conjecture and motivated by a lattice theory point of view. First, we consider the collection of all lattices with the same set of join irreducible elements, which itself forms a lattice in a natural way. Second, there is a construction that yields all atomic lattices from Boolean ones that leads to an interesting approach to the conjecture. The second part of this is joint work with Bill Sands.

Graph theory I Time: Monday, 14:00 - 16:00 Organizer: Celina Figueiredo

Some developments on Tutte's 3-flow conjecture (14:00 - 14:30) Presenter:  Ricardo Dahab On the total colouring conjecture in powers of cycles (14:30 - 15:00) Presenter:  Christiane Campos Problem session (15:00 - 16:00) Presenter:  Jeremy Spinrad

Graph theory I Time: Tuesday, 16:30 - 18:00 Organizer: Celina Figueiredo

Perfect matching polytope and solid bricks (16:30 - 17:00) Presenter: U.S.R. Murty The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of $G$. Edmonds (1965) showed that a vector $x$ in $\Q^E$ belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x >= 0 (non-negativity), (ii) x(\nabla(v)) = 1, for all v in V (degree constraints) and (iii) x(\nabla(S)) \geq 1, for all odd subsets S of V (odd set constraints). We are interested in the problem of characterizing graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. (It is well-known that bipartite graphs have this property.) The appropriate context for studying this problem is the theory of matching covered graphs. An edge of a graph is admissible if there is some perfect matching of the graph containing that edge. A graph is matching covered if it is connected, has at least two vertices and each of its edges is admissible. A cut C of a matching covered graph G is a tight cut if |M \cap C| = 1 for every perfect matching M of G, and is a separating cut of G if each of the two graphs obtained by shrinking a shore of G to a single vertex is also matching covered. Every tight cut is also a separating cut, but the converse is not true. A non-bipartite matching covered graph is a brick if it has no nontrivial tight cuts and is a solid brick if it has no nontrivial separating cuts. We shall show that the above-mentioned problem may be reduced to one of recognizing solid bricks. The complexity status of this problem is unknown. This is joint work with Marcelo de Carvalho and Cláudio Lucchesi. Independent spanning trees in 4-connected graphs (17:00 - 17:30) Presenter:  Orlando Lee The k-behaviour of iterated cliques graphs (17:30 - 18:00) Presenter:  Aurora Morgana

Graph theory I Time: Thurday, 16:30 - 18:00 Organizer: Celina Figueiredo

On Clique-inverse graphs of Kp-free graphs (16:30 - 17:00) Presenter: Claudia Linhares Some properties of maximal generating trees for the clique weigthed graphs of Chordal graphs (17:00 - 17:30) Presenter: Silvia Tondato Chordal Graph Extensions (17:30 - 18:00) Presenter:  Loana Tito Nogueira

Graph theory II Time: Tuesday, 14:00 - 16:00 Organizer: Cláudio Lucchesi

On (p,q,s)-Helly hypergraphs (14:00 - 14:30) Presenter: Fabio Protti In this work, we investigate a generalization of the Helly property proposed by Voloshin. Let p \geq 1 , q \geq 0 and s \geq 0 . A hypergraph \hy is {\em (p,q) -intersecting} when every partial hypergraph \hy' \subseteq \hy formed by p or less hyperedges has intersection of cardinality at least q . A hypergraph \hy is {\em (p,q,s) -Helly} when every partial (p,q) -intersecting hypergraph \hy' \subseteq \hy has intersection of cardinality at least s . (According to this terminology, the usual Helly hypergraphs correspond to the case p=2, q=s=1 .) It is clear that recognizing (p,q) -intersecting hypergraphs can be done in polynomial time for fixed p . When p is not fixed, we show that this problem becomes Co-NP-complete. We present a structural characterization for (p,q,s) -Helly hypergraphs. The case q=s leads to a particular characterization in terms of a special bipartite graph. For fixed p,q , the above characterizations lead to a polynomial-time recognition algorithm. When p is not fixed, we show that deciding whether a hypergraph \hy is (p,q,q) -Helly is NP-hard. We conclude by extending the definition of {\em Helly number} in three possible ways. This is joint work with Mitre C. Dourado and Jayme L. Szwarcfiter. On balanced graphs and some subclasses (14:30 - 15:00) Presenter: Minchih Lin We propose to call a graph balanced if its clique matrix is balanced This definition is motivated by the class of balanced hypergraphs, introduced by Berge in the seventies Several facts can be easily deduced about these graphs: they are perfect and clique-perfect; their number of cliques is bounded polynomially; they form a subclass of hereditary clique-Helly graphs and can be recognized in polynomial time Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved Using properties of domination we define four subclasses of balanced graphs Two of them are characterized by 0-1 matrices and recognized polynomially Finally, we analyze the behavior of balanced graphs and these four subclasses under the clique graph operator. Problem session (15:00 - 16:00) Presenter:  Jayme Szwarcfiter

Graph theory II Time: Thurday, 11:00 - 12:30 Organizer: Cláudio Lucchesi

Ear Decompositions and Conformal Minors of Matching Covered Graphs (11:00 - 11:30) Presenter: U.S.R. Murty A single ear of a graph G is a path P of odd length whose internal vertices, if any, have degree two in G . A double ear is a pair of vertex-disjoint single ears. An \emph{ear} is either a single or double ear. If R is an ear of a graph G , the graph obtained from G by deleting all edges and internal vertices of the constituent paths of R is denoted by G-R and is said to be obtained by removing R from G . An ear R of a matching covered graph G is removable if G-R is matching covered. An \emph{ear decomposition} of a matching covered graph G is a sequence G_1,G_2,\ldots,G_r of matching covered subgraphs of G such that (i) G_1 = K_2 , (ii) G_r = G , and (iii) for 1 \leq i \leq r-1 , G_i is obtained from G_{i+1} by removing a removable ear from it. Lovász and Plummer have shown that every matching covered graph has an ear decomposition. (Every bipartite graph has an ear decomposition which involves the removal of single ears only. An ear decompositions of a non-bipartite matching covered graph requires the removal of at least one double ear.) For each graph G_i in an ear decomposition G_1,G_2,\ldots,G_r , the graph G-V(G_i) has a perfect matching and, conversely, given any matching covered subgraph H of G such that G-V(H) has a perfect matching, there is an ear decomposition G_1,G_2,\ldots,G_r of G such that H = G_i for some i . The notions of a conformal subgraph and conformal minor are motivated by this observation. A subgraph H of a matching covered graph G is a conformal subgraph of G if (i) H is matching covered and {\em (ii)} G-V(H) has a perfect matching. A matching covered graph H is a conformal minor of G if some even subdivision of H is isomorphic to a conformal subgraph of G . If H is a conformal minor of G , we shall say that G has an H-minor and if H is not a conformal minor of G , then G is H -free. This talk is an introduction to the theory of conformal minors of matching covered graphs. We shall comment in particular on two problems. Lovász showed that every non-bipartite matching covered graph has either K_4 -minor or a \bar{C_6}-minor. Solid bricks are \bar{C_6} -free. We have shown that every nonsolid brick has, as a conformal minor, either \bar{C_6}, the Petersen graph or one of the two graphs we denote by R_8 and R_{10}. The problems of characterizing K_4-free and \bar{C_6}-free graphs are very much open. An orientation \vec{G} of a matching covered graph G is called a \emph{Pfaffian orientation} of G if, for every conformal circuit C of G , the number of edges of C whose directions in \vec{G} agree with any given sense of orientation of C is odd. (In this case, the determinant of the adjacency matrix of \vec{G} is the square of the number of perfect matchings of G .) The complete bipartite graph K_{3,3} has no Pfaffian orientation. Little showed that a bipartite matching covered graph G has a Pfaffian orientation if and only if G is K_{3,3}-free. One of the deepest results in this theory is the characterization of braces that are K_{3,3}-free (due to Robertson, Seymour and Thomas, and McCuaig). This is joint work with Marcelo de Carvalho and Cláudio Lucchesi. List Partition Problem for Graphs (11:30 - 12:00) Presenter: Elaine Eschen The k-partition problem is: Given a graph G and a positive integer k, partition the vertices of G into at most k parts A1 , A2 , ... , Ak, where it may be specified that Ai induce a stable set, a clique, or an arbitrary subgraph, and pairs Ai, Aj (i not equal to j) be completely non-adjacent, completely adjacent, or arbitrarily adjacent. The list k-partition problem generalizes the k-partition problem by specifying for each vertex x a list L(x) of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list k-partition problems: e.g. 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete. This is joint work with K. Cameron, C.T. Hoang, and R. Sritharan. The homogeneous set sandwich problem (12:00 - 12:30) Presenter:  Vinicius Gusmão A homogeneous set is a non-trivial module of a graph, i.e.~a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G_1(V,E_1),G_2(V,E_2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph G_S(V,E_S), E_1 \subseteq E_S \subseteq E_2, which has a homogeneous set. Two years ago, Tang \textit{et al.} proposed an interesting O(\triangle _1 \cdot n^2) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm and present a new deterministic algorithm for the Homogeneous Set Sandwich Problem, whose O(m_1 \overline{m_2}) time complexity becomes its current upper bound.

Graph theory II Time: Friday, 9:30 - 11:00 Organizer: Cláudio Lucchesi

Improving a Minimal Fill Algorithm (9:30 - 10:00) Presenter:  Jeremy Spinrad This talk reduces the time bound for computing a minimal fill in a dense graph. We use matrix multiplication to reduce the running time whil computing the same ordering of vertices as Tarjan's Lex-M algorithm for solving the problem. As a consequence, we get faster algorithms for decomposing graphs using clique cutsets.

Probabilistic combinatorics Time: Monday, 16:30 - 18:00 Organizer: Yoshiharu Kohayakawa

List-coloring when \chi is near n (16:30 - 17:00) Presenter:  Bruce Reed On the connected domination number (17:00 - 17:30) Presenter:  Martín Matamala A set of vertices X of a graph G is a dominating set if each vertex not in X has a neighbor in X. The domination number of a graph G, denoted \gamma(G), is the smallest integer m such that there exists a dominating set X of G of size m. A dominating set X such that the graph induced by X is connected is called a dominating connected set. The connected domination number, \gamma_c(G), is defined similarly. In this note we use probabilistic methods to improve the upper bound given by Caro, West and Yuster (SIAM J. Disc. Methods 2000) for \gamma_c(G) in terms of the size of G and its minimum degree.

Probabilistic combinatorics Time: Thursday, 11:00 - 12:30 Organizer: Yoshiharu Kohayakawa

A theory of computing symposia (11:00 - 11:30) Presenter:  Prabhakar Raghavan We consider the problem of scheduling a conference to achieve the benefits in time-compression of parallel sessions, but without the associated high degree of conflict between talks. We describe a randomized construction meetings these goals that we analyze based on an expansion property of an associated graph. We also give algorithms for attendees scheduling their time within such a conference as well as algorithms for verifying a proposed conference schedule. Expected length of the longest common subsequence for words over large alphabets (11:30 - 12:30) Presenter:  Marcos Kiwi Consider the length L of the longest common subsequence (LCS) of two randomly uniformly and independently chosen n character words over a k--ary alphabet. Subadditivity arguments yield that {\mathbb E}(L)/n converges to a constant \gamma_k. Under suitable assumptions on k we settle a conjecture of Sankoff and Mainville from the early 80's claiming that \gamma_k\sqrt{k}\to 2 when n\to\infty. Our work elicits a speculated upon connection between several probabilistic models of sequence comparison and the behavior of the celebrated longest increasing sequence (LIS) problem (also referred too as Ulam's problem). The talk will survey results on both the LCS and LIS problem, place them under a common framework, and focus on the exact asymptotic results that can be derived. Several natural questions that arise from stating such framework will be discussed. This is joint work with Martin Loebl [Charles U.] and Ji\v{r}\'{\i} Matou\v{s}ek [Charles U.].

Probabilistic combinatorics Time: Friday, 9:30 - 11:00 Organizer: Yoshiharu Kohayakawa

On packing Hamilton Cycles in \epsilon-regular Graphs (9:30 - 10:00) Presenter:  Alan Frieze A graph G=(V,E) on n vertices is (\alpha,\epsilon)-regular if its minimal degree is at least \alpha n, and for every pair of disjoint subsets S, T\subset V of cardinalities at least \epsilon n, the number of edges e(S,T) between S and T satisfies: \left|{e(S,T)\over|S||T|}-\alpha\right|\leq\epsilon. We prove that if \alpha\gg\epsilon>0 are constants, then every (\alpha,\epsilon)-regular graph on n vertices contains a family of (\alpha/2-O(\epsilon))n edge-disjoint Hamilton cycles. As a consequence we derive that for every constant 0<p<1, with high probability in the random graph G(n,p), almost all edges can be packed into edge-disjoint Hamilton cycles. A similar result is proven for the directed case. Convergence times and decay of the return probability for random walks with random rates in Z^d} (10:00 - 10:30) Presenter:  Luiz Renato Fontes We consider symmetric random walks in the d-dimensional torus whose rates come from a family of i.i.d.~random variables with a polynomial tail at the origin, and derive estimates for times of convergence to equilibrium as a function of the volume which are sharp in log scale. We also consider the decay of the return probability in infinite volume and obtain sharp estimates in the annealed case. Spectral techniques are key to all the derivations. This is joint work with Pierre Mathieu. p_c({\cal G}) for the frog model is not a monotonic function of {\cal G} (10:30 - 11:00) Presenter:  Fábio Prates Machado We show that p_c({\cal G}), the critical probability for the frog model on a graph {\cal G}, is not a monotonic function. This answers a question presented in Alves {\it et al.}. The non-monotonicity is an unexpected fact as the frog model is a percolation model. The frog model is a discrete time particle system on graphs, known as frog model with death. In this model particles move as a discrete time independent simple symmetric random walks (SSRWs) on the vertices of a graph {\cal G} dying, after a geometrically distributed random lifetime. Initially there is an independent random number of particles at each site of {\cal G}. A site of {\cal G} is singled out and called its root. All particles are inactive at time zero, except for those that are placed at the root. At each instant of time, each active particle may die with probability (1-p). Once an active particle survives, it jumps - along edges - on one of its nearest neighbors sites, chosen with uniform probability, performing a SSRW on the vertices of {\cal G}. Up to the time it dies, it activates all inactive particles it hits along its way. From the moment they are activated on, every such particle starts to walk, performing exactly the same dynamics, independent of everything else. This is joint work with L.R.Fontes and A. Sarkar.