This session will serve to present some of the recent developments in the areas of graph theory and of computational and discrete geometry. These two areas of discrete mathematics are particularly relevant, both historically and in the present. Some of the topics that will be discussed revolve around extremal graph theory, random graphs, geometric graphs, and point proximity structures, such as Voronoi diagrams.
En esta sesión se presentarán recientes avances en las áreas de teoría de grafos y de geometría discreta y computacional. Estos dos ámbitos de la matemática discreta tienen una particular relevancia y presencia nacional tanto históricamente como en la actualidad. Algunos de los temas que se tratarán incluyen teoría de grafos extremales y aleatorios, grafos geométricos y estructuras de proximidad de puntos, como los diagramas de Voronoi.
1.A (1.12)
1.B (1.12)
Temporal graphs model time-dependent propagation processes. We study the temporal Stochastic Block Model. Each edge has a unique, randomly chosen timestamp, and connectivity depends on sequences of edges with increasing timestamps. Our goal is to understand the asymptotic behavior of the temporal diameter in the subcritical regime, where the average connections per node are $c \log n$, with $c < 1$. We analyze longest increasing paths and the size of reachable vertex sets.
Joint work with Guillem Perarnau and Gabor Lugosi.
We count unlabelled chordal graphs with with tree-width at most $t$, which are the graphs that can be obtained from an initial vertex by iteratively adding a new vertex connected to all vertices of an existing clique of size at most $t$. In order to do so, we extend Pólya theory and the method of cycle pointing to take into account cycles of cliques.
Joint work with Clément Requilé.
Given a $k$-graph $H$ of size $n$ with an $r$-edge-colouring, we look for a minimum $l$-degree condition that guarantees the existence of a colour-bias perfect matching in $H$, this is, one that has more than $n/rk$ edges in one colour. For each $1\leq l\leq k$ and $r\geq 2$, we determined the minimum $l$-degree threshold that forces a perfect matching of significant colour-bias in an $r$-coloured $k$-graph.
The presented result is joint work with J. Balogh and A. Treglown, and with H. Hàn, R. Lang, J. P. Marciano, M. Pavez-Signé, N. Sanhueza-Matamala and A. Treglown.
A subgraph $H$ of an edge-coloured graph $G$ is rainbow if no two edges of $H$ have the same colour. In this talk we will present a few advances towards decomposing edge-coloured random graphs into small collections of rainbow subgraphs, in a variety of scenarios.
This is joint work with Antônio Kaique, Guilherme Mota, and Walner Mendonça, and with Lyuben Lichev, Jaehoon Kim and Marc Noy.
Given a class $C$ of drawings of (multi-)graphs in the plane, we say that a particular drawing in $C$ is saturated when the addition of any edge to it results in a drawing not included in $C$. In this talk I will focus on $k$-planar drawings, in which each edge is crossed at most $k$ times. In my talk I will introduce a generic framework to determine tight bounds on the minimum number of edges among all $n$-vertex saturated $k$-planar drawings in many natural classes of graph drawings.
Joint work with Steven Chaplick, Irene Parada, Jonathan Rollin, and Torsten Ueckerdt.
Let $S$ be a point set in general position in $\mathbb{R}^d$. The order-$k$ Voronoi diagram of $S$, $V_k(S)$, is a subdivision of $\mathbb{R}^d$ into cells whose points have the same $k$ nearest points of $S$. Sibson's formula expresses a point $Q$ of $S$ as a convex combination of other points of S using ratios of volumes of the intersection of cells of $V_2(S)$ and the cell of $Q$ in $V_1(S)$. We generalize this result to express $Q$ as a convex combination of other points of $S$ using ratios of volumes from Voronoi diagrams of any given order.
Collaborators: Mercè Claverol, Clemens Huemer y Dolores Lara.
In abstract Voronoi diagrams of order $\leq k$, the number of unbounded faces ranges from $k(k+1)$ to $k(2n-k-1)$. This result is shown via a permutation framework that maps unbounded faces to permutations of sites and unbounded edges to switches between adjacent elements in these permutations. This combinatorial approach has further applications in Computational Geometry. Our ongoing work extends the framework by exploring colorings of permutation elements, with the goal of deriving tight inequalities.
Joint work with Evanthia Papadopoulou and Sang Won Bae.
Shortest path problems are fundamental problems in computational geometry. In a general version of the problem the space is subdivided into regions. Each of the regions has a (non-negative) weight associated to it, representing the cost per unit distance of traveling in that region. This variant cannot be solved exactly within the Algebraic Computation Model over the Rational Numbers. In this talk, I will explore some of the most common techniques used to approximate a solution to this problem.