Seminários passados – segundo semestre/2015

Path Decompositions of Graphs
Palestrante: Fábio Botler (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 23/10 às 14:00.
Resumo:
Given two graphs \(H\) and \(G\), an \(H\)-decomposition of \(G\) is a set of pairwise edge-disjoint copies of \(H\) in \(G\) that cover the edge-set of \(G\). Dor and Tarsi (1997) proved that the \(H\)-decomposition problem is NP-complete whenever \(H\) is connected and has at least 3 edges. In 2006, Barát and Thomassen posed the following conjecture: for each tree \(T\), there exists a natural number \(k_T\) such that, if \(G\) is a \(k_T\)-edge-connected graph and \(|E(G)|\) is divisible by \(|E(T)|\), then \(G\) admits a \(T\)-decomposition. We proved that this conjecture holds in the special case \(T\) is a path. In this talk we give an overview of this proof and discuss related conjectures and some partial results. This is a joint work with G. O. Mota, M. T. I. Oshiro, and Y. Wakabayashi.

Monochromatic Cycle Partitioning
Palestrante: Richard Lang (U. Chile)
Onde e quando: Auditório NUMEC, sexta-feira 23/10 às 15:20.

Resumo:
Given an arbitrary edge-colouring of the complete graph \(K_n\) with \(r\) colours, how many monochromatic cycles are needed to partition its vertices? Here single edges and vertices count as cycles as well. It is not trivial that this number is independent of the size of \(n\). This, however, was shown in a landmark paper by Erdos, Gyarfas and Pyber in 1991. They proved that \(K_n\) can be partitioned into \(25r^2 \log r\) monochromatic cycles and conjectured that this can be brought down to \(r\) cycles. The conjecture has been recently disproved, but it is believed that it was not too far off the mark.
The area of Monochromatic Cycle Partitioning has spawned many interesting results and methods, and appears to be undergoing a surge of activity as well as a geographic expansion of those working on it. This talk is meant to give a short introduction to the topic.

Transversals of longest paths and longest cycles
Palestrante: Juán Gutiérrez (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 16/10 às 14:00.

Resumo:
For a graph G, let lct(G) be the minimum cardinality of a set of vertices of G that intersects every longest cycle of G and define lpt(G) analogously for longest paths instead of longest cycles. Thomassen proved that for every graph, lct(G) <= n/3; more recently Rautenbach and Sereni proved that lpt(G) < n/4, where n is the order of G.

De Rezende, Fernandes, Martin, Wakabayashi proved that for 2-trees lpt(G) = 1, and Ehrenmuller, Fernandes and C.G. Heise proved same result for partial 2-trees. In this talk, we will show that, if G is a 3-tree, then lpt(G) <= 2 and lct(G) = 1. Joint work with Cristina G. Fernandes and Julia Ehrenmuller.

Packing minor-closed families of graphs
Palestrante: Silva Messuti (Universidade de Hamburgo)
Onde e quando: Auditório NUMEC, sexta-feira 9/10 às 14:00.

Resumo:
Motivated by a conjecture of Gyárfás, recently Böttcher, Hladký, Piguet, and Taraz showed that every collection \(T_1,\dots,T_n\) of trees on~\(n\) vertices with \(\sum_{i=1}^ne(T_i)\leq {n\choose 2}\) and with bounded maximum degree can be packed into the complete graph on \((1+o(1))n\) vertices.  We generalise this result where we relax the restriction of packing families of trees to families of graphs from any given non-trivial minor-closed class of graphs.

Generalized Gram relations for polyhedra, and the combinatorics and number theory behind them.
Palestrante: Sinai Robins (Brown University)
Onde e quando: Auditório NUMEC, sexta-feira 9/10 às 15:20.

Resumo:
How do we extend the 2-dim’l familiar fact that the sum of the angles of a triangle equals \(\pi\) to higher dimensional objects? We begin with a natural discretization of the volume of a spherical polytope, and define certain natural analogues of theta functions – called cone theta functions – from first principles. These functions help us analyze the structure of spherical polytopes.

It turns out that we can obtain precise asymptotics of the cone theta function attached to any simplicial polyhedral cone, near a rational ‘cusp’, and we use these asymptotics to give new extensions of the Gram-relations for the solid angles of faces of a simple rational polytope. Hence the combinatorics of polytopes is generalized by using some number theory.

We’ll include lots of pictures and aim most of the talk at beginning graduate students.

A rainbow Erdos–Rothschild-type probelm for edge-colorings of graphs
Palestrante: Hanno Lefmann (TU Chemnitz)
Onde e quando: Auditório NUMEC, sexta-feira 25/09 às 14:00.

Resumo:
We consider a multicolored version of a question first posed by Erdos and Rothschild in 1974.  Given a fixed number \(r\) of colors and a fixed graph \(F\), we look for \(n\)-vertex graphs \(H\), where \(n\) is large, that allow the maximum number of edge-colorings with \(r\) colors with no rainbow-copy of \(F\), i.e., there is no copy of \(F\) in \(H\) with all edges of \(F\) colored differently.  In particular, we consider as fixed forbidden graphs \(F\) rainbow-colored complete graphs \(F=K_{k+1}\) on \((k+1)\) vertices.  Among others, such as discussing related results and problems, for \(r\geq r_0(k)\) we determine the unique extremal graph \(H\) on \(n\) vertices, \(n\) large, for this problem of a forbidden rainbow \(F=K_{k+1}\).  Tools in the arguments are stability in graphs in the sense of Simonovits and the regularity lemma of Szemerédi.  This is joint work with Carlos Hoppen (UFRGS Porto Alegre) and Knut Odermann (TU Chemnitz).

Better bounds for planar sets avoiding unit distances
Palestrante: Fernando Mário de Oliveira Filho (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 21/08 às 14:00.

Resumo:
A conjecture of Erdős asserts that the maximum fraction of the Euclidean plane that can be covered by a set of points containing no two points at distance one is less than \(1/4\). I will show that this maximum fraction is at most \(0.258795\) by combining ideas from harmonic analysis and linear programming to provide an extension of the Lovász theta number to the infinite unit-distance graph on the plane. I will also discuss a related result, namely that sets that avoid the unit distance and are composed of blocks of small diameter have density less than \(1/4\).

(This is joint work with T. Keleti, M. Matolcsi, and I.Z. Ruzsa, arXiv link.)

A probabilistic tool applied to a graph coloring problem
Palestrante: Carlos Hoppen (UFRGS)
Onde e quando: Auditório NUMEC, sexta-feira 7/08 às 14:00

Resumo:
We consider graphs with a large number of edge-colorings that avoid a class of patterns. This is motivated by a multicolored variant, due to Balogh, of a problem of Erdős and Rothschild. To obtain our results, we use a probabilistic argument to prove that, in every graph with a large number of edges, there is an almost spanning subgraph which contains a large number of subgraphs of any bounded degree sequence satisfying a density condition.

Transversal planes to convex sets in \(R^d\)
Palestrante: Jorge Ramírez Alfonsín (U. de Montpellier)
Onde e quando: Auditório NUMEC, sexta-feira 7/08 às 15:30

Resumo:
Let \(k,d,\lambda\ge 1\) be integers with \(d\ge \lambda\). What is the maximum positive integer \(n\) such that every set of \(n\) points in \(R^d\) has the property that the convex hulls of all \(k\)-sets have a transversal \((d-\lambda)\)-plane ? What is the minimum positive integer \(n\) such that every set of \(n\) points in general position in \(R^d\) has the property that the convex hulls of all \(k\)-sets do not have a transversal \((d-\lambda)\)- plane? In this talk, we investigate these two questions. We define a special Kneser hypergraph and, by using some geometric and topological results, we relate our second question to the chromatic number of such hypergraphs. Moreover, we establish a connection (when \(\lambda = 1\)) with Kneser’s conjecture, first proved by Lovász.