Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The induced saturation problem for posets
School of Mathematics, University of Birmingham, United Kingdom.
School of Mathematics, University of Birmingham, United Kingdom.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
School of Mathematics, University of Birmingham, United Kingdom.
2023 (English)In: Combinatorial Theory, E-ISSN 2766-1334, Vol. 3, no 3, article id 9Article in journal (Refereed) Published
Abstract [en]

For a fixed poset P, a family F of subsets of [n] is induced P-saturated if F does not contain an induced copy of P, but for every subset S of [n] such that S ∉ F, P is an induced subposet of F ∪{S}. The size of the smallest such family F is denoted by sat∗ (n, P). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset P, either sat* (n, P) = O(1) or (Formula presented). In this paper we improve this general result showing that either (Formula presented). Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset (Formula presented) we have (Formula presented); so if true this conjecture implies our result is tight up to a multi-plicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset P, either sat* (n, P) = O(1) or (Formula presented). We prove that this latter conjecture is true for a certain class of posets P.

Place, publisher, year, edition, pages
eScholarship Publishing , 2023. Vol. 3, no 3, article id 9
Keywords [en]
Partially ordered sets, saturation, Turán-type problems
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-219078DOI: 10.5070/C63362792Scopus ID: 2-s2.0-85180680891OAI: oai:DiVA.org:umu-219078DiVA, id: diva2:1826187
Available from: 2024-01-11 Created: 2024-01-11 Last updated: 2024-01-11Bibliographically approved

Open Access in DiVA

fulltext(544 kB)37 downloads
File information
File name FULLTEXT01.pdfFile size 544 kBChecksum SHA-512
ac343dc896d3b54cc1dae08e0267f3dfea7115bfab710b7c427183f8e5bfe430da52cc9bcfdfde8105c2c6877ac71b19af378a8044a6cd21daeca3558e37d75d
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Sharifzadeh, Maryam

Search in DiVA

By author/editor
Sharifzadeh, Maryam
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 37 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 231 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf