Shattering-extremal set systems from Sperner families

We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an a...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-04, Vol.276, p.92-101
Main Authors: Kusch, Christopher, Mészáros, Tamás
Format: Article
Language:English
Subjects:
Gröbner bases
Sauer–Shelah lemma
Shattering
Sperner families
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c320t-2224cd4ec563b15a07ef1960f5402bac174106a03ece0522068e8a80ff7456bc3
container_end_page 101
container_issue
container_start_page 92
container_title Discrete Applied Mathematics
container_volume 276
creator Kusch, Christopher
Mészáros, Tamás
description We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach.
doi_str_mv 10.1016/j.dam.2019.07.016
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2430111540</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0166218X19303324</els_id><sourcerecordid>2430111540</sourcerecordid><originalsourceid>FETCH-LOGICAL-c320t-2224cd4ec563b15a07ef1960f5402bac174106a03ece0522068e8a80ff7456bc3</originalsourceid><addsrcrecordid>eNp9kEFLAzEQhYMoWKs_wNuC511nsrvJFk9StAoFD1XwFtLsRLN0d2uSiv33ptSzp2E-3nszPMauEQoEFLdd0eq-4ICzAmSRyAmbYCN5LqTEUzZJROQcm_dzdhFCBwCYtgmrV586RvJu-MjpJ3rq9SYLFLOwD5H6kFk_9tlqS34gn1ndu42jcMnOrN4EuvqbU_b2-PA6f8qXL4vn-f0yNyWHmHPOK9NWZGpRrrHWIMniTICtK-BrbVBWCEJDSYag5hxEQ41uwFpZ1WJtyim7OeZu_fi1oxBVN-78kE4qXpWAiCkpqfCoMn4MwZNVW-967fcKQR3aUZ1K7ahDOwqkSiR57o4eSu9_O_IqGEeDodZ5MlG1o_vH_QtgOmu_</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2430111540</pqid></control><display><type>article</type><title>Shattering-extremal set systems from Sperner families</title><source>ScienceDirect Freedom Collection</source><creator>Kusch, Christopher ; Mészáros, Tamás</creator><creatorcontrib>Kusch, Christopher ; Mészáros, Tamás</creatorcontrib><description>We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach.</description><identifier>ISSN: 0166-218X</identifier><identifier>EISSN: 1872-6771</identifier><identifier>DOI: 10.1016/j.dam.2019.07.016</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Gröbner bases ; Sauer–Shelah lemma ; Shattering ; Sperner families</subject><ispartof>Discrete Applied Mathematics, 2020-04, Vol.276, p.92-101</ispartof><rights>2019 Elsevier B.V.</rights><rights>Copyright Elsevier BV 2020</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c320t-2224cd4ec563b15a07ef1960f5402bac174106a03ece0522068e8a80ff7456bc3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Kusch, Christopher</creatorcontrib><creatorcontrib>Mészáros, Tamás</creatorcontrib><title>Shattering-extremal set systems from Sperner families</title><title>Discrete Applied Mathematics</title><description>We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach.</description><subject>Gröbner bases</subject><subject>Sauer–Shelah lemma</subject><subject>Shattering</subject><subject>Sperner families</subject><issn>0166-218X</issn><issn>1872-6771</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp9kEFLAzEQhYMoWKs_wNuC511nsrvJFk9StAoFD1XwFtLsRLN0d2uSiv33ptSzp2E-3nszPMauEQoEFLdd0eq-4ICzAmSRyAmbYCN5LqTEUzZJROQcm_dzdhFCBwCYtgmrV586RvJu-MjpJ3rq9SYLFLOwD5H6kFk_9tlqS34gn1ndu42jcMnOrN4EuvqbU_b2-PA6f8qXL4vn-f0yNyWHmHPOK9NWZGpRrrHWIMniTICtK-BrbVBWCEJDSYag5hxEQ41uwFpZ1WJtyim7OeZu_fi1oxBVN-78kE4qXpWAiCkpqfCoMn4MwZNVW-967fcKQR3aUZ1K7ahDOwqkSiR57o4eSu9_O_IqGEeDodZ5MlG1o_vH_QtgOmu_</recordid><startdate>20200415</startdate><enddate>20200415</enddate><creator>Kusch, Christopher</creator><creator>Mészáros, Tamás</creator><general>Elsevier B.V</general><general>Elsevier BV</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20200415</creationdate><title>Shattering-extremal set systems from Sperner families</title><author>Kusch, Christopher ; Mészáros, Tamás</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c320t-2224cd4ec563b15a07ef1960f5402bac174106a03ece0522068e8a80ff7456bc3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Gröbner bases</topic><topic>Sauer–Shelah lemma</topic><topic>Shattering</topic><topic>Sperner families</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kusch, Christopher</creatorcontrib><creatorcontrib>Mészáros, Tamás</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Discrete Applied Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kusch, Christopher</au><au>Mészáros, Tamás</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Shattering-extremal set systems from Sperner families</atitle><jtitle>Discrete Applied Mathematics</jtitle><date>2020-04-15</date><risdate>2020</risdate><volume>276</volume><spage>92</spage><epage>101</epage><pages>92-101</pages><issn>0166-218X</issn><eissn>1872-6771</eissn><abstract>We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.dam.2019.07.016</doi><tpages>10</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0166-218X
ispartof Discrete Applied Mathematics, 2020-04, Vol.276, p.92-101
issn 0166-218X
1872-6771
language eng
recordid cdi_proquest_journals_2430111540
source ScienceDirect Freedom Collection
subjects Gröbner bases
Sauer–Shelah lemma
Shattering
Sperner families
title Shattering-extremal set systems from Sperner families
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T09%3A41%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Shattering-extremal%20set%20systems%20from%20Sperner%20families&rft.jtitle=Discrete%20Applied%20Mathematics&rft.au=Kusch,%20Christopher&rft.date=2020-04-15&rft.volume=276&rft.spage=92&rft.epage=101&rft.pages=92-101&rft.issn=0166-218X&rft.eissn=1872-6771&rft_id=info:doi/10.1016/j.dam.2019.07.016&rft_dat=%3Cproquest_cross%3E2430111540%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c320t-2224cd4ec563b15a07ef1960f5402bac174106a03ece0522068e8a80ff7456bc3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2430111540&rft_id=info:pmid/&rfr_iscdi=true