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?

 

Biologia molecular e genética (parte II)

Speaker: Felipe R. Silva, EMBRAPA/UNICAMP.

Date: 17 aug 2021, 16h30.

Place: Google Meet: kkd-ktkr-swg.

 

Biologia molecular e genética

Speaker: Felipe R. Silva, EMBRAPA/UNICAMP.

Date: 12 aug 2021, 16h.

Place: Google Meet: kkd-ktkr-swg.

Abstract: TBA.

 

Co-degeneracy and co-treewidth: Using the complement to solve dense instances

Speaker: Gabriel Lagoa Duarte, U, UFF.

Date: 28 jul 2021, 14h.

Place: Google Meet: swt-uoda-eyn.

Abstract: Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle,Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently.

In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle,Longest Path, and Edge Dominating Setare FPT when parameterized by co-degeneracy. On the other hand, Graph Coloringis para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy.

Additionally, we show that Precoloring Extensionis fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure.

This is joint work with Mateus de Oliveira Oliveira and Uéverton S. Souza.

 

Reducing graph transversals via edge contractions

Speaker: Vinícius Fernandes dos Santos, UFMG.

Date: 30 jun 2021, 14h.

Place: Google Meet: meet.google.com/npz-qztp-riw.

Abstract: For a graph parameter $\pi$, the Contraction($\pi$) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which $\pi$ has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $\pi$ is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, which in particular imply that Contraction($\pi$) is co-NP-hard even for fixed k=d=1 when $\pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $\pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Joint work with Paloma T. Lima, Ignasi Sau and Uéverton S. Souza, available at arXiv:2005.01460.

 

Maximum cut and Steiner tree restricted to interval graphs and related families

Speaker: Celina de Figueiredo, COPPE UFRJ.

Date: 12 mai 2021, 14h.

Place: Google Meet: meet.google.com/nhe-vccv-qrf

Abstract: We consider Column 16 -- Graph Restrictions and Their Effect -- of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns, and several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We focus on columns MaxCut and StTree, where there are recent resolved entries for interval graphs and related families.

 

Pagina 1 de 3