Seminários do primeiro semestre de 2005

Herança de uniformidade e aplicações (Sala 252-A, de 24/06/2005 14:00 até 24/06/2005 15:00) por cris

Consideraremos grafos `uniformes', isto é, grafos cujas arestas são `bem distribuídas'. Discutiremos resultados que, a grosso modo, dizem que `boa distribuição' para conjuntos de tamanho moderado implica `boa distribuição' para conjuntos pequenos típicos. Discutiremos duas aplicações deste resultado: consideraremos um problema de enumeração assintótica de grafos e um problema da teoria combinatória dos números.

The cycle space of an infinite, locally finite graph (Sala Gilioli - Bloco A, de 13/05/2005 14:00 até 13/05/2005 15:00) por cris

A number of well-known theorems concerning the cycle space of a finite graph (such as MacLane's planarity criterion or Tutte's generating theorem) either fail for locally finite graphs, or have to be weakened considerably. This is not the case when infinite cycles are allowed. These (more precisely, their closures) are homeomorphic images of the unit circle in the graph compactified by its ends. In the resulting cycle space, all the basic properties of a finite cycle, as well as the theorems mentioned above, have almost verbatim extensions. The talk is based on work by Diestel, Kühn, and Bruhn, and on the PhD work of the speaker, which is partly joint work with Bruhn and Diestel.

Empacotamento utilizando técnicas de programação não-linear (Sala 252 - A, de 03/06/2005 14:00 até 03/06/2005 15:00) por cris

O problema de empacotar um conjunto de itens num objeto aparece em várias situações, tais como carregamento de paletes, carregamento de containeres e corte de peças na indústria textil. Há uma variedade enorme de problemas desse tipo, dependendo das características dos itens e do objeto. Os itens que deseja-se empacotar podem ser idênticos ou distintos, e a quantidade de cada um deles pode ser limitada ou ilimitada. Os itens podem ser círculos, retângulos, polígonos regulares, etc. O objeto também pode ser um círculo, um retângulo ou uma região convexa arbitrária. Tambám pode haver restrições de ortogonalidade entre os itens ou alguma outra restrição no padrão do empacotamento. Finalmente, o objetivo pode ser maximizar a área ocupada de um objeto fixo (empacotando a "maior quantidade" possível de itens) ou minimizar a área de um objeto no qual um conjunto fixo de itens possa ser empacotado. Neste seminário apresentaremos nossa expêriencia ao tentar resolver esse tipo de problemas utilizando técnicas de programação não-linear.

Formulações para o problema de Steiner com grupos (Sala 252 - A do IME-USP, de 20/05/2005 14:00 até 20/05/2005 15:00) por cris

Dado um grafo G=(V,E), uma função c : E -> R+ e um conjunto \cal{R} de subconjuntos de V, chamados grupos, o objetivo é encontrar uma árvore T de custo mínimo que contenha pelo menos um vértice de cada grupo. Vamos mostrar nesta palestra um estudo de um poliedro associado ao problema, e algumas formulações inteiras para o mesmo. Este trabalho está sendo feito em conjunto com Fernando Mario de Oliveira Filho.

Conservation and rearrangements in genomes (Anfiteatro Jacy Monteiro, de 06/05/2005 15:20 até 06/05/2005 16:20) por cris

Conserved segments in genomes are groups of genes situated on a same chromosomic region in several species, which indicates that they stayed grouped during evolution. Large chromosomic rearrangements, like reversals, may change the organisation of the genes, so determine the conserved segments. Though rearrangements and conserved segments are closely linked, it is only recently that some studies began to mix the principles of detection of conserved segments, and reconstitution of possible scenarios of reversals. Possible incompatibility of the results have several times been remarked. I will discuss about the construction of a good model that would include both topics. I will present a first step in that direction, answering a question asked by Bérard, Bergeron and Chauve on the existence of a polynomial algorithm that would decide if there exists a minimum scenario of reversals that transforms a genome into another while preserving the common co-localised groups of genes.

Some results on the minimum phylogenetic supergraph problem (Sala 252-A do IME-USP, de 08/04/2005 14:00 até 08/04/2005 15:00) por cris

We consider the problem of computing a directed supergraph of a group of trees or forests on a common set of leaves. This problem arises in phylogenetic reconstruction when trying to handle hybridization phenomena. In particular, trees and graphs we consider have some constraints: nodes have degree $1$ or $3$ and there is a root $r$ with a directed path to each other node. The question is, given a group of trees, to compute the supergraph of minimum size, where ``size'' is the number of recombination nodes, i.e. nodes with indegree $2$. We first compare the minimum supergraph approach with two other known approaches to hybridization, namely the SPR distance between trees, and the maximum agreement forest. Then we prove that the complexity of this minimization problem is independent of the number of roots in the forests: the approximation ratio for finding a supergraph of a group of forests with $p$ leaves is at worst $10$ times bigger than the approximation ratio for finding a supergraph of a group of trees (where $p=1$). Finally, we prove that the minimum supergraph problem is MAX-SNP-complete for a class of very simple graphs (those consisting of forests with only $2$ leaves and only one leaf per connected component).

Transposições e ordenação por blocos (Sala 252-A do IME-USP, de 01/04/2005 14:00 até 01/04/2005 15:00) por cris

Apresentaremos alguns resultados recentes sobre o problema de calcular a distância de transposição entre duas seqüências e uma variante deste, conhecida como problema da ordenação por blocos (block sorting).

Ramsey properties of random hypergraphs (Anfiteatro Jacy Monteiro, de 06/05/2005 14:00 até 06/05/2005 15:00) por cris

We consider the upper bound for the threshold problem of the {\it Ramsey property} in the random $k$-uniform hypergraph $G^{(k)}(n,p)$. Given some fixed hypergraph $F^{(k)}$ we say some hypergraph $H^{(k)}$ has the Ramsey property for $F^{(k)}$ for $r$ colours if every $r$-colouring of the edges of $H^{(k)}$ yields a monochromatic copy of $F^{(k)}$. In the mid-nineties R\"odl and Ruci\'nski solved the corresponding threshold problem for arbitrary graphs $F^{(2)}$ and they found an upper bound for the complete $3$-uniform hypergraph on $4$ vertices. In collaboration with these authors we proved the upper bound of the conjectured threshold for $k$-uniform, $k$-partite hypergraphs $F^{(k)}$. We also simpliefied the proof in the graph case for two-colourings, by avoiding an application of Szemer\'edi's regularity lemma, which was one of the essential tools in the original proof.

Ramsey results for 3-colorings and odd cycles (Sala 252-A do IME-USP, de 18/03/2005 14:00 até 18/03/2005 15:00) por cris

For graphs $G_1,\ldots, G_k$, the Ramsey number $R(G_1,\ldots, G_k)$ is the minimum integer $N$ satisfying that for any $k$-coloring of edges of the complete graph $K_N$ there exists a color $i$ for which the corresponding color class contains $G_i$ as a subgraph. In 1973, Bondy and Erd\H{o}s conjectured that if $n$ is odd, then $R(C_n, C_n, C_n)=4n-3$. We prove this conjecture for large $n$. (Joint work with Y. Kohayakawa and M. Simonovits.)

Online Ramsey Games on Random Graphs (Sala Gilioli do IME-USP, de 11/03/2005 15:20 até 11/03/2005 16:20) por cris

We study the following simple, one player game. The board is a graph with $n$ vertices, which initially contains no edges. These are presented one by one to the player in an order chosen uniformly at random among all permutations. One of two colors, red or blue, has to be assigned to each edge immediately. The player's object is to color as many edges as possible without creating a monochromatic copy of some fixed graph $F$. As soon as the first monochromatic copy of $F$ is closed, the game ends. We call this the $F$-avoidance game and refer to the number of properly colored edges as its \emph{length}. We prove a threshold phenomenon for the expected duration of this game for all graphs $F$ in a large family, which includes cliques and cycles of fixed size $\ell$. We show that for each graph $F$, there is a function $N_0(n)$ such that the player can asymptotically almost surely survive up to $N(n) \ll N_0(n)$ by playing greedily, but that there is no strategy such that the game would last for $N(n) \gg N_0(n)$ edges.

An Online Spanning Tree Problem in Randomly Weighted Graphs (Sala Gilioli do IME-USP, de 11/03/2005 14:00 até 11/03/2005 15:00) por cris

In this talk we consider an online variant of the minimum spanning tree problem in randomly weighted graphs. We assume that the input graph is complete and the edge weights are uniform distributed over [0,1]. An algorithm receives the edges one by one and has to decide immediately whether to include the current edge into the spanning tree or to reject it. The corresponding edge sequence is determined by some adversary. We propose an algorithm which achieves E[ALG]/E[OPT] = O(1) and E[ALG/OPT] = O(1) against a fair adaptive adversary, i.e., an adversary which determines the edge order online and is fair in a sense that he does not know more about the edge weights than the algorithm. Furthermore, we prove that no online algorithm performs better than E[ALG]/E[OPT] = \Omega(\log n) if the adversary knows the edge weights in advance. This lower bound is tight, since there is an algorithm which yields E[ALG]/E[OPT] = O(\log n) against the strongest imaginable adversary.

Fair Multi-Party Computation (Sala Gilioli do IME-USP, de 08/03/2005 11:00 até 08/03/2005 12:00) por cris

Secure multi-party computation (MPC) has been one of the most fundamental problems in cryptography. At a high level, the problem is concerned with n parties, each holding a private input, that want to compute a function of those inputs so that each party learns its own output, but no other information is revealed, even in the presence of malicious parties that may deviate arbitrarily from the protocol. Instances of MPC include password authentication, distributed auctions, on-line bidding, etc. MPC is called ``fair'' if either all the parties learn the outuput of the function being computed, or nobody does. A well-known result due to [Cleve'86] shows that fair MPC is impossible when a majority of the parties are corrupted (which in particular applies to the case of two parties and one corruption). In this talk, we show how to circumvent this impossibility result, and present fair MPC constructions that tolerate up to (n-1) corruptions. The constructions make use of some recent results in timed-release cryptography. The talk will be high-level and self-contained.