{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/21100"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/21100","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Combinatorics of finite sets","abstract":"Let $\\lbrack n\\rbrack = \\{1,2,\\..., n\\},A$ and let $2\\sp{\\lbrack n\\rbrack}$ represent the subset lattice of (n) with sets ordered by inclusion. A collection I of subsets of (n) is called an ideal if every subset of a member of I is also in I. An intersecting family S in 2$\\sp{\\lbrack n\\rbrack }$ is called a star if there exists an element of (n) belonging to every member of S, and it is a 1-star if the intersection of every two members of I is exactly that element. Chvatal conjectured that if I is any ideal, then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2$\\sp{\\lbrack n\\rbrack }$ that is compressed with respect to a given element. We prove that among the largest intersecting families of I there is a star. We also prove that if the maximal elements $B\\sb1,\\...,B\\sb{q}$ of an ideal I can be partitioned into two 1-stars, then I satisfies Chvatal's conjecture.","abstract_html":"Let $\\lbrack n\\rbrack = \\{1,2,\\..., n\\},A$ and let $2\\sp{\\lbrack n\\rbrack}$ represent the subset lattice of (n) with sets ordered by inclusion. A collection I of subsets of (n) is called an ideal if every subset of a member of I is also in I. An intersecting family S in 2$\\sp{\\lbrack n\\rbrack }$ is called a star if there exists an element of (n) belonging to every member of S, and it is a 1-star if the intersection of every two members of I is exactly that element. Chvatal conjectured that if I is any ideal, then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2$\\sp{\\lbrack n\\rbrack }$ that is compressed with respect to a given element. We prove that among the largest intersecting families of I there is a star. We also prove that if the maximal elements $B\\sb1,\\...,B\\sb{q}$ of an ideal I can be partitioned into two 1-stars, then I satisfies Chvatal's conjecture.","abstract_has_math":true,"creators":["Snevily, Hunter Saint Clair"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Reznick, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:58:24Z","date_published":"2011-05-07T12:58:24Z","updated_at":"2026-07-22T22:25:17Z","subjects":["Mathematics"],"languages":["eng"],"rights":["Copyright 1991 Snevily, Hunter Saint Clair"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210996","(UMI)AAI9210996"],"render_values":[{"text":"AAI9210996","href":null,"code":true},{"text":"(UMI)AAI9210996","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/21100","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Reznick, Bruce"]},{"key":"dc:creator","label":"Author","values":["Snevily, Hunter Saint Clair"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:58:24Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Snevily, Hunter Saint Clair"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210996","(UMI)AAI9210996","http://hdl.handle.net/2142/21100"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Let $\\lbrack n\\rbrack = \\{1,2,\\..., n\\},A$ and let $2\\sp{\\lbrack n\\rbrack}$ represent the subset lattice of (n) with sets ordered by inclusion. A collection I of subsets of (n) is called an ideal if every subset of a member of I is also in I. An intersecting family S in 2$\\sp{\\lbrack n\\rbrack }$ is called a star if there exists an element of (n) belonging to every member of S, and it is a 1-star if the intersection of every two members of I is exactly that element. Chvatal conjectured that if I is any ideal, then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2$\\sp{\\lbrack n\\rbrack }$ that is compressed with respect to a given element. We prove that among the largest intersecting families of I there is a star. We also prove that if the maximal elements $B\\sb1,\\...,B\\sb{q}$ of an ideal I can be partitioned into two 1-stars, then I satisfies Chvatal's conjecture.","In Chapter 2, we consider the following two conjectures concerning intersecting families of a finite set. Conjecture 1: (Frankl and Furedi (18)) Given n, k, let ${\\cal A}$ be a collection of subsets of an n-set such that 1 $\\leq \\vert A\\cap B\\vert \\leq k$ for all A, B $\\in {\\cal A}$. Then $\\vert{\\cal A}\\vert \\leq t\\sb{n,k}$, where $t\\sb{n,k} = \\sum\\sbsp{i=0}{k}{n-1\\choose i}.$ Conjecture 2: (Snevily) Let S = $\\{ l\\sb1$, ...,$l\\sb{k}\\}$ be a collection of k positive integers. If ${\\cal A}$ is a collection of subsets of X such that $\\vert A \\cap B\\vert \\in S$ for all A, $B \\in {\\cal A}$, then $\\vert {\\cal A}\\vert \\leq t\\sb{n,k}$. We prove that Conjecture 1 is true when $n > 4.5k\\sp{3} + 7.5k\\sp2 + 3k + 1.$ We prove necessary conditions for possible counterexamples to Conjecture 2 when n is sufficiently large.","Let ${\\cal B}(k)$ denote the bipartite graph whose vertices are the k and k + 1 sets of (2k + 1), with edges specified by the inclusion relationship. Erdos conjectured that ${\\cal B}(k)$ contains a Hamitonian cycle. Any such cycle must be composed of two matchings between the middle levels of the Boolean lattice. We study such matchings that are invariant under cyclic permutations of the ground set. We then construct a new class of matchings called modular matchings and show that these are nonisomorphic to the lexical matchings. We describe the orbits of the modular matchings under automorphisms of ${\\cal B}(k),$ and we also construct an example of a matching that is neither lexical nor modular.","Finally, we generalize some results about special vertex labelings that, by a theorem of Rosa, yield decompositions of the complete graph $K\\sb{n}$ into isomorphic copies of certain specified graphs.","Made available in DSpace on 2011-05-07T12:58:24Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210996.pdf: 3366094 bytes, checksum: 9a484010039f533d9bd8a524a1c8b7aa (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:48:29Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:21:57-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Combinatorics of finite sets"]}]}],"canonical_facts":{"dc:contributor":["Reznick, Bruce"],"dc:creator":["Snevily, Hunter Saint Clair"],"dc:date":["2011-05-07T12:58:24Z","10000-01-01","1991"],"dc:description":["Let $\\lbrack n\\rbrack = \\{1,2,\\..., n\\},A$ and let $2\\sp{\\lbrack n\\rbrack}$ represent the subset lattice of (n) with sets ordered by inclusion. A collection I of subsets of (n) is called an ideal if every subset of a member of I is also in I. An intersecting family S in 2$\\sp{\\lbrack n\\rbrack }$ is called a star if there exists an element of (n) belonging to every member of S, and it is a 1-star if the intersection of every two members of I is exactly that element. Chvatal conjectured that if I is any ideal, then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2$\\sp{\\lbrack n\\rbrack }$ that is compressed with respect to a given element. We prove that among the largest intersecting families of I there is a star. We also prove that if the maximal elements $B\\sb1,\\...,B\\sb{q}$ of an ideal I can be partitioned into two 1-stars, then I satisfies Chvatal's conjecture.","In Chapter 2, we consider the following two conjectures concerning intersecting families of a finite set. Conjecture 1: (Frankl and Furedi (18)) Given n, k, let ${\\cal A}$ be a collection of subsets of an n-set such that 1 $\\leq \\vert A\\cap B\\vert \\leq k$ for all A, B $\\in {\\cal A}$. Then $\\vert{\\cal A}\\vert \\leq t\\sb{n,k}$, where $t\\sb{n,k} = \\sum\\sbsp{i=0}{k}{n-1\\choose i}.$ Conjecture 2: (Snevily) Let S = $\\{ l\\sb1$, ...,$l\\sb{k}\\}$ be a collection of k positive integers. If ${\\cal A}$ is a collection of subsets of X such that $\\vert A \\cap B\\vert \\in S$ for all A, $B \\in {\\cal A}$, then $\\vert {\\cal A}\\vert \\leq t\\sb{n,k}$. We prove that Conjecture 1 is true when $n > 4.5k\\sp{3} + 7.5k\\sp2 + 3k + 1.$ We prove necessary conditions for possible counterexamples to Conjecture 2 when n is sufficiently large.","Let ${\\cal B}(k)$ denote the bipartite graph whose vertices are the k and k + 1 sets of (2k + 1), with edges specified by the inclusion relationship. Erdos conjectured that ${\\cal B}(k)$ contains a Hamitonian cycle. Any such cycle must be composed of two matchings between the middle levels of the Boolean lattice. We study such matchings that are invariant under cyclic permutations of the ground set. We then construct a new class of matchings called modular matchings and show that these are nonisomorphic to the lexical matchings. We describe the orbits of the modular matchings under automorphisms of ${\\cal B}(k),$ and we also construct an example of a matching that is neither lexical nor modular.","Finally, we generalize some results about special vertex labelings that, by a theorem of Rosa, yield decompositions of the complete graph $K\\sb{n}$ into isomorphic copies of certain specified graphs.","Made available in DSpace on 2011-05-07T12:58:24Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210996.pdf: 3366094 bytes, checksum: 9a484010039f533d9bd8a524a1c8b7aa (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:48:29Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:21:57-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9210996","(UMI)AAI9210996","http://hdl.handle.net/2142/21100"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Snevily, Hunter Saint Clair"],"dc:subject":["Mathematics"],"dc:title":["Combinatorics of finite sets"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:17Z"}