Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2410.06812 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909725691478016 |
|---|---|
| author | Krone, Maximilian |
| author_facet | Krone, Maximilian |
| contents | For two families $\mathcal{A}, \mathcal{B} \subseteq \mathcal{P}([k])$, we write $\mathcal{A}\vdash\mathcal{B}$ if $A\not\supseteq B$ for each two sets $A \in \mathcal{A}$ and $B \in \mathcal{B}$. $\mathcal{A}$ and $\mathcal{B}$ are called incomparable if $\mathcal{A}\vdash\mathcal{B}$ and $\mathcal{B}\vdash\mathcal{A}$. Seymour proved that the maximum size of two incomparable equal-sized families in $\mathcal{P}([k])$ is $\frac{1}{4}2^k$.
A sequence of families $\mathcal{B}_1,\dots,\mathcal{B}_l \ \subseteq \mathcal{P}([k])$ is called $d$-exceeding if $\mathcal{B}_i\vdash\mathcal{B}_j$ for all $i,j\in [l]$ with $j-i\in [d]$. Cyclically reusing $d+1$ pairwise incomparable families yields arbitrarily long $d$-exceeding sequences of families. We prove inversely that the maximum size of equal-sized families of a sufficiently long $1$-exceeding sequence in $\mathcal{P}([k])$ is also $\frac{1}{4}2^k$.
A sequence of sets $B_1,\dots,B_l \subseteq [k]$ is called $d$-exceeding if $\{B_1\},\dots,\{B_l\}$ is $d$-exceeding, that is, if $B_i \not\supseteq B_j$ for all $i,j\in [l]$ with $j-i\in [d]$. We locate the maximum $d$ such that there exist arbitrarily long $d$-exceeding sequences of subsets of $[k]$ between $(1-o(1)) \tfrac{1}{e} 2^k$ and $\tfrac{1}{2}2^k-2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06812 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On an acyclic relaxation of incomparable families of sets Krone, Maximilian Combinatorics 05D05 For two families $\mathcal{A}, \mathcal{B} \subseteq \mathcal{P}([k])$, we write $\mathcal{A}\vdash\mathcal{B}$ if $A\not\supseteq B$ for each two sets $A \in \mathcal{A}$ and $B \in \mathcal{B}$. $\mathcal{A}$ and $\mathcal{B}$ are called incomparable if $\mathcal{A}\vdash\mathcal{B}$ and $\mathcal{B}\vdash\mathcal{A}$. Seymour proved that the maximum size of two incomparable equal-sized families in $\mathcal{P}([k])$ is $\frac{1}{4}2^k$. A sequence of families $\mathcal{B}_1,\dots,\mathcal{B}_l \ \subseteq \mathcal{P}([k])$ is called $d$-exceeding if $\mathcal{B}_i\vdash\mathcal{B}_j$ for all $i,j\in [l]$ with $j-i\in [d]$. Cyclically reusing $d+1$ pairwise incomparable families yields arbitrarily long $d$-exceeding sequences of families. We prove inversely that the maximum size of equal-sized families of a sufficiently long $1$-exceeding sequence in $\mathcal{P}([k])$ is also $\frac{1}{4}2^k$. A sequence of sets $B_1,\dots,B_l \subseteq [k]$ is called $d$-exceeding if $\{B_1\},\dots,\{B_l\}$ is $d$-exceeding, that is, if $B_i \not\supseteq B_j$ for all $i,j\in [l]$ with $j-i\in [d]$. We locate the maximum $d$ such that there exist arbitrarily long $d$-exceeding sequences of subsets of $[k]$ between $(1-o(1)) \tfrac{1}{e} 2^k$ and $\tfrac{1}{2}2^k-2$. |
| title | On an acyclic relaxation of incomparable families of sets |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2410.06812 |