The Induced Saturation Number for $\mathcal{V}_3$ is Linear

Given a poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the Boolean lattice is said to be $\mathcal{P}$-saturated if $\mathcal{F}$ does not contain an induced copy $\mathcal P$, but every proper superset of $\mathcal{F}$ contains one. The minimum size of a $\mathcal P$-saturated family in the $n$-dimensional Boolean lattice is denoted by $sat^*(n,\mathcal{P})$.\par In this paper, we consider the poset $\mathcal V_3$ (the four element poset with one minimal element and three incomparable maximal elements) and show that $sat^*(n,\mathcal{V}_3)\geq \frac{n}{2}$. This represents the first linear lower bound for $sat^*(n,\mathcal{V}_3)$, improving upon the previously best-known bound of $2\sqrt{n}$. Our result establishes that $sat^*(n,\mathcal{V}_3) = Θ(n)$.

Publication Details

Journal
ArXiv.org
Published
2025-07-11
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

The Induced Saturation Number for $\mathcal{V}_3$ is Linear

ArXiv.org
Limits and Structures in Graph Theory
article

The Induced Saturation Number for $\mathcal{V}_3$ is Linear

article en

Abstract

Given a poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the Boolean lattice is said to be $\mathcal{P}$-saturated if $\mathcal{F}$ does not contain an induced copy $\mathcal P$, but every proper superset of $\mathcal{F}$ contains one. The minimum size of a $\mathcal P$-saturated family in the $n$-dimensional Boolean lattice is denoted by $sat^*(n,\mathcal{P})$.\par In this paper, we consider the poset $\mathcal V_3$ (the four element poset with one minimal element and three incomparable maximal elements) and show that $sat^*(n,\mathcal{V}_3)\geq \frac{n}{2}$. This represents the first linear lower bound for $sat^*(n,\mathcal{V}_3)$, improving upon the previously best-known bound of $2\sqrt{n}$. Our result establishes that $sat^*(n,\mathcal{V}_3) = Θ(n)$.

ArXiv.org
Openalex Percentile: Top 43%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

The Induced Saturation Number for $\mathcal{V}_3$ is Linear · ArXiv.org (2025) | TGRS Research Map | TGRS