Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"Extremal Set Theory"”.
-
Two problems in extremal set theory
… focus of this dissertation is on two problems in extremal set theory, which is a branch of extremal combinatorics. The general problem in extremal set theory is to start with all collections of subsets of an underlying ground set, apply restrictions, and then ask how large or small some property …
-
New results on some Erdős-Ko-Rado-type problems
… thesis, we study two longstanding problems in extremal set theory related to the Erdős-Ko-Rado theorem. In these problems, we have a collection F of k-subsets of an n-set that contains no copy of some forbidden substructure. The forbidden substructures in question here are known as clusters and …
-
Forbidden configurations
… field of Forbidden Configurations, a problem in Extremal Set Theory. We consider a family of subsets of {1,2,...,m} as the corresponding {0,1}-incidence matrix. For {0,1}-matrices F, A, we say F is a *subconfiguration* of A if A has a submatrix which is a row and column permutation of F. We say a …
-
Colouring Subspaces
… 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 …
-
Cliques in block graphs of designs and orthogonal arrays
… result in combinatorics, particularly in extremal set theory. This theorem not only establishes an upper bound on the size of the largest intersecting family but also characterizes the families that attain this bound—–these are known as maximal canonically intersecting. Recent work by …
-
FLOWER BASES IN FULL BLOOM: INTERSECTING FAMILIES AND A GENERALIZATION OF DIVERSITY
… the flower base method. We work in the field of extremal set theory, focusing our attention on r-uniform intersecting families. The classic Erd˝os-Ko-Rado Theorem states that, for n large enough, the largest runiform intersecting family, a so-called maximum star, consists of taking all r-sets …
-
FLOWER BASES IN FULL BLOOM: INTERSECTING FAMILIES AND A GENERALIZATION OF DIVERSITY
… the flower base method. We work in the field of extremal set theory, focusing our attention on r-uniform intersecting families. The classic Erd˝os-Ko-Rado Theorem states that, for n large enough, the largest runiform intersecting family, a so-called maximum star, consists of taking all r-sets …
-
The Erdős-Ko-Rado Theorem for intersecting families of permutations.
… Erdős-Ko-Rado Theorem is a fundamental result in extremal set theory. It describes the size and structure of the largest collection of subsets of size k from a set of size n having the property that any two subsets have at least t elements in common. Following the publication of the original …
-
Extensions of the Erdős-Ko-Rado Theorem to Perfect Matchings
One of the important results in extremal set theory is the Erdős-Ko-Rado (EKR) theorem which gives a tight upper bound on the size of intersecting sets. The focus of this thesis is on extensions of the EKR theorem to perfect matchings and uniform set partitions. Two perfect matchings are said to be …
-
Families of forbidden configurations
… configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an m-set given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this …
-
Some isoperimetric-type problems on graphs
Discrete isoperimetric problems are extremal problems on graphs that ask how we can choose a fixed number of vertices that are as closely packed as possible to have a small 'boundary'. This thesis discusses three problems with this common motivation behind, while varying how we measure the boundary …
-
Maximum Intersecting Families of Permutations
In extremal set theory, the Erd}os-Ko-Rado (EKR) theorem gives an upper bound on the size of intersecting k-subsets of the set {1; : : : ;n}. Furthemore, it classi es the maximum-sized families of intersecting k-subsets. It has been shown that similar theorems can be proved for other mathematical …
-
Cross-Sperner Systems
Two sets $A$ and $B$ are \emph{comparable} if $A \subseteq B$ or $B \subseteq A$. A collection of families $(\F_{1}, \F_{2} , \cdots , \F_{k}) \in \mathcal{P}([n])^k$ is \emph{cross-Sperner} if there is no pair $i \not= j$ for which some $F_i \in \F_i$ is comparable to some $F_j \in \F_j$. Two …
-
Graph-dependent Covering Arrays and LYM Inequalities
… They have connections to many areas including extremal set theory, design theory, and graph theory. We define and study several generalizations of covering arrays, and we develop a method which produces an infinite family of LYM inequalities for graph-intersecting collections. A common theme …
-
A Characterization of LYM and Rank Logarithmically Concave Partially Ordered Sets and Its Applications
The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets …
-
On problems in Extremal Combinatorics
Extremal Combinatorics studies how large or how small a structure can be, if it does not contain certain forbidden configuration. One of its major areas of study is extremal set theory, where the structures considered are families of sets, and the forbidden configurations are restricted …
-
Generalizations of Sperner's Theorem: Packing Posets, Families Forbidding Posets, and Supersaturation
Sperner's Theorem is a well known theorem in extremal set theory that gives the size of the largest antichain in the poset that is the Boolean lattice. This is equivalent to finding the largest family of subsets of an $n$-set, $[n]:=\{1,2,\dots,n\}$, such that the family is constructed from …
-
Independent Sets and Eigenspaces
… 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 …