Aprèn - Guillem Perarnau Llobet

En aquest treball abordem els problemes de mostreig i comptatge aproximat en models d'espins en grafs, recopilant els resultats més significatius de l'àrea i introduïnt els coneixements previs necessaris del camp de la física estadística. En particular, prestem especial atenció als mètodes generals de disseny d'algorismes desenvolupats per Weitz i Barvinok, així com els avenços recents en matèria de comptatge i mostreig de conjunts independents de mida donada. Així mateix, discutim com es podrien adaptar aquests arguments als problemes de comptatge i mostreig de coloracions amb les mides de cada color fixades, explicant amb detall la línia de recerca actual que estem duent a terme.

En este trabajo abordamos los problemas de muestreo y conteo aproximado en modelos de espines en grafos, recopilando los resultados más significativos del campo e introduciendo el conocimiento previo necesario del área de la física estadística. En particular, prestamos especial atención a los métodos generales de diseño de algorismos desarrollados por Weitz y Barvinok, así como a los avances recientes en cuanto al conteo y muestreo de conjuntos independientes de un tamaño dado. Así mismo, discutimos cómo se podrían adaptar estos argumentos al problema de contar y muestrear coloraciones con el tamaño de cada color fijo, explicando en detalle la línea de investigación que estamos llevando a cabo actualmente.

We approach the problems of approximate sampling and counting in spin models on graphs, surveying the most significant results in the area and introducing the necessary background from statistical physics. We pay particular attention to the general algorithm design frameworks developed by Weitz and Barvinok, as well as to the newer results on counting and sampling independent sets of given size. In addition, we discuss the adaptation of the arguments behind these results to count and sample colorings with fixed color sizes, explaining in detail the current research line we are undertaking.

A covering hyperplane method and applications

Master thesis

Coderch Sendrós, Guillem

Tutor / Supervisor: Serra Albó, Oriol; Perarnau Llobet, Guillem

Publication date: 2023

School of Mathematics and Statistics (FME)

Access to the full text

Slow polynomial mixing of Glauber dynamics at criticality

Master thesis

Hernández Mus, Adrián

Tutor / Supervisor: Perarnau Llobet, Guillem

Publication date: 2023

School of Mathematics and Statistics (FME)

View detail Access to the full text

Study of random w-trees and automaton synchronization

Master thesis

Genda, Attila

Tutor / Supervisor: Perarnau Llobet, Guillem

Publication date: 2023

School of Mathematics and Statistics (FME)

View detail Access to the full text

En aquest treball s'han investigat numèricament i analíticament les propietats de sincronització de paraules repetides en autòmats finits deterministes. Es presenta un algorisme polinomi O(n^2) per trobar paraules curtes de sincronització basades en arbres w. L'algorisme és capaç de trobar paraules sincronitzadores de longitud proporcional a (n log(n))^0.5 amb autòmats de mida de fins a uns quants centenars de milers d'estats. També es presenten resultats experimentals sobre l'alçada dels arbres w que mostren que l'alçada mitjana de l'arbre és de O((n/k)^0.5). A més, en aquest estudi es porta a terme el modelatge del procés de sincronització aleatori de DFA per cadenes de Markov. També es presenten tres estimacions diferents justificades experimentalment per a la longitud mitjana de la paraula de sincronització més curta, que indiquen que la longitud de la paraula de reinici més curta és proporcional a l'arrel quadrada de la mida de l'autòmat.

En este trabajo se investigaron numérica y analíticamente las propiedades de sincronización de palabras repetidas en autómatas finitos deterministas. Se presenta un algoritmo polinomial O (n ^ 2) para encontrar palabras sincronizadas cortas basadas en árboles w. El algoritmo es capaz de encontrar palabras de sincronización de longitud proporcional a (n log(n))^0.5 con autómatas de tamaño de unos pocos cientos de miles de estados. También se presentan resultados experimentales sobre la altura de los árboles w los cuales muestran que la altura media de los árboles es de O((n/k)^0.5). Además, en este estudio se lleva a cabo el modelado del proceso de sincronización aleatoria DFA por cadenas de Markov. También se presentan tres estimaciones diferentes justificadas experimentalmente para la longitud media de la palabra de sincronización más corta, lo que indica que la longitud de la palabra de reinicio más corta es proporcional a la raíz cuadrada del tamaño del autómata.

The synchronization properties of repeated words on deterministic finite automata were investigated numerically and analytically in this work. A polynomial O(n^2) algorithm for finding short synchronizing words based on w-trees is presented. The algorithm is capable of finding synchronizing words of length proportional to (n log(n))^0.5 with automata of size up to a few hundred thousand states. Experimental results on the height of w-trees is also presented showing that the mean tree height is of O((n/k)^0.5). Furthermore, the modeling of the random DFA synchronization process by Markov chains is carried out in this study. Three different experimentally justified estimates for the mean shortest synchronizing word length are presented as well indicating that the shortest resetting word length is proportional to the square root of the automaton size.