This thesis studies the circular chromatic number of Kneser graphs. It was known that if m is greater than 2n^{2}(n-1), then the Kneser graph KG(m,n) has its circular chromatic number equal its chromatic number . In particular, if n = 3, then KG(m,3) has its circular chromatic number equal its chromatic number when m is greater than 36. In this thesis, we improve this result by proving that if m is greaer than 24, then chi_c(KG(m,3)) = chi(KG(m,3)).

This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F_<em>q</em>, and two <em>k</em>-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the <em>q</em>-Kneser graph when <em>k</em>=2. There are two cases. When <em>k</em>=2 and <em>v</em>=4, the chromatic number is <em>q</em>²+<em>q</em>. If <em>k</em>=2 and <em>v</em>>4, the chromatic number is (<em>q</em>^(v-1)-1)/(<em>q</em>-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the <em>q</em>-Kneser graph in general.

This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.

This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F_<em>q</em>, and two <em>k</em>-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the <em>q</em>-Kneser graph when <em>k</em>=2. There are two cases. When <em>k</em>=2 and <em>v</em>=4, the chromatic number is <em>q</em>²+<em>q</em>. If <em>k</em>=2 and <em>v</em>>4, the chromatic number is (<em>q</em>^(v-1)-1)/(<em>q</em>-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the <em>q</em>-Kneser graph in general.

This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.

This thesie discusses uniquely circular colourable and uniquely fractional colourable graphs. Suppose G = (V;E) is a graph and r &#x00B8; 2 is a real number. A circular r-colouring of G is a mapping f : V (G) ! [0; r) such that for any edge xy of G, 1 ¡P jf(x) &#x00A1; f(y)j ¡P r &#x00A1; 1. We say G is uniquely circular r-colourable if there is a circular r-colouring f of G and any other circular r-colouring of G can obtained from f by a rotation or a ¢Xip of the colours. Let I(G) denote the family of independent sets of G. A fractional r-colouring of G is a mapping f : I(G) ! [0; 1] such that for any vertex x, Px2I f(I) = 1 and PI2I(G) f(I) ¡P r. A graph G is called uniquely fractional r-colourable if there is exactly one fractional r-colouring of G. Uniquely circular r-colourable graphs have been studied extensively in the literature. In particular, it is known that for any r &#x00B8; 2, for any integer g, there is a uniquely circular r- colourable graph of girth at least g. Uniquely fractional r-colouring of graphs is a new concept. In this thesis, we prove that for any r &#x00B8; 2 for any integer g, there is a uniquely fractional r-colourable graph of girth at least g. It is well-known that for any graph G, &#x00C2;f (G) ¡P &#x00C2;c(G). We prove that for any rational numbers r &#x00B8; r0 > 2 and any integer g, there is a graph G of girth at least g, which is uniquely circular r-colourable and at the same time uniquely fractional r0-colourable.

This paper is a compilation of results in combinatorics utilizing the probabilistic method. Below is a brief description of the results highlighted in each chapter. Chapter 1 provides basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used throughout the paper. Chapter 2 introduces the independent domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the independent domination number is one of two values. Also, the the number of independent dominating sets of given cardinality is analyzed statistically. Chapter 3 introduces the tree domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the tree domination number is one of two values. Additional related domination parameters are also discussed. Chapter 4 introduces a generalized rook polynomial first studied by J. Goldman et al. Central and local limit theorems are then proven for certain classes of the generalized rook polynomial. Special cases include known central and local limit theorems for the Stirling numbers of the first and second kind and additionally new limit theorems for the Lah numbers and certain classes of known generalized Stirling numbers. Chapter 5 introduces the Kneser Graph. The exact expected value and variance of the distance between [n] and a vertex chosen uniformly at random is given. An asymptotic formula for the expectation is found.

Cette thèse est consacrée à l'étude des représentations automorphes algébriques des groupes linéaires découvertes par Chenevier-Renard. On s'intéresse plus particulièrement à leurs paramètres de Satake. Pour cela, nous utilisons la théorie d'Arthur afin de faire apparaître ces représentations par le biais de représentations automorphes discrètes des groupes spéciaux orthogonaux de réseaux bien choisis. Ensuite, on détermine des propriétés d'opérateurs de Hecke agissant sur ces mêmes réseaux, ce qui nous donne de nombreuses informations sur ces paramètres de Satake. On arrive notamment à déterminer la trace dans la représentation standard de nombreux paramètres de Satake des représentations algébriques évoquées, dont les poids peuvent être arbitrairement grands. Ces résultats nous permettent aussi de déterminer de nombreux opérateurs de Hecke, associés aux voisinage de Kneser, vus comme endomorphismes agissant sur les classes d'isomorphisme des réseaux pairs de déterminant 2 en dimension 23 ou 25. / In this these we study the different algebraic automorphic representations discovered by Chenevier-Renard. We focus more particularly on their Satake parameters. To do so, we use Arthur's theory, which enables us to see these representations through discrete automorphic representations for the special orthogonal group of well chosen lattices. Afterwards, we can compute some properties of Hecke operators acting on these lattices. This gives us a lot of information on these Satake parameters. In particular, we can determine the trace in the standard representation for many of these algebraic representations, which weight can be arbitrarily high. These results also enable us to compute many Hecke operators, connected to the notion of neighbourhood developed by Kneser, seen as linear operators acting on the classes of isomorphism of even lattices with determinant 2 in dimension 23 or 25.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-05-30T13:29:28Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese Filipe Andrade.pdf: 827988 bytes, checksum: 2b48a1cdaad11619e56c67a685d04671 (MD5) / Made available in DSpace on 2017-05-30T13:29:28Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese Filipe Andrade.pdf: 827988 bytes, checksum: 2b48a1cdaad11619e56c67a685d04671 (MD5) Previous issue date: 2016-01-15 / CNPQ / Nesse trabalho estaremos interessados em estudar propriedades relacionadas as soluções brandas para certos tipos de equações de evoluções. Dentre tais propriedades estudamos a existência de tais soluções assim como questões de periodicidade, para o problema de Cauchy abstrato com retardo dependendo do estado e para o problema com semigrupo exponencialmente estável. E para a equação que modela a dinâmica das estruturas flexíveis, esturademos a propriedade de Kneser. / In the present study, we focused on properties related to mild solutions to certain types of evolution equations. Among such properties, we studied the existence of these solutions as well as periodicity problems to the abstract Cauchy problem with state dependent delay and to the hyperbolic semigroup problem. In addition, for the equation that models the dynamic of flexible structures we studied the Kneser property.

Orientadora: Letícia Rodrigues Bueno / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2013