Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.03408 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912632002314240 |
|---|---|
| author | Bodnár, Levente Pikhurko, Oleg |
| author_facet | Bodnár, Levente Pikhurko, Oleg |
| contents | We consider two types of problems: maximising, over subsets $S\subseteq \{0,1\}^n$, the density of $d$-subcubes $C$ in the $n$-hypercube graph that span a subgraph such that $S\cap C$ is i) isomorphic to the given configuration $H\subseteq\{0,1\}^d$ (the inducibility problem), or ii) has the given size $s$ (the statistics problem). Using flag algebras, we determine the limit of this density as $n\to\infty$ for 5 new configurations $H\subseteq\{0,1\}^3$ and for 3 new pairs $(d,s)$, namely for $(3,2)$, $(4,2)$ and $(4,4)$. Interestingly, the lower bounds in the last three cases come from blowups of small Hamming codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_03408 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some exact values of the inducibility and statistics constants for hypercubes Bodnár, Levente Pikhurko, Oleg Combinatorics 05D05, 05C35 We consider two types of problems: maximising, over subsets $S\subseteq \{0,1\}^n$, the density of $d$-subcubes $C$ in the $n$-hypercube graph that span a subgraph such that $S\cap C$ is i) isomorphic to the given configuration $H\subseteq\{0,1\}^d$ (the inducibility problem), or ii) has the given size $s$ (the statistics problem). Using flag algebras, we determine the limit of this density as $n\to\infty$ for 5 new configurations $H\subseteq\{0,1\}^3$ and for 3 new pairs $(d,s)$, namely for $(3,2)$, $(4,2)$ and $(4,4)$. Interestingly, the lower bounds in the last three cases come from blowups of small Hamming codes. |
| title | Some exact values of the inducibility and statistics constants for hypercubes |
| topic | Combinatorics 05D05, 05C35 |
| url | https://arxiv.org/abs/2503.03408 |