标题： 关于路径笛卡尔积的诱导子图 显示英文标题

标题： On Induced Subgraph of Cartesian Product of Paths

摘要： Chung, Füredi, Graham 和 Seymour（JCTA, 1988）构造了一个超立方体$Q^n$的诱导子图，该子图有$\alpha(Q^n)+1$个顶点，并且最大度小于$\lceil \sqrt{n} \rceil$。 随后，黄（数学年刊，2019）通过证明超立方体$Q^n$的这种诱导子图的最大度数至少为$\lceil \sqrt{n} \rceil$，从而证明了敏感性猜想，并提出了一个问题：给定一个图$G$，设$f(G)$是图$G$在$\alpha(G)+1$个顶点上的诱导子图的最大度数的最小值，我们能对$f(G)$说些什么？ 在本文中，我们研究路径的笛卡尔积$P_m$的这个问题，记为$P_m^k$。 我们确定当$m=2n+1$时$f(P_{m}^k)$的精确值，通过证明对于$n\geq 2$和$f(P_3^k)=2$有$f(P_{2n+1}^k)=1$，并在$m=2n$时给出$f(P_{m}^k)$的非平凡下界，通过证明$f(P_{2n}^k)\geq \lceil \sqrt{\beta_nk}\rceil$。 特别是，当 $n=1$时，我们有 $f(Q^k)=f(P_{2}^k)\ge \sqrt{k}$，这是黄的结果。 $f(P_{3}^k)$ 和 $f(P_{2n}^k)$ 的下界是通过黄提供的谱方法给出的。 显示英文摘要

摘要： Chung, F\"uredi, Graham, and Seymour (JCTA, 1988) constructed an induced subgraph of the hypercube $Q^n$ with $\alpha(Q^n)+1$ vertices and with maximum degree smaller than $\lceil \sqrt{n} \rceil$. Subsequently, Huang (Annals of Mathematics, 2019) proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube $Q^n$ is at least $\lceil \sqrt{n} \rceil$, and posed the question: Given a graph $G$, let $f(G)$ be the minimum of the maximum degree of an induced subgraph of $G$ on $\alpha(G)+1$ vertices, what can we say about $f(G)$? In this paper, we investigate this question for Cartesian product of paths $P_m$, denoted by $P_m^k$. We determine the exact values of $f(P_{m}^k)$ when $m=2n+1$ by showing that $f(P_{2n+1}^k)=1$ for $n\geq 2$ and $f(P_3^k)=2$, and give a nontrivial lower bound of $f(P_{m}^k)$ when $m=2n$ by showing that $f(P_{2n}^k)\geq \lceil \sqrt{\beta_nk}\rceil$. In particular, when $n=1$, we have $f(Q^k)=f(P_{2}^k)\ge \sqrt{k}$, which is Huang's result. The lower bounds of $f(P_{3}^k)$ and $f(P_{2n}^k)$ are given by using the spectral method provided by Huang.