Noticias en español
Recent progress on tree packings.
Abstract:We say that a graph H decomposes a graph G if the edges of G can be partitioned into edge-disjoint copies of H. In 1976, Ringel conjectured that any tree of order n+1 decomposes the complete graph on 2n+1 vertices. Recently Montgomery, Pokrovskiy and Sudakov presented a proof of this conjecture for large n. In this talk, we will study the techniques used by Montgomery, Pokrovskiy and Sudakov to prove Ringel’s conjecture.
Read MoreEl grupo de automorfismos de los grafos de fichas de los bipartitos completos.
Abstract: Sea $G$ una gráfica simple de $n$ vértices y $k$ un entero tal que $1\leq k\leq n-1$. El grafo de $k$-fichas, $F_k(G)$, de $G$ es el grafo cuyos vértices son los $k$-conjuntos de vértices de $G$, y donde dos de estos $k$-conjuntos son adyacentes si su diferencia simétrica es una arista de $G$. En esta plática hablaremos sobre la relación que existe entre los grupos de automorfismos de $G$ y de $F_k(G)$. Además, daremos un bosquejo de la prueba para determinar el grupo de automorfismos de $F_k(K_{m,n})$, donde $K_{m,n}$ denota al grafo bipartito completo. En esta familia de grafos...
Read MoreEmpaquetamiento óptimo de árboles de grado máximo acotado.
Abstract: En 1976, Gyárfás y Lehel conjeturaron que si T_1,…, T_n es una secuencia de árboles tal que T_i tiene i vértices, entonces el grafo completo en n vértices K_n tiene una descomposición en T_1,…, T_n. Recientemente, Joos, Kim, Kühn y Osthus [1] probaron esta conjetura para árboles de grado máximo acotado. En este seminario vamos a estudiar las técnicas utilizadas en la demostración de este resultado. En especial, veremos una aplicación del método de absorción iterativo. [1] Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus, Optimal packings of bounded degree trees. J....
Read MoreStructural properties in hypercubes.
Abstract: In this talk we review some structural questions on subgraphs of the hypercube of dimension n. We present a simpler proof of Huang’s 2019 result that any subgraph of $H_n$ on more than half the number of vertices has a vertex of degree at least $\sqrt{n}$. We present some strengthening of the result, and we observe a connection to an older question of Erdos who asked: how many edges of $H_n$ one should take to guarantee existence of a 4-cycle.
Read MoreThe Hamilton Compression of Highly Symmetric Graphs.
Abstract: The relationship between symmetry and Hamiltonicity in graphs has gained much attention in recent years but is still not so well understood, this can be seen, for example, in the colliding conjectures of Lovász and Babai. To try to shed some light on this relationship, we introduce a measure of how symmetric the Hamilton cycles in a graph can be. We say that a Hamilton cycle C=x_1,…,x_n in a graph is k-symmetric, if the mapping x_i to x_(i+n/k) for all i=1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices...
Read MoreÁrboles generadores en grafos aleatorios III
Abstract: En los dos últimos seminarios vimos algunas técnicas utilizadas para encajar árboles con muchas hojas apartadas o con muchos caminos de largo medio en el grafo aleatorio. Finalizamos esta serie de seminarios sobre el artículo Spanning trees in random graphs de Montgomery, estudiando cómo se utiliza el método de absorción para encajar árboles con muchos caminos largos en el grafo aleatorio.
Read More