Introdução ao Método Probabilístico: Primeiro e Segundo Momento

Speaker: Alicia Amorim, UFF.

Date: 30 nov 2022, 14h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: O Método Probabilístico é um método usado para provar teoremas baseado na ideia “Se um evento ocorre com probabilidade positiva, então tal evento é não vazio”. É uma ferramenta bastante utilizada em matemática discreta com diversas aplicações em combinatória, álgebra, teoria dos números e computação.

Neste seminário vamos fazer uma introdução ao método e explorar um pouco da sua essência através da sua aplicação em alguns problemas em teoria de grafos e teoria dos números

Subgrafos multipartidos grandes em grafos H-livres

Speaker: Taísa Martins, UFF.

Date: 05 oct 2022, 14h.

Place: Google Meet: swt-uoda-eyn.

Abstract: Füredi provou que todo grafo K_{r+1}-livre G pode se tornar r-partido pela remoção de no máximo k arestas onde k = ((r-1)/2r)(v(G))^2 - e(G). Investigamos versões mais fortes desse resultado. Para r<5, mostramos que todo grafo K_{r+1}-livre G pode se tornar r-partido pela remoção de no máximo 4k/5 arestas, e conjecturamos que o mesmo é verdadeiro para todo r. Tal conjectura implica uma solução para um problema de Sudakov com relação ao menor número de arestas que precisam ser removidas para tornar um grafo K_{r+1}-livre em um grafo bipartido. Por fim, mostramos que todo grafo K_6-livre G pode se tornar bipartido pela remoção de no máximo 4(v(G))^2/25 arestas, resolvendo um dos casos do problema de Sudakov. Nossa principal ferramenta é a técnica de flag álgebras de Razborov.

Esse é um trabalho em conjunto com Ping Hu, Bernard Lidický, Sergey Norin e Jan Volec.

O espectro da matriz distância de uma família de grafos distância-birregular

Speaker: Miriam Abdon, UFF.

Date: 27 jan 2022, 16h.

Place: Google Meet: swt-uoda-eyn.

Abstract:

Atik e Panigrahi, no artigo “On the distance spectrum of distance regular graphs", mostraram que o espectro da matriz distância D de grafos distância-regular tem no máximo d+1 elementos (onde d é o diâmetro de grafo). No artigo eles também levantaram a seguinte questão: existem outros grafos, além dos distância-regular, tais que o espectro de D tem no máximo d+1 elementos?

Respondemos afirmativamente à questão proposta, apresentando uma família de grafos distância-birregular com diâmetro arbitrariamente grande e tais que D possui exatamente quatro autovalores distintos.

Particionando grafos completos coloridos em poucos subgrafos esparsos monocromáticos

Speaker: Walner Mendonça, IST Austria.

Date: 01 dec 2021, 14h.

Place: Google Meet: swt-uoda-eyn.

Abstract:

Gerencsér e Gyárfás provaram em 1967 que para qualquer 2-coloração das arestas de K_n, é possível particionar V(K_n) em dois caminhos monocromáticos. Tal resultado, cuja prova é bastante simples, motivou inúmeros outros problemas desafiantes os quais têm sido objetos de extensa pesquisa em combinatória extremal nos últimos anos. Por exemplo, Erdős, Gyárfás e Pyber conjecturaram em 1991 que para toda r-coloração de K_n existem r caminhos monocromáticos particionando V(K_n). Podemos também encontrar na literatura outras versões do problema onde ao invés de obtermos particionamento por caminhos, foca-se em obter particionamento por árvores, ciclos ou até mesmo potência de ciclos.

Grinshpun e Sárkőzy estudaram uma versão mais geral do problema onde interessa-se em particionar V(K_n) em subgrafos monocromáticos de grau limitado. Eles provaram que para toda sequência de grafos de grau limitado F, o seguinte vale: para qualquer 2-coloração das arestas de K_n é possível particionar V(K_n) em no máximo 2^{O(D log D)} cópias monocromáticas de grafos da sequência F. Eles conjecturaram que para r-colorações, também deve ser possível particionar V(K_n) em uma quantidade exponencial de cópias monocromáticas de grafos da sequência F. Mais precisamente, a conjectura deles afirma que para todo inteiro positivo r, existe uma constante C=C(r) para o qual o seguinte vale: para qualquer r-coloração das arestas de K_n, é possível particionar V(K_n) em no máximo 2^{D^C} cópias monocromáticas de grafos da sequência F. Neste trabalho apresentamos o primeiro progresso na conjectura de Grinshpun e Sárkőzy estabelecendo um limitante super-exponencial.

Apresentação baseada em um trabalho conjunto com Jan Corsten (LSE, UK).

Teoria de Ramsey em grupos

Speaker: Roberto Parente, UFBA e USP

Date: 27 oct 2021, 14h.

Place: Google Meet: swt-uoda-eyn.

Abstract: Em Teoria de Ramsey estamos interessados em, dada uma estrutura matemática, garantir que qualquer coloração de seus elementos sempre existirá uma subestrutura de interesse monocromática. A pergunta desta apresentação é como inserir relações entre as cores utilizando grupos (abelianos). Faremos um breve panorama sobre resultados da Teoria de Ramsey em grupos onde o tipo de problema estudado é o seguinte: dado um grupo G e um grafo H, R(H,G) é o menor inteiro positivo t tal que toda coloração das arestas do grafo completo K_t usando elementos de G como cores possui um subgrafo isomorfo a H tal que a soma das ‘cores’ das arestas de H é 0 (em G). Para quais pares (G,H) esse número existe, e, nesse caso, quão precisamente podemos estimar seu valor?

Mais artigos...

Pagina 1 de 6