Search

L'objectiu principal d'aquest treball és estudiar el grafó, l'objecte límit per a seqüències de grafs densos convergents sota dues nocions equivalents de convergència, definides, respectivament, a partir de la distància de tall i de les densitats d’homomorfismes. Abordarem els resultats més rellevants que involucren els límits de grafs, teoria desenvolupada fonamentalment per Lovász i Szegedy, així com algunes aplicacions. Crucialment, veurem que l’espai mètric de grafons és compacte i que completa el conjunt de grafs, un fet amb profundes conseqüències en molts problemes extremals de grafs. En particular, examinarem el problema de minimitzar i maximitzar el nombre d’alguns subgrafs, com ara triangles o cicles de llargada 4, a grafs amb una densitat d’arestes donada. El nostre estudi dels límits de grafs anirà precedit per una necessària discussió sobre algunes nocions preliminars de teoria de grafs; concretament, grafs aleatoris i pseudoaleatoris i els lemes de regularitat i de comptatge., El objetivo principal de este trabajo es estudiar el grafón, el objeto límite para secuencias de grafos densos convergentes bajo dos nociones de convergencia, definidas, respectivamente, a partir de la distancia de corte y de las densidades de homomorfismos. Abordaremos los resultados más relevantes que involucran a los límites de grafos, teoría desarrollada fundamentalmente por Lovász y Szegedy, así como algunas aplicaciones. Crucialmente, veremos que el espacio métrico de grafones es compacto y que completa el conjunto de grafos, un hecho con profundas consecuencias en muchos problemas extremales de grafos. En particular, examinaremos el problema de minimizar y maximizar el número de algunos subgrafos, como triángulos o ciclos de longitud 4, en grafos con una densidad de aristas fijada. Nuestro estudio de los límites de grafos irá precedido por una necesaria discusión sobre algunas nociones preliminares de teoría de grafos; concretamente, grafos aleatorios y pseudoaleatorios y los lemas de regularidad y de conteo., The main objective of this thesis is to study the graphon, the limit object for convergent dense graph sequences under two equivalent notions of convergence, defined, respectively, from the cut metric and homomorphism densities. We will explore the principal results involving graph limits, a theory primarily developed by Lovász and Szegedy, as well as some of their applications. Fundamentally, we will see that the graphon metric space is compact and that it is the completion of the set of graphs, a statement with deep consequences in many graph extremal problems. In particular, we will examine the problem of minimizing and maximizing the number of some subgraphs like triangles or 4-cycles in graphs with a given edge density. Our study of graph limits will be preceded by a necessary discussion on some preliminar notions from graph theory, namely random and quasirandom graphs and the regularity and counting lemmas.

We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of map homomorphism that preserves both the combinatorial structure (as a graph homomorphism) and the topological structure of the surface (in particular, orientability and genus). Notions such as the core of a graph and the homomorphism order on cores are then extended to maps. We also develop a purely combinatorial framework for various topological features of a map such as the contractibility of closed walks, which in particular allows us to characterize map cores. We then show that the poset of map cores ordered by the existence of a homomorphism is connected and, in contrast to graph homomorphisms, does not contain any dense interval (so it is not universal for countable posets). Finally, we give examples of a pair of cores with an infinite number of cores between them, an infinite chain of gaps, and arbitrarily large antichains with a common homomorphic image.

© 2024 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license, We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of map homomorphism that preserves both the combinatorial structure (as a graph homomorphism) and the topological structure of the surface (in particular, orientability and genus). Notions such as the core of a graph and the homomorphism order on cores are then extended to maps. We also develop a purely combinatorial framework for various topological features of a map such as the contractibility of closed walks, which in particular allows us to characterize map cores. We then show that the poset of map cores ordered by the existence of a homomorphism is connected and, in contrast to graph homomorphisms, does not contain any dense interval (so it is not universal for countable posets). Finally, we give examples of a pair of cores with an infinite number of cores between them, an infinite chain of gaps, and arbitrarily large antichains with a common homomorphic image., Peer Reviewed, Postprint (published version)

Considerem el següent problema. Donada una família de grafs amb un cert nombre de grafs amb n vèrtexs, volem trobar una representació per a qualsevol graf dins la família fent servir un nombre òptim de bits. És a dir, sigui t el nombre de grafs amb n vèrtexs a la família, volem codificar qualsevol d'aquests grafs fent servir log(t) + o(log(t)) bits, que és el mínim necessari asimptòticament. El primer tipus de famílies que considerem per codificar són diferents tipus de famílies d'arbres, per exemple, arbres ordenats, arbres k-aris i arbres no ordenats. Expliquem dos mètodes per codificar famílies d'arbres. El primer és per a famílies específiques d'arbres i el segon és per a famílies generals d'arbres. A continuació, també considerem les famílies més generals de grafs que siguin tancades per subgrafs induïts i que tinguin separadors petits. Aquestes famílies inclouen grafs planars i qualsevol família de grafs tancada per menors. També presentem una aplicació detallada d'aquesta codificació., Consideramos el siguiente problema. Dada una familia de grafos con un cierto número de grafos de n vértices, queremos encontrar una representación para cualquier grafo dentro de la familia utilizando un número de bits optimo. Es decir, sea t el número de grafos de n vértices en la familia, queremos codificar cualquiera de dichos grafos usando log(t) + o(log(t)) bits, que es el mínimo necesario asintóticamente. El primer tipo de familias que consideramos codificar son distintos tipos de familias de árboles, por ejemplo, árboles ordenados, árboles k-arios y árboles no ordenados. Explicamos dos métodos para codificar familias de árboles. El primero es para familias específicas de árboles y el segundo es para familias generales de árboles. A continuación, también consideramos las familias más generales de grafos que son cerradas por subgrafos inducidos y tienen separadores pequeños. Estas familias incluyen grafos planares y cualquier familia de grafos cerrada por menores. También presentamos una aplicación detallada de esta codificación., We consider the following problem. Given a family of graphs with a certain number of n-vertex graphs, we want to find a representation for any graph within the family using an information-theoretical number of bits. That is to say, if there are a certain number of n-vertex graphs t in the family, then, we want to encode any of such graphs using log(t) + o(log(t)) bits, which is the asymptotically minimum needed. The first type of families we consider encoding are different types of tree families, for instance, ordered trees, k-ary trees and unordered trees. We explain two methods for encoding such families. The first one for specific families of trees and the second one for general families of trees. Then, we also consider the more general families of graphs which are closed under induced sub-graphs and have small separators. These families include planar graphs and any minor-closed family of graphs. We also present a detailed implementation of such encoding.

This thesis focuses on positional games. Positional games is a branch of mathematics that studies two- player games of perfect information. Maker-Breaker positional games will be of special interest, and more precisely, biased Maker-Breaker games, introduced by Chvatal and Erdös, will be widely studied. The main interest in the study of biased Maker-Breaker games is to determine the so-called threshold bias. In this thesis, a study of Maker-Breaker games in general is done, and finally some specific games are analysed. In the last chapter, the new result of the thesis is presented, giving a strategy for the Schur s game, that improves the existing bound for the critical bias of this game.

We prove that the ribbon graph polynomial of a graph embedded in an orientable surface is irreducible if and only if the embedded graph is neither the disjoint union nor the join of embedded graphs. This result is analogous to the fact that the Tutte polynomial of a graph is irreducible if and only if the graph is connected and non-separable., Peer Reviewed, Postprint (author's final draft)

Aquest document està dedicat a la història, les motivacions i algunes solu-cions alproblema dels codis de Gauss.Una corba tancada al pla pot contenir punts d’autointersecció; en suposem unnombre finit, suposem els talls no tangencials i suposem que la corba recorre cadapunt del pla un màxim de dos cops. Si etiquetem els punts de tall amb símbols diferents,triem un punt a la corba, un sentit, i, en recórrer la corba, anotem la seqüència desímbols que anem trobant, aleshores generem una paraula que s’anomena genèricamentcodi de Gauss.El problema dels codis de Gauss és el de caracteritzar quines són les possiblesparaules generades per corbes al pla. Com veurem, les solucions al problema demanengirar la cantonada., Peer Reviewed, Postprint (published version)

There are many models of physical systems based in unsigned graph theory, however there are some systems that cannot be modelled by unsigned graphs and that is the reason of signed graph states models. For these models, there are useful objects as partition functions, and systems that share these objects have some intrinsic properties in common, so it is interesting to build these models in order to relate those systems (with vertex switching invariance or equivalent knot invariance)., Outgoing

Given a set of size $n$ and a positive integer $k

We construct a new polynomial invariant for signed graphs, the trivariate Tutte polynomial, which contains among its evaluations the number of proper colorings and the number of nowhere-zero flows. In this, it parallels the Tutte polynomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. While the Tutte polynomial of a graph is equivalently defined as the dichromatic polynomial or Whitney rank polynomial, the dichromatic polynomial of a signed graph (defined more widely for biased graphs by Zaslavsky) does not, by contrast, give the number of nowhere-zero flows as an evaluation in general. The trivariate Tutte polynomial contains Zaslavsky's dichromatic polynomial as a specialization. Furthermore, the trivariate Tutte polynomial gives as an evaluation the number of proper colorings of a signed graph under a more general sense of signed graph coloring in which colors are elements of an arbitrary finite set equipped with an involution., Peer Reviewed, Postprint (published version)

Given a countably infinite hypergraph $\mathcal R$ and a finite hypergraph $\mathcal A$, the \emph{big Ramsey degree} of $\mathcal A$ in $\mathcal R$ isthe least number $L$ such that, for every finite $k$ and every $k$-colouring of the embeddings of $\mathcal A$ to $\mathcal R$, there exists an embedding $f$ from $\mathcal R$ to $\mathcal R$ such that all the embeddings of $\mathcal A$ to the image $f(\mathcal R)$ have at most $L$ different colours. We describe the big Ramsey degrees of the random countably infinite 3-uniform hypergraph, thereby solving a question of Sauer. We also give a new presentation of the results of Devlin and Sauer on, respectively, big Ramsey degrees of the order of the rationals and the countably infinite random graph.Our techniques generalise (in a natural way) to relational structures and give new examples of Ramsey structures (a concept recently introduced by Zucker with applications to topological dynamics)., Peer Reviewed, Postprint (published version)

© 2017 Elsevier Ltd. We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well., Postprint (updated version)

We present a unified framework to asymptotically count the number of sets, with a given cardinality, free of certain configurations. This is done by combining the hypergraph containers methodology joint with arithmetic removal lemmas. Several applications involving linear configurations are described, as well as some applications in the random sparse setting., Postprint (author's final draft)

In this work we explain and prove the graph removal lemma, both in its dense and sparse cases, and show how these can be applied to finite groups to obtain arithmetic removal lemmas. We show how the concept of regularity plays a crucial role in the proof of the removal lemma. We explain the motivation behind the sparse case, and the importance of pseudorandom graphs in sparse versions of the removal lemma. Finally, we show how the removal lemma, both in its graph and arithmetic versions, can be used to prove Roth's theorem, that is, the existence of 3-term arithmetic progressions in any dense subset of the natural numbers.

The final publication is available at link.springer.com, We prove a removal lemma for systems of linear equations over finite fields: let X1, . . . , Xm be subsets of the finite field Fq and let A be a (k × m) matrix with coefficients in Fq and rank k; if the linear system Ax = b has o(q m-k ) solutions with xi ¿ Xi , then we can destroy all these solutions by deleting o(q) elements from each Xi . This extends a result of Green [Geometric and Functional Analysis 15(2) (2005), 340–376] for a single linear equation in abelian groups to systems of linear equations. In particular, we also obtain an analogous result for systems of equations over integers, a result conjectured by Green. Our proof uses the colored version of the hypergraph Removal Lemma., Supported as project 1M0545 by Czech Ministry of Education. Supported by the Catalan Research Council under project 2005SGR0258. Supported by the Spanish Research Council under project MTM2005-08990-C01-C, Peer Reviewed, Postprint (author's final draft)

This thesis presents some contributions in additive combinatorics and arithmetic Ramsey theory. More specifically, it deals with the interaction between combinatorics, number theory and additive combinatorics. This area saw a great improvement with the Szemerédi Regularity Lemma and some of the results that followed. The Regularity Lemma and its consequences have become a widely used tool in graph theory, combinatorics and number theory. Furthermore, its language and point of view has deeply changed the face of additive number theory, a fact universally acknowledged by the Abel award given to Szemerédi in 2012. One of the main reasons for the prize has been Szemerédi's theorem, a result regarding the existence of arbitrarily long arithmetic progressions in dense sets of the integers, the proof of which uses the Regularity Lemma in a key step. One of the earlier consequences of the Regularity Lemma was the Removal Lemma for graphs that was used by Ruzsa and Szemerédi to show Roth theorem, regarding the existence of 3-term arithmetic progressions in dense sets of the integers, in a combinatorial way. The Removal Lemma states that in any graph K with few copies of a subgraph, say a triangle, we can remove few edges from K so that the result contains no copy of the subgraph. This has become a key tool in the applications of the so-called Regularity Method, which has extensive literature in combinatorics, graph theory, number theory and computer science. In 2005 Green introduced a regularity lemma for Abelian groups as well as an algebraic removal lemma. The removal lemma for groups states that, for a given finite Abelian group G, if there are o(|G|^3) solution to x+y+z+t=0 with the variables taking values in S, a subset of G, then we can remove o(|G|) elements from S to make the set S solution-free. The main contributions of this work corresponds to extensions of the removal lemma for groups to either more general contexts, like non-necessary Abelian finite groups, or t, Postprint (published version)

The Szemerédi Regularity Lemma (SzRL) was introduced by Endré Szemerédi in his celebrated proof of the density version of Van der Waerden Theorem, namely, that a set of integers with positive density contains arbitrarily long arithmetic progressions. The SzRL has found applications in many areas of Mathematics, including of course Graph Theory and Combinatorics, but also in Number Theory, Analysis, Ergodic Theory and Computer Science. One of the consequences of the SzRL are the so-called `Counting Lemma' and `Removing Lemma', which roughly says that a sufficiently large graph G which contains not many copies of a fixed graph H can be made H-free by removing a small number of edges. Recently Ben Green gave an algebraic version of both, the SzRL and the Removal Lemma for groups. In this algebraic version the structural result fits into the algebraic structure in terms of subgroups. On the other hand, the Removal Lemma has its algebraic counterpart in the estimation of the number of solutions of equations in groups. The purpose of this Master Thesis is to give a detailed account on the SzRL and some of its applications, particularly to Additive Combinatorics. We particularly focuss on the consequences of the SzRL related to the Counting Lemma. By combining the version by Alon and Shapira of the directed version of the SzRL with the version of Simonovits for edge-colored graphs, we state and prove a Counting Lemma for arc-colored directed graphs. The methods used by Green heavily rely on Fourier Analysis, and as such, his results are applicable only to Abelian groups. By using our general version of the Counting Lemma we prove a generalization of Ben Green's Removal Lemma which is applicable to finite groups, non necessarily abelian.