Seminários de Teoria da Computação, Combinatória e Otimização

Bem-vindo!

Os seminários do grupo ocorrem regularmente às sextas-feiras às 14:00. As datas também são mantidas em um calendário Google.

Aqui também divulgamos seminários organizados por iniciativa dos alunos do grupo. Usamos o acrônimo T.A.C.O. (Teoria da computação, Algoritmos, Combinatória e Otimização) na descrição desses seminários para diferenciá-los dos seminários usuais.

Group seminars take place on Fridays at 14:00. Seminar dates can also be found in a Google calendar. Here you find speakers and abstracts for future and past seminars.

Here we also publish seminars organized by the students of the TCCO group. We put the acronym T.A.C.O. (Theory of computation, Algorithms, Combinatorics and Optimization) in the description of such seminars to differentiate them from the regular ones.

Seminários de 2016

Subdivisão de digrafos com grau mínimo alto
Palestrante: Phablo Moura (IME-USP)
Quando: Sexta-feira, 2/12/2016, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Dado um digrafo \(D\), uma subdivisão de \(D\) é um digrafo obtido pela substituição de cada arco \(uv\) em \(D\) por um caminho direcionado \(P(u,v)\) de \(u\) para \(v\) tal que todo vértice interno de \(P(u,v)\) (caso exista) é um novo vértice. Em 1985, Mader conjecturou a existência de uma função \(f\) tal que todo digrafo com grau mínimo de saída pelo menos \(f(k)\) contém uma subdivisão do torneio transitivo de ordem \(k\). Essa conjectura ainda está completamente aberta uma vez que mesmo a existência de \(f(5)\) é desconhecida. Neste seminário, apresentaremos algumas novas evidências dessa conjectura. Mais precisamente, se \(D\) é um caminho orientado, ou uma in-arborescência (i.e. uma árvore com todas arestas orientadas em direção à raiz), então todo digrafo com grau mínimo de saída suficientemente grande contém uma subdivisão de \(D\). Ademais, apresentaremos um visão geral das principais conjecturas e resultados da literatura relativos à subdivisão de digrafos.

(Este é um trabalho em conjunto com Pierre Aboulker, Nathann Cohen, Frédéric Havet, William Lochet e Stéphan Thomassé)

Embedding and packing large graphs into dense and sparse graphs
Palestrante: Anusch Taraz (TU Hamburg)
Quando: Sexta-feira, 7/10/2016, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Extremal combinatorics is often concerned with the forced appearance of highly organized structures. In this talk, we explain two major research avenues that deal with such situations. On the one hand, density results assert that these substructures must be present in any sufficiently dense host configuration. On the other hand, partition theorems guarantee that, no matter how we partition a sufficiently large object, at least one of the partition classes must contain the desired substructure.

We first survey old and new results of both types, to give a flavour of the field and its methods, and then focus on a sequence of results that generalize the existence of paths and cycles to graphs of sublinear bandwidth.

Complexity of Matchings and Packings
Palestrante: Jie Han (IME-USP)
Quando: Sexta-feira, 30/9/2016, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Given two \(k\)-graphs (\(k\)-uniform hypergraphs) \(H\) and \(F\), a perfect \(F\)-packing in \(H\) is a collection of vertex disjoint copies of \(F\) in \(H\) which together cover all the vertices in \(H\). In the case when \(F\) is a single edge, a perfect \(F\)-packing is simply a perfect matching. For a given fixed \(F\), it is often the case that the decision problem whether an \(n\)-vertex \(k\)-graph \(H\) contains a perfect \(F\)-packing is NP-complete. Indeed, if \(k\ge 3\), the corresponding problem for perfect matchings is NP-complete whilst if \(k = 2\) the problem is NP-complete in the case when F has a component consisting of at least \(3\) vertices.

There has been interest in determining the best possible degree condition that forces a perfect \(F\)-packing in \(H\). From the complexity point of view, if such a condition is satisfied by \(H\), then the decision problem is trivially in P: the answer is always positive.

Then a natural question that arises from this is: can we lower the degree condition and still guarantee that the decision problem is polynomial-time solvable? In this talk I will discuss this problem and a recent general theorem developed for problems of this type.

Joint work with Andrew Treglown (University of Birmingham).

Edge-colorings of graphs and hypergraphs without sub(hyper)graphs with a given coloring pattern
Palestrante: Hanno Lefmann (TU Chemnitz)
Quando: Sexta-feira, 23/9/2016, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Given any graph \(G\) on \(n\) vertices and given a number \(r\) of colors, how many edge-colorings of \(G\) with \(r\) colors are there such that no monochromatic triangle arises? What are the extremal graphs on \(n\) vertices?

These are typical questions that we consider in this talk. Instead of forbidding triangles one can forbid fixed complete graphs, and instead of the monochromatic pattern one can look at the rainbow or other patterns. Among others we also consider forbidding a monochromatic or rainbow Fano plane, which is a linear \(3\)-uniform hypergraph on seven vertices, and the corresponding extremal \(n\)-vertex \(3\)-uniform hypergraphs.

Extremal problems for uniformly dense hypergraphs
Palestrante: Mathias Schacht (Universität Hamburg)
Quando: Sexta-feira, 9/9/2016, às 14:00
Onde: Auditório Jacy Monteiro

Resumo:

For a \(k\)-uniform hypergraph \(F\) let \(\textrm{ex}(n,F)\) be the maximum number of edges of a \(k\)-uniform \(n\)-vertex hypergraph \(H\) which contains no copy of \(F\). Determining or estimating \(\textrm{ex}(n,F)\) is a classical and central problem in extremal combinatorics. While for \(k=2\) this problem is well understood, due to the work of Turán and of Erdös and Stone, only very little is known for \(k\)-uniform hypergraphs for \(k>2\). We focus on the case when \(F\) is a \(k\)-uniform hypergraph with three edges on \(k+1\) vertices. Already this very innocent (and maybe somewhat particular looking) problem is still wide open even for \(k=3\).

We consider variants of the problem where the large hypergraph \(H\) enjoys additional hereditary density conditions. Questions of this type were suggested by Erdös and Sós about 30 years ago. We present recent results in that direction, which were obtained in joint with Chr. Reiher and V. Rödl.

Applications of flag algebras in extremal graph theory
Palestrante: Jan Volec (ETH Zürich)
Quando: Terça-feira, 2/8/2016, às 15:40
Onde: Sala B-144

Resumo:

We present two techniques in extremal graph theory based on the semidefinite method from flag algebras. The first technique combines the semidefinite method with stability-type arguments, and we demonstrate this technique on a problem concerned with the maximum number of rainbow triangles in 3-edge-colored graphs.

In the second part of the talk, we apply finite forcibilty techniques in the flag algebra setting in order to determine the minimum number of edges that occur in \(5\)-cycles of \(n\)-vertex graphs with more than \(n^2/4\) edges.

The talk is based on results obtained jointly with Jozef Balogh, Andrzej Grzesik, Ping Hu, Bernard Lidicky, Florian Pfender, and Michael Young.

Erdős' 1/50-conjecture for Andrásfai-graphs
Palestrante: Wiebke Bedenknecht (Universität Hamburg)
Quando: Terça-feira, 2/8/2016, às 14:40
Onde: Sala B-144

Resumo:

It is known that any \(n\)-vertex triangle-free graph \(G\) with \(\chi(G)\leq3\) and \(\delta(G)>n/3\) is a blow-up of a graph \(F_d\) for some \(d\geq 1\), where \(F_d\) is a certain \(d\)-regular triangle-free graph with \(3d-1\) vertices. Erdős conjectured that any \(n\)-vertex triangle-free graph contains a subset of \(n/2\) vertices that spans at most \(n^2/50\) edges. We confirm this conjecture for an infinite family of blow-ups of \(F_d\) for \(d\geq 1\).

Joint work with Guilherme Mota, Mathias Schacht and Christian Reiher.

Sharp thresholds for monochromatic cycles
Palestrante: Fabian Schulenburg (Universität Hamburg)
Quando: Terça-feira, 2/8/2016, às 14:00
Onde: Sala B-144

Resumo:

For a given graph \(F\) we consider the family of (finite) graphs \(G\) with the Ramsey property for \(F\), that is, the set of such graphs \(G\) with the property that every two-colouring of the edges of \(G\) yields a monochromatic copy of \(F\). For \(F\) being a triangle Friedgut, Rödl, Rucínski, and Tetali (2004) established the sharp threshold for the Ramsey property in random graphs. We obtained a simpler proof of this result which extends to a more general class of graphs \(F\) including all cycles.

The proof is based on Friedgut's criteria (1999) for sharp thresholds, and on the recently developed container method for independent sets in hypergraphs. The proof builds on some recent work of Friedgut et al. who established a similar result for van der Waerden’s theorem. This is joint work with Mathias Schacht.

Online Combinatorial Optimization Problems
Palestrante: Mário César San Felice (IME-USP)
Quando: Sexta-feira, 20/5/2016, às 14:00
Onde: Sala B-139

Resumo:

Online problems allow us to capture the uncertainty related to input data that arrives over time. This characteristic is common in problems from several areas of operations research and computer science, like:

  • Resource management - the first online algorithms were developed for scheduling, packing and load balancing problems.
  • Dynamic data structures - the list access problem deals with the maintenance of linked lists used in dictionaries.
  • Computer architecture - the paging problem deals with the management of cache and random access memories.
  • Sustainability - the ski-rental problem capture energy consumption issues in computer clusters and multi-core processors.
  • Network design - online versions of Steiner tree and facility location problems deal with building infrastructures to serve demands that arrive in real time.

In this seminar I will give an introduction to the area of online computation through the perspective of competitive analysis by showing some important examples in these fields.

Equiangular lines
Palestrante: Gabriel Coutinho (IME-USP)
Quando: Sexta-feira, 13/5/2016, às 14:00
Onde: Sala B-139

Resumo:

A set of lines is called equiangular if the angle between any two lines is the same. What is the maximum number of equiangular lines in a real or complex vector space of dimension \(d\)? For instance, in \(\mathbb{R}^2\), it is quite obvious that the best we can do is to pick the three lines corresponding to the medians of an equilateral triangle. Naive intuition however serves no use in higher dimensions or in complex spaces. For example, there are nine equiangular lines in \(\mathbb{C}^3\). Perhaps unsurprisingly, this problem remains open in general. Yet it has motivated very active research in the past few years.

In this talk, I will briefly survey some basic properties, old results and connections to other fields, notably combinatorics. I will also talk about the results in a joint work with Godsil, Shirazi and Zhan. No prior knowledge about the topic will be required.

Independent sets and matchings via the hardcore model
Palestrante: Ewan Davies, Matthew Jenssen, Barnaby Roberts (LSE)
Quando: Sexta-feira, 8/4/2016, às 14:00
Onde: Sala B-144

Resumo:

We will give three short talks on a probabilistic method that allows us to prove a collection of results (both new and old) under the same framework. In particular we prove the following:

(1) A strengthening of Jeff Kahn's and Yufei Zhao's theorem that disjoint unions of \(K_{d,d}\)s maximise the number of independent sets in a \(d\)-regular graph.

(2) A new result replacing independent sets in 1) by matchings and a resolution of the asymptotic upper matching conjecture.

(3) Shearer's result on independent sets in triangle-free graphs and the resulting upper bound on the Ramsey number \(R(3,k)\).

(4) A result of Cooper, Dutta and Mubayi counting the number of independent sets in triangle-free graphs.

The proofs of the above all rely on analysing the hardcore model and the monomer-dimer model borrowed from statistical physics. This is joint work with Will Perkins.

Finite Geometries and Graphs
Palestrante: Gabriela Araujo-Pardo (Universidad Nacional Autónoma de México)
Quando: Sexta-feira, 18/3/2016, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

In this talk we discuss some relations between two topics of Discrete Mathematics: Finite Geometries and Graphs. In particular, we give a brief survey of the "Cage Problem" and how finite geometries have been used to solve some questions related to cages. We also give our techniques to find more "small graphs" using finite geometries. On the other hand, we also discuss some problems related to colorings of the edges of complete graphs: the achromatic, pseudoachromatic, and connected pseudoachromatic indices of complete graphs and how projective planes solve some questions related to these parameters.