Grafos-distância sobre os inteiros

Yoshiharu Kohayakawa

IME-USP

Sexta-feira, 19 de setembro de 2003, 14:00

Sala 266, Bloco A, IME-USP

Resumo:

Consideraremos certos problemas extremais sobre representações de grafos como grafos-distância sobre os inteiros. Dado um grafo G=(V,E), desejamos encontrar uma injeção \phi : V -> Z+={1,2,...} e um subconjunto D de Z+ de forma que {u,v} \in E se e só se |\phi(u)-\phi(v)| \in D.

Seja s(n) o menor inteiro N tal que qualquer grafo G com n vértices admite uma representação (\phiG,DG) tal que \phiG(v) <= N para todo v em V(G). Mostraremos que s(n)=(1+o(1))n2 conforme n->\infty. É um tanto surpreendente que a cota inferior s(n) >= (1+o(1))n2 segue mesmo considerando apenas grafos r-regulares, desde que r=r(n) >> log n.

Dado um grafo G=(V,E), seja De(G) a menor cardinalidade possível de um conjunto D para o qual existe algum \phi:V->Z+ tal que (\phi,D) representa G. Mostraremos que, para quase todo grafo G com n vértices, temos

De(G) >= 1/2{n\choose2}-(1+o(1))n3/2(log n)1/2,
enquanto que, para algum grafo G com n vértices, temos
De(G) >= {n\choose2}-n3/2(log n)1/2+o(1).
Outros problemas extremais de natureza similar serão mencionados.

Este é um trabalho conjunto com M. Ferrara e V. Rödl (Atlanta).

Last modified: Thu Sep 18 11:35:52 BRT 2003