论文标题
高立方体中顶点诱导的完美循环和路径的最大密度
Maximum density of vertex-induced perfect cycles and paths in the hypercube
论文作者
论文摘要
令$ h $和$ k $为顶点套装$ v（q_d）$的子集，$ d $ -cube $ q_d $（我们称为$ h $和$ k $ configurations in $ q_d $）。我们说$ k $是$ h $的\ emph {确切复制}，如果有$ q_d $的自动形态，将$ h $发送到$ k $。如果$ d $是一个正整数，而$ h $是$ q_d $中的配置，我们将$π（h，d）$定义为限制为$ n $，将最大分数的无限属于无限，与所有子集$ s $ s $ s $ s $ s $ s $ v（q_n）$，sub-d $ d $ d $ c_n的$ q_n $相关$ $ $ h $ he is s n is n is n is n is akecre n is n is akecy n is akecy n insecy $。我们确定$π（C_8,4）$和$π（p_4,3）$，其中$ c_8 $是$ q_4 $的“完美” 8个周期，$ q_4 $和$ p_4 $是一条“完美”路径，带有4个顶点$ q_3 $，并构成$π（c_ {2d}，d），$ $ $ $ $ $ $ $ p_ $ d+d+d+d;在我们的证据中，有与计算某些属性的序列数量以及某些小图的诱导性的联系。特别是，我们需要确定两分图家族中两个顶点分离边缘的诱导性。
Let $H$ and $K$ be subsets of the vertex set $V(Q_d)$ of the $d$-cube $Q_d$ (we call $H$ and $K$ configurations in $Q_d$). We say $K$ is an \emph{exact copy} of $H$ if there is an automorphism of $Q_d$ which sends $H$ to $K$. If $d$ is a positive integer and $H$ is a configuration in $Q_d$, we define $π(H,d)$ to be the limit as $n$ goes to infinity of the maximum fraction, over all subsets $S$ of $V(Q_n)$, of sub-$d$-cubes of $Q_n$ whose intersection with $S$ is an exact copy of $H$. We determine $π(C_8,4)$ and $π(P_4,3)$ where $C_8$ is a "perfect" 8-cycle in $Q_4$ and $P_4$ is a "perfect" path with 4 vertices in $Q_3$, and make conjectures about $π(C_{2d},d)$ and $π(P_{d+1},d)$ for larger values of $d$. In our proofs there are connections with counting the number of sequences with certain properties and with the inducibility of certain small graphs. In particular, we needed to determine the inducibility of two vertex disjoint edges in the family of bipartite graphs.
