Improved Bounds for Cross-Sperner Systems

A collection of families $(\mathcal{F}_{1}, \mathcal{F}_{2} , \cdots , \mathcal{F}_{k}) \in \mathcal{P}([n])^k$ is cross-Sperner if there is no pair $i \not= j$ for which some $F_i \in \mathcal{F}_i$ is comparable to some $F_j \in \mathcal{F}_j$. Two natural measures of the 'size' of such...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2024-04, Vol.31 (2)
Main Authors: Behague, Natalie, Kuperus, Akina, Morrison, Natasha, Wright, Ashna
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue 2
container_start_page
container_title The Electronic journal of combinatorics
container_volume 31
creator Behague, Natalie
Kuperus, Akina
Morrison, Natasha
Wright, Ashna
description A collection of families $(\mathcal{F}_{1}, \mathcal{F}_{2} , \cdots , \mathcal{F}_{k}) \in \mathcal{P}([n])^k$ is cross-Sperner if there is no pair $i \not= j$ for which some $F_i \in \mathcal{F}_i$ is comparable to some $F_j \in \mathcal{F}_j$. Two natural measures of the 'size' of such a family are the sum $\sum_{i = 1}^k |\mathcal{F}_i|$ and the product $\prod_{i = 1}^k |\mathcal{F}_i|$. We prove new upper and lower bounds on both of these measures for general $n$ and $k \ge 2$ which improve considerably on the previous best bounds. In particular, we construct a rich family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós, and Szécsi from 2011.
doi_str_mv 10.37236/11860
format article
fullrecord <record><control><sourceid>crossref</sourceid><recordid>TN_cdi_crossref_primary_10_37236_11860</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_37236_11860</sourcerecordid><originalsourceid>FETCH-LOGICAL-c218t-245eb40f63424ff3b16c398850aa427eb30cbf077328977d2c5f6107e13f23573</originalsourceid><addsrcrecordid>eNpNj81Kw0AURgdRsFZ9hqwEF6Nz753fpQarhYKL6jokk7mgmCbMVKFvb60uXH1n9XGOEJegbsgh2VsAb9WRmIFyTvqA9vgfn4qzUt6VAgzBzMT1cpjy-JX66n783PSl4jFXdR5Lkesp5U3K1XpXtmko5-KE24-SLv52Ll4XDy_1k1w9Py7ru5WMCH4rUZvUacWWNGpm6sBGCt4b1bYaXepIxY73NoQ-ONdjNGz3dgmIkYyjubj6_Y0_FjlxM-W3oc27BlRzCGwOgfQN0qJAHQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Improved Bounds for Cross-Sperner Systems</title><source>Freely Accessible Science Journals - check A-Z of ejournals</source><creator>Behague, Natalie ; Kuperus, Akina ; Morrison, Natasha ; Wright, Ashna</creator><creatorcontrib>Behague, Natalie ; Kuperus, Akina ; Morrison, Natasha ; Wright, Ashna</creatorcontrib><description>A collection of families $(\mathcal{F}_{1}, \mathcal{F}_{2} , \cdots , \mathcal{F}_{k}) \in \mathcal{P}([n])^k$ is cross-Sperner if there is no pair $i \not= j$ for which some $F_i \in \mathcal{F}_i$ is comparable to some $F_j \in \mathcal{F}_j$. Two natural measures of the 'size' of such a family are the sum $\sum_{i = 1}^k |\mathcal{F}_i|$ and the product $\prod_{i = 1}^k |\mathcal{F}_i|$. We prove new upper and lower bounds on both of these measures for general $n$ and $k \ge 2$ which improve considerably on the previous best bounds. In particular, we construct a rich family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós, and Szécsi from 2011.</description><identifier>ISSN: 1077-8926</identifier><identifier>EISSN: 1077-8926</identifier><identifier>DOI: 10.37236/11860</identifier><language>eng</language><ispartof>The Electronic journal of combinatorics, 2024-04, Vol.31 (2)</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></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>Behague, Natalie</creatorcontrib><creatorcontrib>Kuperus, Akina</creatorcontrib><creatorcontrib>Morrison, Natasha</creatorcontrib><creatorcontrib>Wright, Ashna</creatorcontrib><title>Improved Bounds for Cross-Sperner Systems</title><title>The Electronic journal of combinatorics</title><description>A collection of families $(\mathcal{F}_{1}, \mathcal{F}_{2} , \cdots , \mathcal{F}_{k}) \in \mathcal{P}([n])^k$ is cross-Sperner if there is no pair $i \not= j$ for which some $F_i \in \mathcal{F}_i$ is comparable to some $F_j \in \mathcal{F}_j$. Two natural measures of the 'size' of such a family are the sum $\sum_{i = 1}^k |\mathcal{F}_i|$ and the product $\prod_{i = 1}^k |\mathcal{F}_i|$. We prove new upper and lower bounds on both of these measures for general $n$ and $k \ge 2$ which improve considerably on the previous best bounds. In particular, we construct a rich family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós, and Szécsi from 2011.</description><issn>1077-8926</issn><issn>1077-8926</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNpNj81Kw0AURgdRsFZ9hqwEF6Nz753fpQarhYKL6jokk7mgmCbMVKFvb60uXH1n9XGOEJegbsgh2VsAb9WRmIFyTvqA9vgfn4qzUt6VAgzBzMT1cpjy-JX66n783PSl4jFXdR5Lkesp5U3K1XpXtmko5-KE24-SLv52Ll4XDy_1k1w9Py7ru5WMCH4rUZvUacWWNGpm6sBGCt4b1bYaXepIxY73NoQ-ONdjNGz3dgmIkYyjubj6_Y0_FjlxM-W3oc27BlRzCGwOgfQN0qJAHQ</recordid><startdate>20240405</startdate><enddate>20240405</enddate><creator>Behague, Natalie</creator><creator>Kuperus, Akina</creator><creator>Morrison, Natasha</creator><creator>Wright, Ashna</creator><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20240405</creationdate><title>Improved Bounds for Cross-Sperner Systems</title><author>Behague, Natalie ; Kuperus, Akina ; Morrison, Natasha ; Wright, Ashna</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c218t-245eb40f63424ff3b16c398850aa427eb30cbf077328977d2c5f6107e13f23573</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Behague, Natalie</creatorcontrib><creatorcontrib>Kuperus, Akina</creatorcontrib><creatorcontrib>Morrison, Natasha</creatorcontrib><creatorcontrib>Wright, Ashna</creatorcontrib><collection>CrossRef</collection><jtitle>The Electronic journal of combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Behague, Natalie</au><au>Kuperus, Akina</au><au>Morrison, Natasha</au><au>Wright, Ashna</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Improved Bounds for Cross-Sperner Systems</atitle><jtitle>The Electronic journal of combinatorics</jtitle><date>2024-04-05</date><risdate>2024</risdate><volume>31</volume><issue>2</issue><issn>1077-8926</issn><eissn>1077-8926</eissn><abstract>A collection of families $(\mathcal{F}_{1}, \mathcal{F}_{2} , \cdots , \mathcal{F}_{k}) \in \mathcal{P}([n])^k$ is cross-Sperner if there is no pair $i \not= j$ for which some $F_i \in \mathcal{F}_i$ is comparable to some $F_j \in \mathcal{F}_j$. Two natural measures of the 'size' of such a family are the sum $\sum_{i = 1}^k |\mathcal{F}_i|$ and the product $\prod_{i = 1}^k |\mathcal{F}_i|$. We prove new upper and lower bounds on both of these measures for general $n$ and $k \ge 2$ which improve considerably on the previous best bounds. In particular, we construct a rich family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós, and Szécsi from 2011.</abstract><doi>10.37236/11860</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1077-8926
ispartof The Electronic journal of combinatorics, 2024-04, Vol.31 (2)
issn 1077-8926
1077-8926
language eng
recordid cdi_crossref_primary_10_37236_11860
source Freely Accessible Science Journals - check A-Z of ejournals
title Improved Bounds for Cross-Sperner Systems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T06%3A43%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Improved%20Bounds%20for%20Cross-Sperner%20Systems&rft.jtitle=The%20Electronic%20journal%20of%20combinatorics&rft.au=Behague,%20Natalie&rft.date=2024-04-05&rft.volume=31&rft.issue=2&rft.issn=1077-8926&rft.eissn=1077-8926&rft_id=info:doi/10.37236/11860&rft_dat=%3Ccrossref%3E10_37236_11860%3C/crossref%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c218t-245eb40f63424ff3b16c398850aa427eb30cbf077328977d2c5f6107e13f23573%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true