Estudamos o problema de famílias intersectantes extremais em um subconjunto aleatório da família dos subconjuntos com exatamente k elementos de um conjunto dado. Obtivemos uma descrição quase completa da evolução do tamanho de tais famílias. Versões semelhantes do problema foram estudadas por Balogh, Bohman e Mubayi em 2009, e por Hamm e Kahn, e Balogh, Das, Delcourt, Liu e Sharifzadeh de maneira concorrente a este trabalho. / We studied the problem of maximal intersecting families in a random subset of the family of subsets with exactly k elements from a given set. We obtained a nearly complete description of the evolution of the size of such families. Similar versions of this problem have been studied by Balogh, Bohman and Mubayi in 2009, and by Hamm and Kahn, and Balogh, Das, Delcourt, Liu and Sharifzadeh concurrently with this work.

Estudamos o problema de famílias intersectantes extremais em um subconjunto aleatório da família dos subconjuntos com exatamente k elementos de um conjunto dado. Obtivemos uma descrição quase completa da evolução do tamanho de tais famílias. Versões semelhantes do problema foram estudadas por Balogh, Bohman e Mubayi em 2009, e por Hamm e Kahn, e Balogh, Das, Delcourt, Liu e Sharifzadeh de maneira concorrente a este trabalho. / We studied the problem of maximal intersecting families in a random subset of the family of subsets with exactly k elements from a given set. We obtained a nearly complete description of the evolution of the size of such families. Similar versions of this problem have been studied by Balogh, Bohman and Mubayi in 2009, and by Hamm and Kahn, and Balogh, Das, Delcourt, Liu and Sharifzadeh concurrently with this work.

In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them. A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star. We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed. We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.

The classical Erdos-Ko-Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size (n > 2k), then the largest possible pairwise intersecting family has size t = (k-1n-1). We consider the probability that a randomly selected family of size t = tn has the EKR property (pairwise nonempty intersection) as n and k = kn tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson's inequality. Using the Stein-Chen method we show that the distribution of X0, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for Xi, the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution X0, X1, ⋯, Xb) can be approximated by a multidimensional Poisson vector with independent components.

With the publication of the famous Erdős-Ko-Rado Theorem in 1961, intersection problems became a popular area of combinatorics. A family of combinatorial objects is t-intersecting if any two of its elements mutually t-intersect, where the latter concept needs to be specified separately in each instance. This thesis is split into two parts; the first is concerned with intersecting injections while the second investigates intersecting posets. We classify maximum 1-intersecting families of injections from {1, ..., k} to {1, ..., n}, a generalisation of the corresponding result on permutations from the early 2000s. Moreover, we obtain classifications in the general t>1 case for different parameter limits: if n is large in terms of k and t, then the so-called fix-families, consisting of all injections which map some fixed set of t points to the same image points, are the only t-intersecting injection families of maximal size. By way of contrast, fixing the differences k-t and n-k while increasing k leads to optimal families which are equivalent to one of the so-called saturation families, consisting of all injections fixing at least r+t of the first 2r+t points, where r=|_ (k-t)/2 _|. Furthermore we demonstrate that, among injection families with t-intersecting and left-compressed fixed point sets, for some value of r the saturation family has maximal size . The concept that two posets intersect if they share a comparison is new. We begin by classifying maximum intersecting families in several isomorphism classes of posets which are linear, or almost linear. Then we study the union of the almost linear classes, and derive a bound for an intersecting family by adapting Katona's elegant cycle method to posets. The thesis ends with an investigation of the intersection structure of poset classes whose elements are close to the antichain. The overarching theme of this thesis is fixing versus saturation: we compare the sizes and structures of intersecting families obtained from these two distinct principles in the context of various classes of combinatorial objects.

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>?? 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>± 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.