2026-04-13T01:14:31Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4456742026-01-15T10:59:44Zcom_2072_1033col_2072_452951

Further results on the chromatic number of random Borsuk graphs Acitores Montero, Álvaro Àrees temàtiques de la UPC::Matemàtiques i estadística Graph theory Combinations Random graph Borsuk Chromatic number Simplicial complex Stereographic projection Poisson point process. Grafs, Teoria de Combinacions (Matemàtica) Classificació AMS::05 Combinatorics::05C Graph theory Classificació AMS::60 Probability theory and stochastic processes::60C05 Combinatorial probability Els vèrtexs d’un graf aleatori de Borsuk són $n$ punts aleatoris uniformes sobre l’esfera unitària $S^d$, i es connecten amb una aresta si l’angle entre ells és més gran que $\pi - \alpha$. En aquest treball, ampliem els resultats ja coneguts sobre el seu nombre cromàtic quan $n$ tendeix a infinit. Existeixen dues constants $\lambda_d$, $C$, que depenen només de la dimensió, tals que sempre que es compleixi $C\left(\frac{\log(n)}{n}\right)^{1/d} \leq \alpha \leq \lambda_d$, el nombre cromàtic és $d+2$ amb probabilitat 1. Existeix una altra constant $C_1$ tal que si $\alpha \leq C_1\left(\frac{\log(n)}{n}\right)^{1/d}$, el nombre cromàtic és menor o igual que $d+1$. La nostra contribució és mostrar que existeix una constant $C_2$ tal que el nombre cromàtic és més gran que $d+1$ amb probabilitat 1 per algun $\alpha \geq C_2\left(\frac{1}{n}\right)^{1/d}$. Utilitzarem mètodes probabilístics i topològics Los vértices de un Borsuk random graph son $n$ puntos aleatorios uniformes sobre la esfera unitaria $S^d$, y se toma una arista entre dos vértices si el ángulo que definen es mayor que $\pi - \alpha$. Aquí extendemos los resultados ya conocidos sobre su número cromático cuando $n$ tiende a infinito. Existen dos constantes $\lambda_d$, $C$, que dependen únicamente de la dimensión, tales que siempre que se cumpla $C\left(\frac{\log(n)}{n}\right)^{1/d} \leq \alpha \leq \lambda_d$, el número cromático es $d+2$ con probabilidad 1. Existe otra constante $C_1$ tal que si $\alpha \leq C_1\left(\frac{\log(n)}{n}\right)^{1/d}$, el número cromático es menor o igual que $d+1$. Nuestra contribución consiste en mostrar que existe una constante $C_2$ tal que el número cromático al menos $d+1$ con probabilidad 1 para algún $\alpha \geq C_2\left(\frac{1}{n}\right)^{1/d}$. Utilizaremos métodos probabilísticos y topológicos The vertices of a Borsuk random graph are $n$ uniform random points on the unit sphere $S^d$, and we take an edge between 2 vertices if their opening angle is bigger than $\pi-\alpha$. Here we extend the results already known about its chromatic number as $n$ tends to infinity. There exist 2 constants $\lambda_d$, $C$, depending only in the dimension such that whenever $C\left(\frac{\log(n)}{n}\right)^{1/d}\leq\alpha\leq \lambda_d$, the chromatic number is $d+2$ with probability 1. There exist another constant $C_1$ such that if $\alpha\leq C_1\left(\frac{\log(n)}{n}\right)^{1/d}$ the chromatic number is at most $d+1$. Our contribution is to show that there exist a constant $C_2$ such that the chromatic number is at least $d+1$ with probability 1 for some $\alpha\geq C_2\left(\frac{1}{n}\right)^{1/d}$. We will use probabilistic and topological methods Outgoing 2025-05-26 Bachelor thesis http://creativecommons.org/licenses/by-nc-nd/4.0/ Open Access Attribution-NonCommercial-NoDerivs 4.0 International Universitat Politècnica de Catalunya