Forbidden subposet problems in the grid

DOI10.1016/J.DISC.2021.112720MaRDI QIDQ2065899zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Dániel T. Nagy, Balázs Patkós, Máté Vizer

Publication date 13 January 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.08297

zbMATH Keywords

Boolean latticeextremal combinatoricsextremal set systemforbidden subposetgrid

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorics of partially ordered sets (06A07)

Abstract: For posets $P$ and $Q$, extremal and saturation problems about weak and strong $P$-free subposets of $Q$ have been studied mostly in the case $Q$ is the Boolean poset $Q_n$, the poset of all subsets of an $n$-element set ordered by inclusion. In this paper, we study some instances of the problem with $Q$ being the grid, and its connections to the Boolean case and to the forbidden submatrix problem.

Recommendations

• Induced and non-induced forbidden subposet problems
• Supersaturation, counting, and randomness in forbidden subposet problems
• The saturation number of induced subposets of the Boolean lattice
• Forbidden induced subposets of given height
• On families of subsets with a forbidden subposet

Cites work

• l-Chain Profile Vectors
• A LYM inequality for induced posets
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Extremal Finite Set Theory
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Forbidden induced subposets of given height
• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• Induced and non-induced poset saturation problems
• Largest family without A B C D
• On a lemma of Littlewood and Offord
• On families of subsets with a forbidden subposet
• Progress on poset-free families of subsets
• Saturation problems about forbidden 0-1 submatrices
• Set families with a forbidden subposet
• The method of double chains for largest families with excluded subposets

Cited in

(5)

• On extremal orthoposets without forbidden substructures
• Forbidden subposet problems with size restrictions
• An exact characterization of saturation for permutation matrices
• Saturation of Ordered Graphs
• Forbidden subposets in the cycle poset

This page was built for publication: Forbidden subposet problems in the grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065899)