# Sóstenes Lins

Sóstenes Luiz Soares Lins (Recife, 13 de abril de 1952) é um matemático brasileiro. Mestre pela Universidade Federal de Pernambuco e doutor (PhD) pela University of Waterloo. Pesquisador Senior 1A do CNPq. Membro da Academia Brasileira de Ciências.

## Biografia

Nascido em Recife, Pernambuco, no dia 13 de abril de 1952, Sóstenes Luiz Soares Lins cursou o primário no Instituto Capibaribe (1957/1958) e no Instituto Recife (1958/1962). O ginasial e o científico foram feitos no Colégio Marista do Recife (1963/1969). Foi aprovado em quinto lugar entre mais de 1000 candidatos no vestibular em 1970 para Engenharia Elétrica. Cursou dois anos e se transferiu para o curso de Matemática da Universidade Federal de Pernambuco, em março de 1972. Terminou o Bacharelado em Matemática no final deste mesmo ano. Iniciou o Mestrado em Matemática em janeiro de 1973 e concluiu em agosto de 1974, tendo o Professor José Morgado como orientador. Iniciou carreira docente na UFPE logo após prestar concurso público para Professor Adjunto, em setembro de 1974. Desta data até o início do curso de PhD, em junho de 1976, ministrou aulas e travou conhecimento com a subárea de Combinatória, até então, inteiramente inexplorada no Brasil. Como autodidata publicou um Research Report sobre uso de matróides no começo de 1975. Ganhou uma bolsa de Estudos para cursar o PhD na Universidade de Waterloo, Canadá, no Departamento de Combinatória e Otimização. O curso durou de junho de 1976 até fevereiro de 1980. As suas pesquisas se concentraram no tópico de mergulhos de grafos em superfícies tendo publicado dois artigos antes da defesa da tese. A sua tese de PhD foi elaborada sob a supervisão do Prof. Daniel H. Younger e foi defendida em 29 de fevereiro de 1980. De volta ao Brasil, tem feito pesquisas na área de Topologia Combinatória e Otimização Discreta. Publicou mais de 30 trabalhos e dois livros. Um deles, Temperley-Lieb Recoupling Theory and Invariants of 3-Manifolds, em colaboração com Louis Kauffman, foi publicado como Annals of Mathematical Studies (nº 134), uma prestigiosa série publicada pela Universidade de Princeton em 1994.

## A tese

A Tese de Ph.D. intitulada Graphs of Maps, foi composta por uma Introdução e 5 capítulos.
A Introdução traz uma visão geral do que trata a tese.
A primeira parte do capítulo 1 trata de demonstrar a equivalência entre três modelos para mapas. Na segunda parte deste capítulo é introduzido um novo tipo de dual, chamado phial, para mapas. As duas dualizações geram um conjunto de seis mapas associados a um mapa dado. A teoria é muito bonita e foi publicada mais tarde no Journal of Combinatorial Theory B, em 1982.
No capítulo 2 é estudada uma generalização de grafos planares chamados grafos ricos. Planaridade é um tópico muito especial de Combinatória. Do ponto de vista algorítmico alguns problemas NP-completos são polinomiais quando restritos a grafos planos, por exemplo, o MAX-CUT problem. O problema de grafos não planares é que eles não têm um dual abstrato, como o que é dado pelo mergulho no plano. O importante em grafos planos é que as fronteiras das faces (ou as cofronterias dos vértices do dual) geram o espaço dos circuitos. Um grafo é rico se ele pode ser mergulhado numa superfície de forma que o seu espaço de circuitos seja gerado pelas cofronteiras dos vértice do dual e dos vértices do phial (que correspondem aos zig-zags do mapa). Um zig-zag em um mapa é a sequência maximal de arestas que alternadamente usam a opção mais à direita e mais à esquerda em cada transição. Uma vitória do meu modelo para mapas baseado em grafos cúbicos é que a noção de zig-zag pode ser definida para superfícies não-orientáveis, em que esquerda e direita não fazem sentido.
No capítulo 3 é mostrada uma generalização para o plano projetivo do chamado Gauss Code Problem. É dada uma solução algorítmica completa de quais códigos de Gauss são possíveis de realizar no plano projetivo.
O capítulo 4 trata da minimax projetiva.
O último capítulo faz um apanhado geral do que foi conseguido e de futuras direções para pesquisa.

## Principais Softwares Desenvolvidos

1. LABIRINTOS: Um programa para confecção de placas de circuito impresso de duas faces. Uso intensivo de teoria de grafos e algoritmos combinatórios em geral.
2. ATEXTA: Um programa para alocação de executores a tarefas em situação de horários conflitantes. Usa teoria de matróides e tem aplicações à distribuição de salas e professores às turmas e em problemas de alocação de recursos humanos e computacionais na indústria.
3. HRAZBRA: Um programa para desdobramento de cartões para a loteria esportiva. Trata-se de sistema bastante completo que opera com chaves multiplicativas a três parâmetros. Usando estas ideias, um grupo do Departamento de Matemática da UFPE jogou algumas vezes na Loteria Esportiva e fizemos os 13 pontos uma vez usando o HRAZBRA. Isto ocorreu em 1981, mas infelizmente naquela ocasião houve 38.000 ganhadores.
4. TURBOLOTO: Um programa semelhante ao anterior para a loto. é baseado na subárea da Combinatória que estuda os chamados Sistemas de Steiner, fruto de muita pesquisa corrente. Um subsistema baseado em planos inversivos finitos de ordem até 82 foi desenvolvido sob encomenda e operou em São Paulo.
5. ORDIGRAF: Um sistema para fazer a hierarquização de atividades econômicas. Usa o Teorema de Perron-Frobenius sobre matrizes primitivas e técnicas recursivas para encontrar componentes fortes de grafos dirigidos. Em uso em um empresa de consultoria.
6. CONJUG: Um sistema de programas para minimizar perdas no corte industrial de materiais tais como: papel, chapas e vergalhões de aço, papelão na indústria de embalagens, etc. Está implementada uma versão unidimensional, baseada no método simplex revisado e no problema knapsack como subrotinas. Nesta versão do problema, o ótimo matemático é sempre atingido. Existe também uma implementacão para o caso bidimensional. O software CONJUG é usado até hoje pela Klabin S. A.
7. PIG (Programa Interativo para Gemas): Trata-se de um sistema de programas para auxílio em sua pesquisa básica sobre variedades tridimensionais. Este é um sistema em contínuo desenvolvimento e que conta com mais de 300 páginas de código fonte em Turbo Pascal. Vários estudantes de Mestrado e de Iniciação Científica contribuíram para aprimorar este sistema. Em particular ele foi dirigido para a produção de um catálogo de variedades tridimensionais. Para dar uma ideia da complexidade computacional na formação deste catálogo, na geração das gemas de apenas 28 vértices foram gastos mais de três meses de operação ininterrupta de um PC-AT.
8. DZNTEX: Compilador para facilitar a inclusão de desenhos no Tex. Os desenhos são produzidos com software compatível com auto-cad e o DZNTEX transforma-os em arquivos legíveis pelo Tex.
9. BINGOTIM: Programa para acompanhamento de sorteios tipo BINGO. Examina 2 milhões de cartões em 1,5 segundos. Além disto, neste tempo mínimo faz consulta em disco rígido para saber se a cartela batida está paga. Usa elegantemente teoria dos códigos, mudanças de base de espaços vetoriais sobre corpos finitos e estrutura de dados.
10. WCJO: O novo sistema Conjug passou a se chamar WCJO e foi incorporado pela Klabin Papelão Ondulado S.A. como módulo de otimização em todas as suas fábricas, a partir de julho de 1996.
11. Sistema SAD (Sistema de Apoio a Decisão): Para particionamento ótimo de unidades de coleta de esgotos da cidade do Recife.
12. PalletZoom: Trata-se de um sistema para fornecer composições de paletes para estocagem e transporte. Os Supermercados Bompreço S.A. adquiriram uma cópia do PalletZoom em abril de 1999.
13. WCJB: Desenvolvido em Delphi é um módulo para otimização de bobinas de papel denominado WCJB.
14. EXPEDPLEX: Supervisionou o desenvolvimento do Sistema ExpedPlex para otimização do empacotamento de caixas em paletes e contêiners.
15. s-PLEX: Supervisionou o desenvolvimento do Sistema s-Plex para otimização do corte e laminação de bobinas de aço.
16. NOVO CONJUG: Entre 2003 e 2005 foi desenvolvimento do Novo Sistema Conjug para a Otimização do corte de caixas de papelão ondulado. Encomenda feita pela Klabin S.A.

## Principais Publicações

* Temperley-Lieb recoupling theory and invariants of 3-manifolds. Lins, S., Princeton University Press, 1994.
* Graph-encoded maps, Lins, S., Journal of Combinatorial Theory, Series B 32 (2), 171-181, 1982.
* Graph-encoded 3-manifolds. Lins, S., Mandel, A., Discrete Mathematics 57 (3), 261-284, 1985.
* Gems, Computers, and Attractors for 3-manifolds. Lins, S. World Scientific, 1995.
* An L-approach for packing (l, w)-rectangles into rectangular and L-shaped pieces, Lins, L., Lins, S., Morabito R., Journal of the Operational Research Society 54 (7), 777-789, 2003.
* An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container, Lins, L., Lins, S., Morabito R. European Journal of Operational Research 141 (2), 421-439, 2002.
* A minimax theorem on circuits in projective graphs, Lins, S., Journal of Combinatorial Theory, Series B 30 (3), 253-262 , 1981.
* The Gauss code problem off the plane, Lins, S., Richtfr, B., Shank, H. Aequationes Mathematicae 33 (1), 81-95, 1987.
* Computing Turaev-Viro invariants for 3-manifolds, Kauffman, L.H., Lins, S., Manuscripta Mathematica 72 (1), 81-94, 1991.
* On the fundamental group of 3-gems and a planar class of 3-manifolds, Lins, S., European Journal of Combinatorics 9 (4), 291-305, 1988.
* Graphs of maps, Lins, S., arXiv:math/0305058, 2003.
* Traversing trees and scheduling tasks for duplex corrugator machines, Lins, S., Pesquisa Operacional 9 (1), 40-54, 1989.
* A simple proof of Gagliardi's handle recognition theorem, Lins, S., Discrete Mathematics 57 (3), 253-260, 1985.
* A sequence representation for maps, Lins, S., Discrete Mathematics 30, 249-263, 1980.

## O Projeto GemBlinks/UNIVs

No ano de 2013, deu início ao Projeto GemBlinks/UNIVs que está tendo grande sucesso em divulgar a Matemática, em especial a Topologia. Em 2014 o Shopping Center RioMar, no Recife, abriu suas portas para uma Exposição sobre UNIVs (esculturas em aço de grande beleza artística induzidos por 3-manifolds que descobriu em 2013). Mais de 650 pessoas assinaram o livro de visitantes. Ver fotos aqui. Em Outubro de 2014 o acervo de UNIVs (cerca de 60 peças) foi colocado em uma sala nobre do Espaço Ciência, Olinda-PE, onde uma nova Exposição está sendo preparada e deverá estar aberta ao público em breve.