COMBINATORIAL ANALYSIS

Author: ELIZALDE TORRENT SERGI.
Year: 2003.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: SALA D'ACTES DE LA FME.
Place of preparation: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Author: HIDALGO DOBLADO MARIA JOSE.
Year: 2003.
University: SEVILLA [www.us.es].
Place of defense: FACULTAD DE MATEMATICAS.
Place of preparation: FACULTAD DE MATEMATICAS.

Summary: The main objectives of the thesis is the formalization of mathematical theories in automated reasoning systems, formal verification algorithms such theories and conducting such verification so that the evidence in the system essentially correspond with the usual. To that end, we chose a system of reasoning, PVS, and two theories as objects of formalization, programming logic preposicional and formal analysis of concepts. Moreover, the desire for a natural reasoning on the specifications leads to the problem of choosing the basic rates in the building specifications. In this sense, data types formally elected to represent the concepts of the theories have to be the closest possible to such notions. In both cases, the type closest to the object you wish to be represented in the language of PVS is the kind of finite sets. However, although the choice of the joint PVS as a basis for type specifications enables smart on the same reasoning, there is the problem that these specifications are not evaluable. The solution we are proposing to this problem is methodological. To this end we have established PVS in a generic framework in which connect different specifications, formally defined when two different specifications correspond to the same concept. Within that framework, we have studied the properties of a general nature which are conserved between specifications of the same algorithm. This has enabled us to work on two levels. On the one hand, the reasoning perform at the level where the distance between an idea and its formal specification is minimal, although it is not assessable. And secondly, only to certain specifications, obtain other evaluable for the same concept, and with the same properties (including ownership of a correction algorithm). In connection with the theories considered: * We have made a formalization of programming logic preposicional, testing the equivalence between the different interpretations of semantic software. Additionally, we tested the completeness strong resolution SLD, using an abstract representation of the factors involved in the resolution process. Finally, we have built refinements evaluable of algorithms proportional logic programming. * We have formalized the theory of formal analysis of concepts, in the abstract and we got evaluable refinements of the algorithms that theory.

Author: GIMENEZ LLACH OMER.
Year: 2004.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: SALA D'ACTES FME.
Place of preparation: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Summary: This thesis is a contribution to the study of asymptotic enumeration and the complexity of evaluating the Tutte polynomial on certain families of graphs and matroids. The main result is the obtention of a complete asymptotic expression for the number of labelled planar graphs using methods of singularity analysis. As a consequence of our work we obtain the limit probability distribution of many interesting parameters of random planar graphs on n vertices, like the number of edges or the number of connected components. With respect to our contribution to the study of the computational complexity of evaluating the Tutte polynomial, we focus on three particular families of structures: the class of bounded clique-width graphs (a generalization of bounded tree-width graphs) and two sub-classes of transversal matroids, multi-path matroids, which we introduce generalizing the class of lattice-path matroids, and bicircular matroids. We prove that evaluating the Tutte polynomial for bicircular matroids is #P-hard in every point of the plane except for two lines and an hyperbola. The situation is the opposite for multi-path matroids, for which we show algorithms that compute the Tutte polynomial in polynomial time. As for bounded clique-width graphs, we show how to compute their Tutte polynomial in sub-exponential time, a strong indication that the problem is not #P-hard.

Author: MOLINERO ALBAREDA XAVIER.
Year: 2005.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: SALA D'ACTES DE L'FME.
Place of preparation: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Summary: There are four distinct but closely related problems about the generation of combinatorial objects: drawing (generate a random object of a given combinatorial class and size), ranking (compute the rank of a given object from a combinatorial class, according to some previously fixed order), unranking (generate a combinatorial object whose rank and size are given, according to a fixed specific order) and iteration or exhaustive generation (generate all objects of a given combinatorial class and size, according to some fixed order). In this thesis we combine some well-known principles and novel ideas in a generic framework to design efficient solutions to the last three problems. Our algorithms are generic in the sense that their input considers a finite specification of the combinatorial class whose objects we deal with. We provide algorithms for unranking and ranking objects of size n with average cost O(n sqrt n) for the lexicographic order and O(n log n) for the boustrophedonic order. In the case of iterative classes (classes where recursion is not used to specify them), the cost is Theta(n). Furthermore, we have also studied several heuristics to improve the performance of the unranking algorithms, and the probability distribution of the cost of unranking labelled classes with lexicographic ordering. For the iteration problem, we have designed algorithms with constant amortized cost for a large family of admissible classes, including the most interesting classes (we call them superexpoentiallabelled admissible classes, and superpolynomial unlabelled admissible classes). We have also introduced several techniques (e.g., the use of finger pointers) to improve the performance. The flexibility of our generic algorithms makes them attractive for rapid prototyping and for their inclusion in general combinatorial libraries, like the COMBSTRUCT package for MAPLE or the MUPAD-CombINAT package for MUPAD.

Author: BARAJAS TOMAS JAVIER.
Year: 2006.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: SALA D'ACTES FME.
Place of preparation: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Summary: The general problem of finding the chromatic number of a given graph is as old as graph theory itself. An important part of the contemporary concepts or graph theory arose from the different attempts to solve the four-color problem, one of the most famous problems in the area. Problems related with graph colorings are still an active and prolific research area, see for instance the book of Jensen and Toft {\it Graph Coloring Problems} \cite{jt}, where the authors describe the state--of--the--art of more than two hundred open problems in the area. In particular, the problem of finding the chromatic number of the so--called distance graphs is mentioned in this book. This problem is one of the main motivations of the research developed in this thesis. Distance graphs and circulant graphs are Cayley graphs (graphs with a transitive and regular group of automorphisms) of cyclic groups. The determination of the chromatic number of distance graphs and circulant graphs has attracted a considerable interest in the literature and it is one of the main topics of this Thesis. A frequently used method for coloring circulant graphs relates this problem with the so--called {\it Lonely Runner Problem\/} which is also one of the themes of this Thesis. One of the main contributions of this work is an algebraic tool that we call the Prime Filtering Lemma. It allows to distribute the elements through the ring of integers modulo $n$ by means of appropriated multipliers. This tool is intensively used to deal with chromatic problems in distance graphs and circulant graphs. First we solve in the positive the first open case of a conjecture by Zhu (for degree 8) which states that a distance graph can have the maximum chromatic number only if it contains a large clique (in contrast with the situation for general graphs.) We also consider the next case (of degree 10), where the conjecture in its general form has been disproved, and we manage to give an almost complet characterization of the distance graphs with maximum chromatic number. The techniques used to attack these problems are connected with the so--called Lonely Runner Problem, which has several applications to number theory (diophantine approximation) geometry (view obstruction problems) matroid theory (nowhere-zero flows) in addition to the applications to chromatic problems considered here. with a series of contributions by different authors, the problem has been soved up to six runners. Here we solve the first open case with seven runners with a relatively compact proof (in comparison with the former ones). The Thesis finishes by applying the above results to the computation of the chromatic number in circulant graphs. The problem is difficult from the algorithmic point of view (it is NP-hard) but some important cases can be considered. We give a characterization for the case of degree up to six, completing partial existing results. We also consider structured sets of generators, particular the quasiminimal generating sets, and sparse sets of generators (when considered as integers). Finally we give a tight asymptotic bound for the chromatic number which is essentially half of the degree.