Bruce Reed, CNRS, Paris VI, and Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo. Tangles and Tree Width: A New Connectivity Measure and Some Consequences.

A graph is a set of vertices and an adjacency relation which indicates which pairs of vertices are joined by an edge. Thus, graph theory is essentially the study of connectivity. How then does one measure the connectivity of a graph?

Measuring the connectivity between two vertices is straightforward. Two vertices are said to be k-connected if there are k internally vertex disjoint paths between them. A classical theorem of Menger states that vertices a and b are k-connected in a graph G precisely if there is no set X of fewer than k vertices such that a and b lie in different components of G − X. Standard alternating paths techniques, allow us to find either k internally vertex disjoint a-b paths or such a set X efficiently.

An appropriate definition of a highly connected graph, or of a highly connected piece of a graph is more difficult. The classical approach is to call a graph k-connected if every pair of its vertices is k-connected. This definition, although natural, does not capture the kind of connectivity that will concern us. It focuses on local properties rather than global ones. To illustrate what we mean, we consider the hexagonal lattice L. Then L has maximum degree three and hence contains no 4-connected subgraph. On the other hand, if X is a set of at most three vertices of L then L − X is either connected or has two components, one of which is a vertex. Similarly, if X is a set of at most k vertices then the largest component of L − X contains all but at most k^{2} of the vertices of L. Thus, no cutset of size k “globally disconnects” L. One of the goals of this paper is to introduce its readers to a connectivity invariant, the bramble number, which measures global connectivity.

Having done so, we will examine those graphs for which this invariant is bounded by a given k. If the bramble number of G is at most two then G is a forest. It turns out that for any k, the graphs with bramble number at most k have a “tree-like” structure. How tree-like depends on the value of k. We will present a precise duality theorem after we have developed the requisite definitions. Now, such tree-like structures are easy to deal with. For example, we will develop efficient algorithms for resolving seemingly difficult (i.e. NP-complete) problems on graphs whose bramble number is bounded. We will also see that many difficult conjectures can be resolved when restricted to such graphs.

We will also examine the structure of graphs with large bramble number. It turns out that if a graph has large bramble number then it must contain a subdivision of a large piece of the hexagonal lattice. This fact allows us to resolve many difficult questions on such graphs.

Combining the two complementary types of results discussed above has proven very fruitful. We will present some of the many results obtained using this technique. We will also discuss an assortment of other results which elucidate the dual notions of brambles and

Typeset by AMS-TEX following the amsabs style

tree-structures. The most important of these is a theorem which states that every graph can be decomposed into a tree structure of pieces each of which corresponds to a maximally connected part of the graph.

Alair Pereira do Lago, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo. On the Structure of the Burnside Semigroups.

For a fixed set of generators A and for n ≥ 1 and m ≥ 1 integers, the free associative semigroup that satisfies the equation x^{n+m} = x^{n} is called a Burnside semigroup. If we allow n = 0 we have a Burnside group and it can be infinite for m large enough.

We present some structural results on the Burnside semigroups.

In order to classify the structure of these semigroups we have to split them in three cases: n = 1, n = 2 and n ≥ 3. Our main interest here is the case n = 2 whose structure was practically unknown until now. We have a fairly complete set of results for the case n = 2 but here we restrict ourselves to the statement of two facts: one old and one new.

It was known that the semigroups are infinite (with infinitely many J -classes) when n ≥ 2 for more than one generator, while the semigroup is finite for m small enough when n = 1. Anyway, there are only finitely many J -classes for n = 1 and any m.

The maximal subgroups of these semigroups are proved to be free Burnside groups satisfying x^{m} = 1 whose set of generators is associated with a special graph. The cardinality of the generating set is the cyclomatic number of this graph. When n ≥ 3 this special graph is a cycle and the maximal subgroups are cyclic groups of order m. We have examples with an arbitrary number of generators both for n = 1 and for n = 2. Hence we might have infinite maximal subgroups for m large enough. Some of these results in the case n = 1 have been known.

Arnaldo Moura, Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13083–970 Campinas. Sistemas Híbridos: Modelagem, Verificação e Ferramentas.

Cenário: É cada vez mais comum a presença de sistemas híbridos, resultantes da integração entre ambientes analógicos e controladores discretos. Frequentemente, tais sistemas são formados por vários módulos distribuídos que devem cooperar para atingir objetivos comuns. Em resposta a esta evolução, surge a necessidade de modelar tais sistemas de modo a permitir a análise e a verificação rigorosas de propriedades do sistema completo. Destes modelos devem resultar ferramentas computacionais (semi-)automáticas que viabilizem a verificação de sistemas de porte razoável.

Modelos: Autômatos híbridos surgiram como um modelo natural para sistemas híbridos. Um autômato híbrido é formado por um autômato finito (clássico) que descreve o controle discreto do sistema. Este autômato finito é equipado com um conjunto de variáveis contínuas, que evoluem segundo leis dinâmicas, e que descrevem a parte analógica do sistema. Cada módulo do sistema é descrito por um autômato híbrido. O sistema distribuído completo é descrito pelo produto destes autômatos, garantindo mecanismos de sincronização entre os componentes. Cada componente já introduz um número infinito de estados no modelo, através das variáveis contínuas. O produto gera, ainda, uma explosão combinatória no número de componentes discretas nos estados do autômato resultante.

Palestra: Nesta palestra, vamos explorar o potencial da modelagem de sistemas integrados através de autômatos híbridos. A noção de autômato híbrido será apresentada. Exemplos típicos serão discutidos. Em seguida, as propriedades do modelo serão exploradas, mostrando quais restrições a parte contínua deve satisfazer para garantir a (semi-)decidabilidade das propriedades básicas necessárias para a verificação do modelo. Nos casos indecidíveis, serão examinadas abordagens aproximativas como alternativas às soluções exatas. Serão mencionadas algumas ferramentas, já implementadas, que realizam verificação (semi-)automática de sistemas híbridos. O grau de sucesso destas ferramentas pode ser aquilatado através dos exemplos práticos onde foram usadas.

Ralf Borndörfer, Konrad-Zuse-Zentrum, Berlin, Germany, Carlos Eduardo Ferreira, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo, and Alexander Martin, Konrad-Zuse-Zentrum, Berlin, Germany. Decomposing Matrices into Blocks.

In this talk we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called bordered block diagonal form. Given some matrix A, we try to assign as many rows as possible to some number β of blocks of size κ such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We attack this matrix decomposition problem from a polyhedral point of view and develop a branch-and-cut algorithm. We present several new classes of valid and facet-defining inequalities, discuss separation algorithms and the success of primal heuristics. Our computational results show that various matrices from the LP- and MIP-libraries Netlib and Miplib can indeed be decomposed into this form.

Celina M. H. de Figueiredo, Instituto de Matemática, Universidade Federal do Rio de Janeiro, Brazil; e-mail: celina@cos.ufrj.br, and Frédéric Maffray, Laboratoire Leibniz - IMAG, France; e-mail: Frederic.Maffray@imag.fr. Optimizing Bull-free Perfect Graphs.

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi [V. Chvátal and N. Sbihi, Bull-free Berge graphs are perfect, Graphs and Combinatorics, 3:127–139, 1987] showed that the Strong Perfect Graph Conjecture holds for bull-free graphs by defining a decomposition operation with respect to homogeneous pairs. Reed and Sbihi [B.A. Reed and N. Sbihi, Recognizing bull-free perfect graphs, Graphs and Combinatorics, 11:171–178, 1995] gave a polynomial-time recognition algorithm for bull-free perfect graphs.

In this talk, we present a polynomial-time algorithm for solving the optimization problems: maximum weighted clique and minimum weighted colouring for bull-free perfect graphs.

Given a bull-free perfect graph with no homogeneous set, our solution considers four cases according to the existence of a hole or of an even antihole in the graph. In case the graph has no hole and no antihole, we have a weakly triangulated graph; solutions for the optimization problems are known in this case. In case the graph has an even hole and no antihole, we defined in [C. M. H de Figueiredo, F. Maffray, and O. Porto, On the structure of bull-free perfect graphs, Graphs and Combinatorics, 13:31–55, 1997] a decomposition which allowed us to exhibit a perfect order in this case. We can further exploit this decomposition to show that we actually have a comparability graph; both comparability and co-comparability graphs are well-studied classes of perfect graphs. In case the graph has an even hole and and even antihole, we show how to use Chvátal’s decomposition with respect to a special homogeneous pair to optimize.

Cristina Gomes Fernandes, Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo. Multicortes em Árvores de Grau Limitado.

O Problema dos Multicortes é o seguinte: dado um grafo G e uma coleção de pares de vértices distintos s_{i}, t_{i} de G, encontrar um conjunto mínimo de arestas de G cuja remoção desconecta cada s_{i} do t_{i} correspondente. Sabe-se que esse problema é NP-difícil mesmo quando restringimos o grafo de entrada a ser uma árvore. Provamos que, para árvores binárias, o problema continua NP-difícil. Para árvores em geral, a melhor razão de aproximação conhecida é dois. Nós apresentamos, para todo ϵ > 0, um algoritmo de aproximação polinomial com razão no máximo 1 + ϵ para árvores de grau limitado. Para o caso particular de árvores binárias, o algoritmo pode ser implementado em tempo linear.

Esse trabalho é conjunto com Gruia Călinescu do Georgia Institute of Technology, EUA.

Gregorio Malajovich, Departamento de Matematica Aplicada, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945 Rio de Janeiro, Brasil. On the Geometry of Graeffe Iteration.

A new version of the Graeffe algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous to renormalization of dynamical systems.

This iteration is called Renormalized Graeffe Iteration. It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm.

If we start with a degree-d polynomial, each renormalized Graeffe iteration costs O(d^{2}) arithmetic operations, with memory O(d).

A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed.

A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000.

(Joint work with Jorge P. Zubelli).

Carlos Gustavo Tamm de Araujo Moreira and Pablo Emanuel, Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina, 110, Jardim Botânico 22460–320 Rio de Janeiro, RJ, Brasil. Um Problema Extremal sobre o Hipercubo e Aplicações a Circuitos Assíncronos.

Investigamos o seguinte problema combinatório extremal, motivado por um problema sobre circuitos assíncronos: estime o menor valor possível de B = B(n) para que exista uma função

F : {0, 1}^{B} → n

tal que:

(i) Para quaisquer x < n, y < n, existem m, n em {0, 1}^{B} com F (m) = x, F (n) = y, e dist(m, n) = 1, ou seja, m e n diferem em apenas um bit.

(ii) Para qualquer x < n, a imagem inversa de x por F é conexa, i.e., dados m, n com F (m) = F (n) = x, existem m = l(0), …, l(k) = n com dist(l(i), l(i + 1)) = 1 e F (l(i)) = x, para 0 ≤ i < l.

Provamos que

2 log_{2} n − log_{2} log_{2} n − 1 < B(n) < 2 log_{2} n − log_{2} log_{2} n + 2

para todo n natural. A estimativa superior anterior era 2 log_{2} n − 1. Descreveremos brevemente o problema computacional que motiva este problema combinatório.

Jayme L. Szwacfiter, Instituto de Matemática, COPPE - Programa de Engenharia de Sistemas e Computação, Núcleo de Computação Eletrônica, UFRJ, and Chao-Ping I. Yan, Instituto de Matemática, Universidade Federal do Rio de Janeiro. O Grafo de Interseção de Caminhos em Estrelas Longas.

Uma estrela longa é uma grafo formado por um conjunto de caminhos induzidos, que se interceptam em exatamente um vértice. Apresentamos uma caracterização do grafo de interseção de caminhos em uma estrela longa. Esta caracterização conduz a um algoritmo de tempo polinomial para reconhecer grafos desta classe. No caso do reconhecimento ser positivo, o algoritmo, adicionalmente, contrói a estrela correspondente.

Katia Guimarães, Departamento de Informática, Universidade Federal de Pernambuco, Estrutura em Classes de Aproximação.

A noção de problemas aproximáveis e algoritmos de aproxi- mação foi introduzida formalmente por Johnson, em 1974, que sugeriu a classificação de problemas de acordo com suas propriedades de aproximação. Embora as versões de decisão dos problemas de otimização NP-completos sejam redutíveis uma à outra em tempo polinomial, tais reduções quando transplantadas para a perspectiva de otimização, nem sempre preservam a função objetivo, e raramente preservam a qualidade das soluções obtidas. Torna-se necessário, portanto, usar reduções mais restritas, que além de mapear instâncias do problema A em instâncias de B, também garantam que boas soluções para B, gerem boas soluções para A. Nesta palestra discutiremos um conjunto de reduções e suas propriedades. Iniciaremos com a tradicional L-redução de Papadimitriou & Yannakakis, identificando alguns problemas estruturais; discutiremos a E-redução, que é mais robusta, mas também apresenta problemas, e por fim discutiremos a AP -redução, recentemente proposta por Crecenzi, Kann, Silvestri & Trevisan, e alguns dos resultados estruturais que o seu uso permitiu provar.

Lev Birbrair, Universidade Federal do Ceará. Local Bilipschitz Classification of 2-dimensional Semialgebraic Sets.

In the paper we present a combinatorial invariant for the problem of local bilipschitz classification of 2-dimensional semialgebraic or subanalytic sets so-called Hölder Complex. The invariant is complete in the following sense: two germs of 2-dimensional closed semialgebraic sets are bilipschitz equivalent if and only if the corresponding Hölder Complexes are combinatorially equivalent.

Manoel Lemos, Departamento de Matemática, Universidade Federal de Pernambuco, Recife. Removendo Ciclos em Grafos.

Para um grafo G, o mínimo dos graus dos seus vértices é denotado por

δ(G) = min{d(v) : v ∈ V (G)}.

Dirac foi o primeiro a impor uma condição em δ(G) para garantir a existência de ciclos longos em grafos simples, mostrando os seguintes resultados: (a) G tem ciclo de comprimento pelo menos k + 1 quando δ(G) ≥ k + 1; (b) no caso em que G for 2conexo, existe ciclo com pelo menos 2k arestas; (c) quando δ(G) ≥ |V (G)|/2, então G é hamiltoniano.

Já Mader estava interessado em garantir a existência de um ciclo em um grafo simples n-conexo cuja remoção de suas arestas mantivesse o grafo n-conexo. Conseguiu mostrar isto no caso em que δ(G) ≥ n + 2. Este teorema responde uma questão levantada por Hobbs, no caso em que o grafo é simples: “quando δ(G) ≥ 4 e G é 2-conexo, então G possui um ciclo cuja remoção o deixa 2-conexo?”

Infelizmente esta questão não é verdadeira, como demonstrou Robertson.

Jackson generalzou conjuntamente os resultados de Dirac e Mader, demonstrando que todo grafo simples 2-conexo tal que δ(G) ≥ k possui um ciclo C com comprimento pelo menos k − 1 tal que G\E(C) é 2-conexo.

Iremos discutir generalizações do teorema de Jackson nesta mini-palestra.

João Meidanis, Institute of Computing, University of Campinas, Caixa Postal 6176, 13083–970 Campinas, Brazil, Maria Emilia M. T. Waltery, Department of Computer Science, University of Brasilia, Brazil, and Institute of Computing, University of Campinas, Brazil, and Zanoni Diasz, Institute of Computing, University of Campinas, Brazil. Reversal Distance of Signed Circular Chromosomes.

We study the problem of comparing two circular chromosomes, evolved from a common ancestor by reversals, given the order of the corresponding genes and their orientations. Determining the minimum number of reversals between the chromosomes is equivalent to look for the minimum number of reversals that transforms a circular sequence of signed integer numbers, defined in an appropriate manner, into another, where a reversal acts on a subsequence, reversing its order and flipping the signs. We carefully formalize the concepts of circular chromosome and circular reversal, and show that this problem is essentially equivalent to the analogous problem on linear chromo- somes. As a consequence we derive polynomial time algorithms based on this observation. We also compute the reversal diameter for signed chromosomes, both linear and circular.

Marcelo H. de Carvalho, Universidade Federal de Mato Grosso do Sul, and Cláudio L. Lucchesi, Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13083–970 Campinas. Decomposição Ótima em Orelhas para Grafos Matching Covered.

Grafos matching covered são grafos conexos em que toda aresta pertence a um emparelhamento perfeito. O estudo desta classe de grafos é motivado pelo fato de que todo grafo cúbico sem aresta de corte é matching covered. Assim, o estudo desta classe de grafos pode nos dar alguma luz para a solução da Conjectura de Tutte que generaliza o problema das quatro cores.

Existem dois procedimentos de decomposição de grafos matching covered: a decomposição em cortes justos e a decomposição em orelhas. Para uma decomposição em orelhas podem ser usadas orelhas simples ou duplas. Uma decomposição em orelhas é ótima se usa o número mínimo de orelhas duplas. Nesta palestra apresentaremos os principais resultados sobre decomposição ótima em orelhas para grafos matching covered.

José Plínio de Oliveira Santos, Departamento de Matemática Aplicada, Instituto de Matemática, Estatística e Computação Científica, Campinas, Brasil. Famílias de Identidades em Partições.

Em um trabalho de 1961, B. Gordon apresentou uma família infinita de identidades em partições que incluem, como casos especiais, as duas famosas identidades de Rogers– Ramanujan.

Recentemente um teorema análogo ao de Gordon foi demonstrado por G.E. Andrews e J.P.O. Santos.

No presente trabalho, feito em colaboração com P. Mondek, apresentamos uma nova família infinita de identidades fazendo uso de um q-análogo de F.H. Jackson para uma fórmula de Dixon. Esta fórmula, por nós utilizada, já havia servido para a prova de dois importantes teoremas dados por J.J. Sylvester e H. Göllnitz.