Resumen de Random combinatorial structures with low dependencies: existence and enumeration
Guillem Perarnau Llobet
En aquesta tesi s'estudien diferents problemes en el camp de la combinatòria i la teoria de grafs, utilitzant el mètode probabilístic. Aquesta tècnica, introduïda per Erd?s , ha esdevingut una eina molt potent per tal de donar proves existencials per certs problemes en diferents camps de les matemàtiques on altres mètodes no ho han aconseguit. Un dels seus principals objectius és l'estudi del comportament de les variables aleatòries. El cas en que aquestes variables compten el nombre d'esdeveniments dolents que tenen lloc en una estructura combinatòria és de particular interès. La idea del Paradigma de Poisson és estimar la probabilitat que tots aquests esdeveniments dolents no succeeixin a la vegada, quan les dependències entre ells són febles o escasses. En tal cas, aquesta probabilitat s'hauria de comportar de forma similar al cas on tots els esdeveniments són independents. El Lema Local de Lovász o la Desigualtat de Suen són exemples d'aquesta idea. L'objectiu de la tesi és estudiar aquestes tècniques ja sigui proveint-ne noves versions, refinant-ne les existents per casos particulars o donant-ne noves aplicacions. A continuació s'enumeren les principals contribucions de la tesi. La primera part d'aquesta tesi estén un resultat d' Erd?s i Spencer sobre transversals llatins. Els autors proven que qualsevol matriu d'enters on cap nombre apareix massa vegades, admet un transversal on tots els nombres són diferents. Això equival a estudiar els aparellaments multicolors en aresta-coloracions de grafs complets bipartits. Sota les mateixes hipòtesis que, es donen resultats sobre el nombre d'aquests aparellaments. Les tècniques que s'utilitzen estan basades en l'estratègia desenvolupada per Lu i Székely. En la segona part d'aquesta tesi s'estudien els codis identificadors. Un codi identificador és un conjunt de vèrtexs tal que tots els vèrtexs del graf tenen un veïnatge diferent en el codi. Aquí s'estableixen cotes en la mida d'un codi identificador mínim en funció dels graus i es resol parcialment una conjectura de Foucaud et al.. En un altre capítol, es mostra que qualsevol graf suficientment dens conté un subgraf que admet un codi identificador òptim. En alguns casos, provar l'existència d'un cert objecte és trivial. Tot i així, es poden utilitzar les mateixes tècniques per obtenir resultats d'enumeració. L'estudi de patrons en permutacions n'és un bon exemple. A la tercera part de la tesi es desenvolupa una nova tècnica per tal d'estimar el nombre de permutacions d'una certa llargada que eviten còpies consecutives d'un patró donat. En particular, es donen cotes inferiors i superiors per a aquest nombre. Una de les conseqüències és la prova de la conjectura CMP enunciada per Elizalde i Noy així com nous resultats en el comportament de la majoria dels patrons. En l'última part de la tesi s'estudia la Conjectura Lonely Runner, enunciada independentment per Wills i Cusick i que té múltiples aplicacions en diferents camps de les matemàtiques. Aquesta coneguda conjectura diu que per qualsevol conjunt de corredors que corren al llarg d'un cercle unitari, hi ha un moment on tots els corredors estan suficientment lluny de l'origen. Aquí, es millora un resultat de Chen ampliant la distància de tots els corredors a l'origen. També s'estén el teorema del corredor invisible de Czerwi?ski i Grytczuk .
