Loading…
On the size of maximal antichains and the number of pairwise disjoint maximal chains
Fix integers n and k with n ≥ k ≥ 3 . Duffus and Sands proved that if P is a finite poset and n ≤ | C | ≤ n + ( n − k ) / ( k − 2 ) for every maximal chain in P , then P must contain k pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities ar...
Saved in:
| Published in: | Discrete mathematics 2010-11, Vol.310 (21), p.2890-2894 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3 |
| container_end_page | 2894 |
| container_issue | 21 |
| container_start_page | 2890 |
| container_title | Discrete mathematics |
| container_volume | 310 |
| creator | Howard, David M. Trotter, William T. |
| description | Fix integers
n
and
k
with
n
≥
k
≥
3
. Duffus and Sands proved that if
P
is a finite poset and
n
≤
|
C
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal chain in
P
, then
P
must contain
k
pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if
P
is a finite poset and
n
≤
|
A
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal antichain in
P
, then
P
has
k
pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains. |
| doi_str_mv | 10.1016/j.disc.2010.06.034 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_849451680</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0012365X10002487</els_id><sourcerecordid>849451680</sourcerecordid><originalsourceid>FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3</originalsourceid><addsrcrecordid>eNp9kE1PwyAYx4nRxDn9Ap56MZ5agQKliRez-JYs2WUmuxEKNKNp6YTOt08vtcuOnoAnv__zPPwAuEYwQxCxuybTNqgMw1iALIM5OQEzxAucMo42p2AGIcJpzujmHFyE0MD4ZjmfgfXKJcPWJMH-mKSvk05-2U62iXSDVVtpXYhX_Ye4fVcZP0I7af2nDSaJQ5veuuEYmyKX4KyWbTBXh3MO3p4e14uXdLl6fl08LFOVMzykFCNGZMmJrmlBmakLUiGtC0khIrisqqI0qIw1XlFFJWGaSM5RUUKNVFnofA5up74737_vTRhEFy2YtpXO9PsgOCkJRYzDSOKJVL4PwZta7Hxc2H8LBMVoUDRiNChGgwIyEQ3G0M2hvQxKtrWXTtlwTOIcI8wJjtz9xJn41w9rvAjKGqeMtt6oQeje_jfmF7Rshoo</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>849451680</pqid></control><display><type>article</type><title>On the size of maximal antichains and the number of pairwise disjoint maximal chains</title><source>ScienceDirect Freedom Collection</source><creator>Howard, David M. ; Trotter, William T.</creator><creatorcontrib>Howard, David M. ; Trotter, William T.</creatorcontrib><description>Fix integers
n
and
k
with
n
≥
k
≥
3
. Duffus and Sands proved that if
P
is a finite poset and
n
≤
|
C
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal chain in
P
, then
P
must contain
k
pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if
P
is a finite poset and
n
≤
|
A
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal antichain in
P
, then
P
has
k
pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.</description><identifier>ISSN: 0012-365X</identifier><identifier>EISSN: 1872-681X</identifier><identifier>DOI: 10.1016/j.disc.2010.06.034</identifier><identifier>CODEN: DSMHA4</identifier><language>eng</language><publisher>Kidlington: Elsevier B.V</publisher><subject>Algebra ; Antichains ; Chains ; Combinatorics ; Combinatorics. Ordered structures ; Construction ; Exact sciences and technology ; Inequalities ; Integers ; Mathematical analysis ; Mathematics ; Partially ordered set ; Sands ; Sciences and techniques of general use ; Two dimensional</subject><ispartof>Discrete mathematics, 2010-11, Vol.310 (21), p.2890-2894</ispartof><rights>2010 Elsevier B.V.</rights><rights>2015 INIST-CNRS</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3</citedby><cites>FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=23212842$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Howard, David M.</creatorcontrib><creatorcontrib>Trotter, William T.</creatorcontrib><title>On the size of maximal antichains and the number of pairwise disjoint maximal chains</title><title>Discrete mathematics</title><description>Fix integers
n
and
k
with
n
≥
k
≥
3
. Duffus and Sands proved that if
P
is a finite poset and
n
≤
|
C
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal chain in
P
, then
P
must contain
k
pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if
P
is a finite poset and
n
≤
|
A
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal antichain in
P
, then
P
has
k
pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.</description><subject>Algebra</subject><subject>Antichains</subject><subject>Chains</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Construction</subject><subject>Exact sciences and technology</subject><subject>Inequalities</subject><subject>Integers</subject><subject>Mathematical analysis</subject><subject>Mathematics</subject><subject>Partially ordered set</subject><subject>Sands</subject><subject>Sciences and techniques of general use</subject><subject>Two dimensional</subject><issn>0012-365X</issn><issn>1872-681X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><recordid>eNp9kE1PwyAYx4nRxDn9Ap56MZ5agQKliRez-JYs2WUmuxEKNKNp6YTOt08vtcuOnoAnv__zPPwAuEYwQxCxuybTNqgMw1iALIM5OQEzxAucMo42p2AGIcJpzujmHFyE0MD4ZjmfgfXKJcPWJMH-mKSvk05-2U62iXSDVVtpXYhX_Ye4fVcZP0I7af2nDSaJQ5veuuEYmyKX4KyWbTBXh3MO3p4e14uXdLl6fl08LFOVMzykFCNGZMmJrmlBmakLUiGtC0khIrisqqI0qIw1XlFFJWGaSM5RUUKNVFnofA5up74737_vTRhEFy2YtpXO9PsgOCkJRYzDSOKJVL4PwZta7Hxc2H8LBMVoUDRiNChGgwIyEQ3G0M2hvQxKtrWXTtlwTOIcI8wJjtz9xJn41w9rvAjKGqeMtt6oQeje_jfmF7Rshoo</recordid><startdate>20101106</startdate><enddate>20101106</enddate><creator>Howard, David M.</creator><creator>Trotter, William T.</creator><general>Elsevier B.V</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>IQODW</scope><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>20101106</creationdate><title>On the size of maximal antichains and the number of pairwise disjoint maximal chains</title><author>Howard, David M. ; Trotter, William T.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Algebra</topic><topic>Antichains</topic><topic>Chains</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Construction</topic><topic>Exact sciences and technology</topic><topic>Inequalities</topic><topic>Integers</topic><topic>Mathematical analysis</topic><topic>Mathematics</topic><topic>Partially ordered set</topic><topic>Sands</topic><topic>Sciences and techniques of general use</topic><topic>Two dimensional</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Howard, David M.</creatorcontrib><creatorcontrib>Trotter, William T.</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>Pascal-Francis</collection><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 mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Howard, David M.</au><au>Trotter, William T.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the size of maximal antichains and the number of pairwise disjoint maximal chains</atitle><jtitle>Discrete mathematics</jtitle><date>2010-11-06</date><risdate>2010</risdate><volume>310</volume><issue>21</issue><spage>2890</spage><epage>2894</epage><pages>2890-2894</pages><issn>0012-365X</issn><eissn>1872-681X</eissn><coden>DSMHA4</coden><abstract>Fix integers
n
and
k
with
n
≥
k
≥
3
. Duffus and Sands proved that if
P
is a finite poset and
n
≤
|
C
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal chain in
P
, then
P
must contain
k
pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if
P
is a finite poset and
n
≤
|
A
|
≤
n
+
(
n
−
k
)
/
(
k
−
2
)
for every maximal antichain in
P
, then
P
has
k
pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.</abstract><cop>Kidlington</cop><pub>Elsevier B.V</pub><doi>10.1016/j.disc.2010.06.034</doi><tpages>5</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0012-365X |
| ispartof | Discrete mathematics, 2010-11, Vol.310 (21), p.2890-2894 |
| issn | 0012-365X 1872-681X |
| language | eng |
| recordid | cdi_proquest_miscellaneous_849451680 |
| source | ScienceDirect Freedom Collection |
| subjects | Algebra Antichains Chains Combinatorics Combinatorics. Ordered structures Construction Exact sciences and technology Inequalities Integers Mathematical analysis Mathematics Partially ordered set Sands Sciences and techniques of general use Two dimensional |
| title | On the size of maximal antichains and the number of pairwise disjoint maximal chains |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-27T17%3A25%3A40IST&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=On%20the%20size%20of%20maximal%20antichains%20and%20the%20number%20of%20pairwise%20disjoint%20maximal%20chains&rft.jtitle=Discrete%20mathematics&rft.au=Howard,%20David%20M.&rft.date=2010-11-06&rft.volume=310&rft.issue=21&rft.spage=2890&rft.epage=2894&rft.pages=2890-2894&rft.issn=0012-365X&rft.eissn=1872-681X&rft.coden=DSMHA4&rft_id=info:doi/10.1016/j.disc.2010.06.034&rft_dat=%3Cproquest_cross%3E849451680%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c362t-52164a984df5756ef74b1dd7a501429bb79e194b18b5c5a46d4a881790d1c97d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=849451680&rft_id=info:pmid/&rfr_iscdi=true |