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 2017

Embedding spanning bounded degree subgraphs in randomly perturbed graphs
Palestrante: Yury Person (Goethe University Frankfurt)
Quando: Sexta-feira, 17/11/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

We study the model of randomly perturbed dense graphs, which is the union of any graph \(G_\alpha\) with minimum degree \(\alpha n\) and the binomial random graph \(G(n,p)\). We study when \(G_\alpha \cup G(n,p)\) contains any single spanning graph with maximum degree \(\Delta\).

Joint work with Julia Böttcher, Richard Montgomery and Olaf Parczyk.

Discrete geometry of surfaces towards the filling area conjecture
Palestrante: Marcos Cossarini (IMPA)
Quando: Sexta-feira, 10/11/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

In 1983, Gromov conjectured that the hemisphere has smallest area among those Riemannian surfaces that fill isometrically a circle of given length. We discuss the history of this problem, and present an equivalent(*) discrete conjecture, where a cycle graph of length 2n is filled isometrically by a square-celled surface. If time permits, we also introduce a directed discrete version, related to Postnikov's plabic graphs.

(*) The square-celled discrete problem is equivalent to the continuous problem for self-reverse Finsler metrics. The directed discrete version is introduced to discretize Finsler metrics that are not self-reverse, and may work for higher dimensions as well.

This work is in progress and not yet available as a paper or preprint.

The Online Multicommodity Connected Facility Location problem
Palestrante: Mário César San Felice (IME-USP)
Quando: Sexta-feira, 20/10/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

The Multicommodity Connected Facility Location problem is a generalization of the Connected Facility Location problem, which arises from a combination of the Facility Location and the Steiner Forest problems through the rent-or-buy model.

We consider the online version of this problem and present a randomized algorithm that is \(O(\log^{2}n)\)-competitive, where \(n\) is the number of given client pairs.

Our algorithm combines the sample-and-augment framework with previous algorithms for the Online Prize-Collecting Facility Location and the Online Steiner Forest problems.

Also, for the special case of the problem with edge scale factor equals 1, we show that a variant of our algorithm is deterministic and \(O(\log{n})\)-competitive.

On the hard sphere model and sphere packings in high dimensions
Palestrante: Matthew Jenssen (LSE, IMPA)
Quando: Sexta-feira, 6/10/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

We provide a statistical physics based proof of the \(\Omega(d \cdot 2^{-d})\) lower bound on the sphere packing density of \(\mathbb{R}^d\). Such a bound on the sphere packing density was first achieved by Rogers, with subsequent improvements to the leading constant by Davenport and Rogers, Ball, Vance, and Venkatesh. While our technique does not achieve the same constant as these other proofs, we do obtain additional probabilistic and geometric information: we lower bound the expected packing density of a random configuration from the hard sphere model and lower bound the entropy of sphere packings of density \(\Theta(d \cdot 2^{-d})\), a measure of how plentiful such packings are.

Minicurso de matróides: Lecture 3: Matroid Polytopes and Ehrhart polynomial
Palestrante: Jorge L. Ramírez Alfonsín (Université de Montpellier)
Quando: Segunda-feira, 14/8/2017, às 16:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

We will introduce and discuss a natural polytope associated to a matroid called matroid base polytope. After recalling some basic facts on Ehrhart theory, we study the Ehrhart polynomial of lattice path matroid polytopes. We shall present a combinatorial method to compute Ehrhart polynomials for these polytopes.

Euler-Maclaurin Summation Formulas for Polytopes
Palestrante: Jamie Pommersheim
Quando: Sexta-feira, 11/8/2017, às 16:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Discovered in the 1730's, the classical Euler-Maclaurin formula may be viewed as a formula for summing the values of a function over the lattice points in a one-dimensional polytope. Several years ago, Berline and Vergne generalized this formula to polytopes of arbitrary dimension, obtaining a formula for the sum of a polynomial function over the lattice points in any rational polytope. This talk will present an algebraic approach to the Euler-Maclarurin problem for polytopes based on recent results of Fischer and the speaker. While this approach is motivated from the theory of toric varieties, in this talk we aim to tell the story in a way that does not directly use results from toric geometry.

Minicurso de matróides: Lecture 2. Oriented matroids: some applications
Palestrante: Jorge L. Ramírez Alfonsín (Université de Montpellier)
Quando: Sexta-feira, 11/8/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

We will present and discuss the so-called McMullen’s problem on projective transformations and polytopes. We will present a result on this geometric problem by using the combinatorics of oriented matroid theory. If time allow us, we will also discuss an application of oriented matroids on some knot problems.

Minicurso de matróides: Lecture 1. Oriented matroids: introduction
Palestrante: Jorge L. Ramírez Alfonsín (Université de Montpellier)
Quando: Quarta-feira, 9/8/2017, às 10:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

We will give an introduction on basic notions on oriented matroid theory. After recalling basic definitions and giving motivating examples of oriented matroids, we will present some standard properties and constructions. We will also discuss the well-known topological representation of oriented matroids.

Subdivisão colorida de mapas
Palestrante: Lucas Moutinho Bueno (UNICAMP)
Quando: Sexta-feira, 30/6/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Esta palestra descreve algoritmos propostos na tese de doutorado de Lucas Bueno. Eles têm como objetivo subdividir mapas topológicos de duas ou três dimensões em triangulações coloridas nos vértices, usando 3 ou 4 cores, respectivamente. Os algoritmos tentam criar o menor número possível de triângulos (ou tetraedros) na saída em tempo compatível com o método convencional da subdivisão baricêntrica. Provamos, tanto teoricamente como empiricamente, que os algoritmos propostos geram menos triângulos (ou tetraedros) que a subdivisão baricêntrica. Triangulações coloridas são importantes para o uso da estrutura de dados Gema para representar a topologia de triangulações de qualquer dimensão \(d >= 2\).

From graphs, to polytopes, to Ehrhart polynomials
Palestrante: Cristina Fernandes (IME-USP)
Quando: Sexta-feira, 23/6/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Liu and Osserman associated to each cubic graph a polytope and the corresponding Ehrhart quasi-polynomial. They studied these polytopes and quasi-polynomials, and conjectured that all connected cubic graphs with the same number of nodes and edges have the same Ehrhart quasi-polynomial. We prove this conjecture.

This is joint work with José Coelho de Pina, Jorge Luis Ramírez Alfonsín, and Sinai Robins.

Path cover number and related problems
Palestrante: Jie Han (IME-USP)
Quando: Sexta-feira, 2/6/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

The path cover number is defined as the minimum number of vertex disjoint paths whose union covers all vertices of the graph. In this talk I will survey the related results on the path cover number, in particular, about a conjecture for the path cover number of regular graphs by Magnant and Martin.

The hyperbolic Hadwiger-Nelson problem
Palestrante: Evan DeCorte (McGill)
Quando: Sexta-feira, 19/5/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Consider the graph \(H(d)\) whose vertex set is the hyperbolic plane, where we join two points with an edge when their distance is equal to \(d\). Asking for the chromatic number of this graph is the hyperbolic analogue to the famous Hadwiger-Nelson problem about colouring the Euclidean plane. As in the Euclidean case, one can lower bound the chromatic number of \(H(d)\) by 4 for all \(d\). Using spectral methods, we prove that if the colour classes are measurable, then at least 6 colours are needed to properly colour \(H(d)\) when \(d\) is sufficiently large. This can be regarded as the hyperbolic analogue to Falconer's lower bound for the measurable chromatic number of the plane. Joint work with Konstantin Golubev.

The sandwich problem for almost monotone properties
Palestrante: Celina Miraglia Herrera de Figueiredo (COPPE-UFRJ)
Quando: Sexta-feira, 31/3/2017, às 14:00
Onde: Auditório Jacy Monteiro

Resumo:

We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in \(C\) as an induced subgraph is almost monotone if \(C\) is the set of thetas, the set of pyramids, or the set of prisms and thetas. Moreover, we show that the imperfect graph sandwich problem, also known as the Berge trigraph recognition problem, can be solved in polynomial time.

Coalescence and minimal spanning trees of irregular graphs
Palestrante: Yevgenij Kovchegov (Oregon State University)
Quando: Sexta-feira, 24/2/2017, às 14:00
Onde: Auditório Antônio Gilioli (sala 247 do Bloco A)

Resumo:

Get the abstract here.

Semidefinite optimization and arithmetic progressions
Palestrante: Frank Vallentin (University of Cologne)
Quando: Sexta-feira, 17/2/2017, às 14:00
Onde: Auditório Jacy Monteiro

Resumo:

In this talk I will derive a semidefinite optimization problem which gives a lower bound for the number of \(k\)-term arithmetic progressions in fixed-cardinality subsets of a finite prime field. After applying symmetry reduction techniques one can compute these lower bounds for \(k = 3\) and \(k = 4\).

(Joint work with Cordian Riener and Aron Rahman.)

Infinite Sidon sets contained in sparse random sets of integers
Palestrante: Sang June Lee (Duksung Women's University, Seoul, Korea)
Quando: Sexta-feira, 3/2/2017, às 14:00
Onde: Sala 144-B

Resumo:

A set~\(S\) of natural numbers is a \emph{Sidon} set if all the sums \(s_1+s_2\) with~\(s_1\), \(s_2\in S\) and \(s_1\leq s_2\) are distinct. Let constants \(\alpha>0\) and \(0<\delta<1\) be fixed, and let~\(p_m=\min\{1,\alpha m^{-1+\delta}\}\) for all positive integers~\(m\). Generate a random set~\(R\subset\mathbb{N}\) by adding~\(m\) to~\(R\) with probability~\(p_m\), independently for each~\(m\). We investigate how dense a Sidon set~\(S\) contained in~\(R\) can be. Our results show that the answer is qualitatively very different in at least three ranges of~\(\delta\). We prove quite accurate results for the range~\(0<\delta\leq2/3\), but only obtain partial results for the range~\(2/3<\delta\leq1\). This is joint work with Y. Kohayakawa and V. Rödl.