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"”.

  1. 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 …

    nebraska Repository record for Two problems in extremal set theory (opens in a new tab)

  2. 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 …

    ubc Repository record for New results on some Erdős-Ko-Rado-type problems (opens in a new tab) Download PDF for New results on some Erdős-Ko-Rado-type problems (opens in a new tab)

  3. 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 …

    ubc Repository record for Forbidden configurations (opens in a new tab) Download PDF for Forbidden configurations (opens in a new tab)

  4. 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 …

    waterloo Repository record for Colouring Subspaces (opens in a new tab)

  5. 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 …

    regina Repository record for Cliques in block graphs of designs and orthogonal arrays (opens in a new tab)

  6. 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 …

    montana Repository record for FLOWER BASES IN FULL BLOOM: INTERSECTING FAMILIES AND A GENERALIZATION OF DIVERSITY (opens in a new tab)

  7. 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 …

    montana-tech Repository record for FLOWER BASES IN FULL BLOOM: INTERSECTING FAMILIES AND A GENERALIZATION OF DIVERSITY (opens in a new tab)

  8. 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 …

    regina Repository record for The Erdős-Ko-Rado Theorem for intersecting families of permutations. (opens in a new tab) Download PDF for The Erdős-Ko-Rado Theorem for intersecting families of permutations. (opens in a new tab)

  9. 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 …

    regina Repository record for Extensions of the Erdős-Ko-Rado Theorem to Perfect Matchings (opens in a new tab) Download PDF for Extensions of the Erdős-Ko-Rado Theorem to Perfect Matchings (opens in a new tab)

  10. 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 …

    ubc Repository record for Families of forbidden configurations (opens in a new tab) Download PDF for Families of forbidden configurations (opens in a new tab)

  11. 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 …

    bristol Repository record for Some isoperimetric-type problems on graphs (opens in a new tab) Download PDF for Some isoperimetric-type problems on graphs (opens in a new tab)

  12. 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 …

    regina Repository record for Maximum Intersecting Families of Permutations (opens in a new tab) Download PDF for Maximum Intersecting Families of Permutations (opens in a new tab)

  13. 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 …

    uvic Repository record for Cross-Sperner Systems (opens in a new tab)

  14. 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 …

    ottawa-retro Repository record for Graph-dependent Covering Arrays and LYM Inequalities (opens in a new tab)

  15. 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 …

    waterloo Repository record for A Characterization of LYM and Rank Logarithmically Concave Partially Ordered Sets and Its Applications (opens in a new tab)

  16. 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 …

    fu-berlin Repository record for On problems in Extremal Combinatorics (opens in a new tab)

  17. 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 …

    south-carolina Repository record for Generalizations of Sperner's Theorem: Packing Posets, Families Forbidding Posets, and Supersaturation (opens in a new tab)

  18. 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 …

    waterloo Repository record for Independent Sets and Eigenspaces (opens in a new tab)