Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.06402 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918328099930112 |
|---|---|
| author | Duan, Boyan Ouyang, Minghui Wang, Zheng |
| author_facet | Duan, Boyan Ouyang, Minghui Wang, Zheng |
| contents | We say that two partial orders on $[n]$ are compatible if there exists a partial order that refines both of them. This compatibility relation induces a natural set system structure between the collection $\mathcal{F}$ of all partial orders and the collection $\mathcal{G}$ of all total orders on $[n]$, where each order is associated with the set of orders compatible with it.
In this note, we determine the VC-dimension of $\mathcal{F}$ with respect to $\mathcal{G}$, proving that $\operatorname{VC}_{\mathcal{G}}(\mathcal{F}) = \lfloor\frac{n^2}{4}\rfloor$ for $n \ge 4$. We also establish bounds on the dual VC-dimension, showing that $2(n-3) \le \operatorname{VC}_{\mathcal{F}}(\mathcal{G}) \le n \log_2 n$ for all $n \ge 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06402 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | VC-dimensions Between Partially Ordered Sets and Totally Ordered Sets Duan, Boyan Ouyang, Minghui Wang, Zheng Combinatorics 05C20 (Primary), 05D05 (Secondary) We say that two partial orders on $[n]$ are compatible if there exists a partial order that refines both of them. This compatibility relation induces a natural set system structure between the collection $\mathcal{F}$ of all partial orders and the collection $\mathcal{G}$ of all total orders on $[n]$, where each order is associated with the set of orders compatible with it. In this note, we determine the VC-dimension of $\mathcal{F}$ with respect to $\mathcal{G}$, proving that $\operatorname{VC}_{\mathcal{G}}(\mathcal{F}) = \lfloor\frac{n^2}{4}\rfloor$ for $n \ge 4$. We also establish bounds on the dual VC-dimension, showing that $2(n-3) \le \operatorname{VC}_{\mathcal{F}}(\mathcal{G}) \le n \log_2 n$ for all $n \ge 1$. |
| title | VC-dimensions Between Partially Ordered Sets and Totally Ordered Sets |
| topic | Combinatorics 05C20 (Primary), 05D05 (Secondary) |
| url | https://arxiv.org/abs/2412.06402 |