A Iniciação Científica é uma atividade de formação complementar e não obrigatória. Por isso, eu imponho as seguintes exigências para orientação de Iniciação Científica de forma a garantir a qualidade do resultado final.

• Eu não oriento alunos que trabalhem ou façam estágio. Ao acordarmos uma orientação de Iniciação Científica, você estará comprometendo-se a dedicar-se exclusivamente à universidade durante toda a duração do projeto (12 meses). É possível receber uma bolsa (remuneração) durante a realização da IC, mas isso não é garantido. Veja a Seção Bolsas.
• A IC requer 20 horas de dedicação semanal, das quais:
  • 1h ou 2h horas serão gastas em uma reunião semanal/quinzenal comigo.
  • Ao menos 8h (duas tardes) deverão ser gastas no TOCA (Laboratório de Teoria da computação, Otimização, Combinatória e Algoritmos)

No momento não estou aceitando alunos de PDPD

A bolsa de Iniciação Científica e PDPD tem duração de 12 meses; a de mestrado, 24 meses; e a de doutorado, 48 meses.

O valor da bolsa depende da agência para o qual o pedido de financiamento foi realizado. As principais financiadoras são a UFABC (atráves do CNPQ e Capes) e a FAPESP (mais sobre a FAPESP a seguir). Os valores em 07/04/2023 são

A bolsa mais prestigiosa que você pode obter é a bolsa fornecida pela Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP). Essa bolsa é fornecida apenas para os melhores estudantes e, com frequência, ser um bom estudante não é suficiente para obter essa honraria. Por esse motivo, ser um (ex-)bolsista FAPESP, de certa forma, é como ostentar um prêmio/certificado de excelência acadêmica.

Além disso, as bolsas da FAPESP possuem, geralmente, um valor expressivamente maior do que as de outras agências e os seus valores são atualizados com uma frequência muito maior do que as de outras agências. Atualmente (08/04/2023) essa diferença não é tão expressiva devido ao fato do governo federal ter reajustado os valores das bolsas federais recentemente em 40%, mas no passado essa diferença já passou de 50% com relação a outras bolsas.

Além disso, as bolsas FAPESP possuem duas vantagens que outras bolsas geralmente não tem: Taxa de Bancanda e BEPE.

Uma coloração ímpar é uma coloração própria \(c \colon V(G) \to \{1, 2, \ldots, k\}\) tal que, para todo vértice não isolado \(u \in V(G)\), temos que existe uma cor \(t\) tal que \(|\{v \in N(G) \colon c(v) = t\}|\) é ímpar. Em outras palavras, para todo vértice não isolado \(u \in V(G)\), existe uma cor que aparece um número ímpar de vezes na vizinhança de \(u\). A figura abaixo exibe um exemplo de uma coloração ímpar. Note que para cada vértice, existe uma cor em sua vizinhança que aparece um número ímpar de vezes. Por exemplo, fixando o vértice \(v_2\) e analisando a sua vizinhança, temos que as cores azul e vermelho aparecem duas vezes, que é um número par, e a preta aparece uma vez (um número ímpar). Assim, a condição é satisfeita para o vértice \(v_2\). Fazendo uma análise semelhante para os vértices restantes, concluímos que a condição é satisfeita para todos os demais e, portanto, essa coloração é uma coloração ímpar.

O número cromático ímpar de um grafo \(G\), denotado por \(\chi_o(G)\), é o menor número de cores de uma coloração ímpar de \(G\). Como uma coloração ímpar é uma coloração própria com uma restrição extra, não é difícil perceber que \(\chi(G) \leq \chi_o(G)\) para todo grafo \(G\).

Com relação a este problema, gostaria de investigar perguntas como as apresentadas a seguir. Lembre-se que mencionei que, devido ao Teorema de Brooks, quase todos os grafos satisfazem \(\chi(G) \leq \Delta(G)\). Note que esse resultado é para uma coloração própria. Como a coloração ímpar é uma coloração própria com uma condição extra, acredita-se que é necessário mais cores para colorir todos os grafos, mas não muitas. De fato, acredita-se que apenas uma cor extra é suficiente.

Pergunta 1: Se \(G\) é um grafo com grau mínimo ao menos \(3\), então \(\chi_o(G) \leq \Delta(G) + 1\)?

Também mencionei que, devido ao celebrado Teorema das Quatro Cores, quatro cores eram suficientes para colorir propriamente qualquer grafo planar. Por causa disso, acredita-se que cinco cores são suficientes para colorir com uma coloração ímpar qualquer grafo planar.

Pergunta 2: Se \(G\) é um grafo planar, então \(\chi_o(G) \leq 5\)?

Sabemos que \(\chi(G) \leq \chi_o(G)\) para qualquer grafo \(G\). O que ainda não se sabe é se o valor de \(\chi_o(G)\) pode ser muito maior do que o valor de \(\chi(G)\). Ou seja, estamos interessados em responder a seguinte pergunta.

Pergunta 3: Para quais grafos \(G\), vale que \(\chi_o(G) \leq C \times \chi(G)\)? onde \(C\) é uma constante.

Dado um grafo \(G\), uma coloração \(c \colon V(G) \to \{1, 2, \ldots, k\}\) (não necessariamente própria) e um vértice \(u \in V(G)\), definimos \(S(u) = \sum_{v \in N(u)} c(v)\), ou seja, \(S(u)\) é a soma da cor dos vizinhos de \(u\). Note que \(S\) é uma função \(S \colon V(G) \to \mathbb{N}\), i.e., uma função que associa os elementos de \(V(G)\) (vértices) aos elementos do conjunto dos naturais. Portanto, \(S\) também é uma coloração (não necessariamente própria), mas ao invés de definirmos \(S\) diretamente estabelecendo a cor de cada vértice, construímos \(S\) de forma indireta, derivando \(S\) de uma outra coloração.

Uma coloração aditiva é uma coloração \(c \colon V(G) \to \{1, 2, \ldots, k\}\) tal que \(S(u) \neq S(v)\) para toda aresta \(uv \in E(G)\), isto é, \(c\) é uma coloração aditiva se a coloração derivada \(S\) é uma coloração própria. O número da sorte, denotado por \(\eta(G)\), é o menor \(k\) para o qual existe uma coloração aditiva para \(G\) com \(k\) cores.

A figura a seguir ilustra duas coloração de um mesmo grafo, uma aditiva (à esquerda) e outra não aditiva (à direita). Nessa figura, os valores circunscritos no vértice denotam a coloração \(c \colon V(G) \to \{1, 2, \ldots, k\}\). Já os números anotados do lado externo dos vértices, denotam \(S \colon V(G) \to \mathbb{N}\). Primeiro vamos analisar a coloração \(c\) exibida à esquerda. Note que essa coloração não é própria, por exemplo, \(c(w_1) = c(w_3) = 2\) e \(w_1w_3 \in E(G)\). Entretanto, essa coloração é aditiva, pois quando analisamos a coloração \(S\) (os valores em vermelho), vemos que \(S\) é uma coloração própria, i.e., \(S(w_i) \neq S(w_j)\) sempre que \(w_iw_j \in E(G)\). Já a coloração \(c\) exibida à direita, apesar de ser uma coloração própria, não é uma coloração aditiva. Note, por exemplo, que \(S(w_1) = S(w_3) = 6\) e \(w_1w_3 \in E(G)\).

Sabemos como construir grafos \(G\) onde \(\eta(G)\) é tão grande quanto quisermos. Isso significa que você pode escolher um número \(\ell\) e através de um algoritmo podemos construir um grafo \(G\) tal que \(\eta(G) \geq \ell\). No entanto, o grafo construído por esse algoritmo possui muitos triângulos (cópias do \(K_3\)). Um grafo livre de triângulos é um grafo que não possui nenhum subgrafo do triângulo. Esses grafos possuem poucas arestas e, portanto, geralmente é mais fácil colorir-los. Assim, é natural perguntar-se.

Pergunta: Se \(G\) é um grafo livre de triângulos, então existe uma constante \(C\) tal que \(\eta(G) \leq C\)?

Um grafo \(G\) é localmente irregular se, para toda aresta \(uv \in E(G)\), temos que \(d_G(u) \neq d_G(v)\), onde \(d_G(x)\) denota o grau do vértice \(x\) em \(G\). A figura abaixo apresenta o desenho de um grafo localmente irregular. Note, por exemplo, que quando analisamos a aresta \(u_2u_5\), vemos que \(d_G(u_2) = 2 \neq 3 = d_G(u_5)\). Ademais, note que essa propriedade vale para toda arestas e, portanto, o grafo \(G\) exibido na figura é localmente irregular.

Dada uma coloração de arestas de um grafo \(G\), podemos olhar as arestas pintadas de uma mesma cor, digamos azul, como sendo um subgrafo de \(G\), o subgrafo azul. Dizemos que esse subgrafo é o subgrafo induzido pela cor azul. Uma decomposição localmente irregular é uma coloração de arestas onde cada cor induz um subgrafo que é um grafo localmente irregular. A figura abaixo exibe uma decomposição localmente irregular de um grafo usando 3 cores. Note como o subgrafo induzido por cada cor forma um grafo localmente irregular.

É conhecido da literatura que nem todo grafo admite uma decomposição localmente irregular, veja por exemplo os grafos abaixo.

No entanto, sabemos descrever exatamente a estrutura dos grafos que não podem ser decompostos em grafos localmente irregulares. Um grafo é decomponível se ele admite uma decomposição localmente irregular.

Baudon, Bensmail, Przybyło e Woźniak conjecturaram que todo grafo decomponível pode ser decomposto em três grafos localmente irregular, isto é, três cores é suficiente para decompor qualquer grafo decomponível em grafos localmente irregulares. Recentemente foi descoberto um grafo pequeno, com apenas 10 vértices, que requer quatro cores.

Nesse problema, estou interessado em responder a seguinte pergunta.

Pergunta: Para todo grafo decomponível \(G\), existe uma decomposição localmente irregular usando apenas 4 cores?

Seria muito legal responder essa permunta usando 4 cores, mas uma resposta para a pergunta abaixo também seria muito legal, pois atualmente ninguém consegue responder essa pergunta usando menos do que 238 cores.

Pergunta: Para todo grafo decomponível \(G\), existe uma decomposição localmente irregular usando apenas 100 cores?

Dizemos que um grafo \(G\) é \(3\text{-conexo}\) se precisamos remover ao menos \(3\) vértices para desconectar \(G\). Aqui a remoção de vértices significa remover os vértices do grafo e qualquer aresta que os toquem. A figura abaixo ilustra um exemplo de um grafo que é \(3\text{-conexo}\).

A figura abaixo ilustra o grafo obtido ao removermos os dois vértices destacados em vermelho. Note que o grafo resultante continua conexo, i.e., permanece sendo uma única malha conectada. Note que para desconectar esse grafo (quebrar a rede de conexão em dois ou mais pedaços) precisamos remover ao menos três vértices, não é possível fazer isso removendo dois ou menos vértices.

Dizemos que um grafo é cúbico se todos os vértices possuem grau três. A figura abaixo exibe um exemplo de um grafo cúbico.

Um conjunto dominante de um grafo \(G\) é um conjunto de vértices \(S\) que satisfaz a seguinte propriedade: se \(u \in V(G)\) então ou \(u \in S\) ou \(u\) tem um vizinho em \(S\). Note que todo grafo \(G\) possui um conjunto dominante, já que \(V(G)\) é um conjunto dominante. Além disso, podemos ver que \(V(G)\) é um conjunto dominante de tamanho máximo, então encontrar um conjunto dominante máximo é um problema trivial. Portanto, estamos interessados em encontrar um conjunto dominante de tamanho mínimo.

Em 1996, Reed provou que todo grafo cúbico com \(n\) vértices possui um conjunto dominante com tamanho menor ou igual à \(3/8 n\). Esse resultado diz que o grafo exibido acima, que tem \(n = 10\) vértices, contém um conjunto dominante de tamanho menor ou igual à \(3/8 \times 10 = 3,75\), o que é verdade como pudemos comprovar pelos vértices destacados em vermelho.

Além de provar o resultado mencionado acima, Reed fez a seguinte pergunta:

Pergunta: Se \(G\) é um grafo cúbico, então \(G\) contém um conjunto dominante de tamanho no máximo \(1/3 n\)?

Tempos depois essa pergunta foi respondida de forma negativa, existiam grafos cúbicos com \(n\) vértices onde seus conjuntos dominantes tinham tamanho maior do que \(1/3 n\). No entanto, todos esses grafos não eram \(3\text{-conexos}\). Assim, uma nova pergunta foi feita e é nesta pergunta que estou interessado.

Pergunta: Se \(G\) é um grafo cúbico e \(3\text{-conexo}\), então \(G\) contém um conjunto dominante de tamanho no máximo \(1/3 n\)?

Pesquisa Operacional é a área do conhecimento que lida com o desenvolvimento de métodos e aplicações para tomada de decisão. No nosso contexto, estaremos interessados em resolver problemas de otimização na prática da forma mais eficiente possível. A grosso modo, um problema de otimização é um problema no qual existe um conjunto de soluções possíveis, cada uma dessas soluções tem um custo/valor, e estamos interessados em encontrar a solução de valor máximo/mínimo. Por exemplo, dado o mapa rodoviário do estado de São Paulo, gostaríamos de encontrar o trajeto mais curto da cidade de Santo André até a cidade de Campinas. A maioria dos problemas interessantes de otimização combinatória, e geralmente os mais importantes em termos práticos, são problemas NP-difíceis. Sendo NP-difícil ou não, precisamos resolvê-los no dia a dia. Como não conhecemos nenhum algoritmo eficiente até o momento, o jeito é apelar para todo tipo de truque baixo para resolver o problema da melhor forma possível. É aqui que entram as heurísticas, meta-heurísticas, programação linear (inteira), programação por restrição, algoritmos de aproximação, algoritmos probabilísticos.

Na verdade, este não é um projeto, é um metaprojeto, ou seja, uma espécie de esqueleto de projeto do qual podemos criar vários projetos. O fluxo de pesquisa nesse (meta)projeto é basicamente o seguinte:

1. Escolher um problema NP-difícil interessante para trabalhar;
2. Bolar uma forma de resolvê-lo (geralmente heurística ou programação linear inteira);
3. Implementar essa solução;
4. Rodar o seu programa em um banco de instâncias do problema (benchmark);
5. Reportar os seus resultados (tempo de execução e qualidade da solução encontrada) comparando-os com os da literatura no relatório final do trabalho.

Como um exemplo de um trabalho nessa linha, veja: Um estudo computacional do Problema do Gnosticismo Perfeito. Tenha em mente que o trabalho anterior é um trabalho de mestrado, para um trabalho de conclusão de curso espera-se algo mais simples.

O SageMath é um sistema de álgebra computacional (CAS) com recursos que cobrem muitos aspectos da matemática, incluindo álgebra, combinatória, teoria dos grafos, análise numérica, teoria dos números, cálculo e estatísticas. Em particular, o SageMath possui um amplo número de ferramentas para lidar com grafos (veja a lista aqui).

Entretanto, o SageMath é baseado em Python, que não é uma linguagem famosa pela sua eficiência. Em alguns casos para ganhar desempenho precisamos implementar o nosso programa em uma linguagem mais eficiente como Fortran/C/C++ ou Rust. Entretanto existe uma carência de bibliotecas para grafos nessas linguagens.

O igraph é uma coleção de bibliotecas para criar e manipular grafos em C. O software é amplamente utilizado em pesquisas acadêmicas em network science e áreas afins. A publicação que apresenta o software tem 11.163 citações em 16 de Março de 2023, de acordo com o Google Scholar. Entretanto, quando comparado ao SageMath, o igraph é extremamente pobre em recursos para grafos.

Minha ideia inicial era propor um meta-projeto no qual contribuíssemos com o projeto igraph (afinal, por que reinventar a roda, não é mesmo?). Entretanto, a linguagem C, por ser antiga, deixa a desejar quando pensamos em práticas modernas de engenharia de software, como o suporte a testes unitários. Embora existam frameworks para testes unitários em C, eles são desajeitados, e, talvez por isso, não são utilizados no projeto igraphs. O projeto igraphs optou por fazer testes de uma forma bem artesanal.

Todos esses pontos me levaram ao desejo de recriar a roda, implementando uma nova biblioteca para grafos, a ABCGraphs, em uma linguagem moderna e eficiente (Rust) e usando as melhores práticas de desenvolvimento de software (testes unitários, versionamento, integração contínua e etc).

Este metaprojeto objetiva adicionar novas funcionalidades à bibliotecas ABCGraphs. O fluxo de trabalho de uma instância desse metaprojeto seria:

1. Escolher uma funcionalidade para adicionar a ABCGraphs, por exemplo, verificar se um dado grafo \(G\) possui largura arbórea no máximo \(k\).
2. Estudar a literatura sobre o problema e descobrir qual trabalho apresenta a melhor solução para o problema, por exemplo, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
3. Estudar a teoria do artigo, compreender o artigo, compreender o porquê do algoritmo funcionar (entender as demonstrações de correção do algoritmo)
4. Implementar o algoritmo, escrever testes unitários
5. Fazer um pull-request e integrar a sua solução na branch do projeto
6. Escrever o relatório do trabalho

Eu sou um capitalista, gosto de dinheiro e me interesso pelo mercado financeiro. Se você desejar desenvolver algum software para o mercado financeiro no seu PGC, tais como,

• Sistema de recomendação de compra e venda de ações/FIIs/commodities
• Ferramentas para auxiliar análise técnica ou fundamentalista;
• etc

eu posso lhe orientar. Saiba entretanto que isso é apenas um hobby para mim, nunca fiz nenhum curso formal nessa área e nem faço pesquisa nela.

O overleaf é um software opensource de edição colaborativa de LaTeX. Atualmente é uma ferramenta muito utilizada por pesquisadores das áreas de exatas, como matemáticos, físicos e cientistas da computação. Embora seja opensource e possa ser instalado localmente em um servidor local, a grande maioria dos usuários utilizam o overleaf pelo site overleaf.com. O overleaf.com oferece uma conta gratuita com as mesmas funcionalidades da versão opensource, mas também oferece uma conta premium com funcionalidades extras importantes que não estão disponíveis na versão opensource, tais como integração com o git, github e dropbox.

O objetivo desse projeto é implementar a integração git, e outras funcionalidades, na versão opensource do overleaf.

Neste trabalho você terá que lidar com desenvolvimento web, aprender a fazer deploy de serviços web, descobrir como se familiarizar como um código que não foi escrito por você, desenvolver testes e trabalhar segundo as boas práticas de desenvolvimento de software para adicionar funcionalidades em um projeto opensource.