论文标题
向后滚动可以使您前进：在稀疏扩张器中嵌入问题
Rolling backwards can move you forward: on embedding problems in sparse expanders
论文作者
论文摘要
我们开发了一种基于Friedman-Pippenger树嵌入技术（1987）及其算法版本的通用嵌入方法，这基本上是由于Aggarwal等人所致。 （1996年），增强了滚动式的想法，允许依次回击先前执行的嵌入步骤。我们使用此方法获得以下结果。 - 我们表明，有界度图的对数长细分的尺寸 - 刺激数在其顶点的数量中是线性的，这解决了PAK的猜想（2002）。 - 我们给出一个确定性的，多项式的在线算法，用于在扩展器图中的给定顶点对之间找到处方长度的顶点 - 偶口路径。我们的结果回答了Alon和Capalbo（2007）的问题。 - 我们表明，$ d $的光谱比率相对较弱的界限迫使存在$ k_t $的拓扑小调，其中$ t =（1-o（1））d $。我们还展示了一个结构，该结构表明，即使$λ= o（\ sqrt {d}）$，理论最大$ t = d+1 $也无法实现。这回答了Fountoulakis，Kühn和Osthus（2009）的问题。
We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. We use this method to obtain the following results. -We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak (2002). -We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo (2007). -We show that relatively weak bounds on the spectral ratio of $d$-regular graphs force the existence of a topological minor of $K_t$ where $t=(1-o(1))d$. We also exhibit a construction which shows that the theoretical maximum $t=d+1$ cannot be attained even if $λ=O(\sqrt{d})$. This answers a question of Fountoulakis, Kühn and Osthus (2009).
