论文标题
部分可观测时空混沌系统的无模型预测
Grid Induced Minor Theorem for Graphs of Small Degree
论文作者
论文摘要
如果Vertex Deletions和Edge收缩可以从$ g $获得$ h $，则图$ h $是图$ g $的少数。我们表明，有一个函数$ f（k，d）= o（k^{10} + 2^{d^5}）$，因此，如果图具有至少$ f（k，d）$和最高$ d $的treewidth，则它包含$ k \ times a $ k \ times a a $ k \ times k $ grid作为诱导的未成年人。这证明了Aboulker，Adler，Kim，Sintiari和Trotignon的猜想[Eur。 J. Comb。，98，2021]，任何具有较大树宽和界限最大程度的图形都包含大壁或大壁的线图作为诱导的子图。这也意味着对于任何固定的平面图$ H $，都有一种亚指数时间算法，用于$ h $诱导的无限制图上的最大重量独立设置。
A graph $H$ is an induced minor of a graph $G$ if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that there is a function $f(k, d) = O(k^{10} + 2^{d^5})$ so that if a graph has treewidth at least $f(k, d)$ and maximum degree at most $d$, then it contains a $k \times k$-grid as an induced minor. This proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon [Eur. J. Comb., 98, 2021] that any graph with large treewidth and bounded maximum degree contains a large wall or the line graph of a large wall as an induced subgraph. It also implies that for any fixed planar graph $H$, there is a subexponential time algorithm for maximum weight independent set on $H$-induced-minor-free graphs.
