论文标题
统一的组合视图超出了某些光谱特性
A unified combinatorial view beyond some spectral properties
论文作者
论文摘要
令$β> 0 $。由托马森（Thomason）定义的杂耍图的动机，著名的扩展器混合引理和呼毒者的顶点分离不等式，我们定义了一个图形$ g $，带有$ n $ vertices是一个弱$ $（n，β）$ - 图形，如果$ \ frac {| x | x | x | x | x | x | x | x | x | y |} {（n- | x |）（n- | y |）} \leβ^2 $持有每对差异$ x，y $ x，y $ of $ v（g）$，$ x $和$ y $之间，并且它是$（n，β）$之间的$ x $和$ y $，如果添加了$ x $和$ x $和$ y $，则不一定是$ x $和y $。我们的主要结果包括以下内容。 （i）对于任何弱$（n，β）$ - 图$ g $，匹配的数字$α'（g）\ ge \ min \ min \ left \ left \ {\ frac {1-β} {1+β}，\，\，\ frac {1} {1} {2} {2} {2} {2} {2} {2} {2} {2} {2} {2} \ right \ right \} \ is a $ g cdot（n-1） w）$ - $ - 两分的图形，带有$ | w | \ ge t | u | $ white $ t \ ge 1 $，然后$α'（g）\ ge \ min \ \ {t（1-2β^2），1 \} \ cdot | u | $。 （ii）对于任何$（n，β）$ - 图$ g $，$α'（g）\ ge \ min \ min \ left \ {\ frac {\ frac {2-β} {2（1+β）}，\，\，\ frac {1} {2} {2} {2} {2} {2} \ right \ right \ right \ cdot bragry bragr $ | w | \ ge | u | $，没有孤立的顶点，然后$α'（g）\ ge \ min \ {1/β^{2}，1 \} \ cdot | u | $。 （iii）如果$ g $是一个弱$（n，β）$ - $ 0 <β\ le 1/3 $或$（n，β）$ - $ 0 <β\ le 1/2 $的图形，则$ g $具有分数的完美匹配。此外，当$ n $均匀时，$ g $具有完美的匹配，而当$ n $奇怪时，$ g $至关重要。 （iv）对于任何连接的$（n，β）$ - 图$ g $，韧性$ t（g）\ ge \ frac {1-β}β$。对于任何连接的弱$（n，β）$ - 图$ g $，$ t（g）> \ frac {5（1-β）} {11β} $，如果$ n $足够大，则$ t（g）> \ left（\ frac {1} {1} {2} {2} {2} {2} - \ varepsilon \ frac f rice noth $ frac f ric ab y.1-1-1- > 0 $。
Let $β>0$. Motivated by jumbled graphs defined by Thomason, the celebrated expander mixing lemma and Haemers's vertex separation inequality, we define that a graph $G$ with $n$ vertices is a weakly $(n,β)$-graph if $\frac{|X| |Y|}{(n-|X|)(n-|Y|)} \le β^2$ holds for every pair of disjoint proper subsets $X, Y$ of $V(G)$ with no edge between $X$ and $Y$, and it is an $(n,β)$-graph if in addition $X$ and $Y$ are not necessarily disjoint. Our main results include the following. (i) For any weakly $(n,β)$-graph $G$, the matching number $α'(G)\ge \min\left\{\frac{1-β}{1+β},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$-bipartite graph with $|W|\ge t|U|$ where $t\ge 1$, then $α'(G)\ge \min\{t(1-2β^2),1\}\cdot |U|$. (ii) For any $(n,β)$-graph $G$, $α'(G)\ge \min\left\{\frac{2-β}{2(1+β)},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$-bipartite graph with $|W|\ge |U|$ and no isolated vertices, then $α'(G)\ge \min\{1/β^{2},1\}\cdot |U|$. (iii) If $G$ is a weakly $(n,β)$-graph for $0<β\le 1/3$ or an $(n,β)$-graph for $0<β\le 1/2$, then $G$ has a fractional perfect matching. In addition, $G$ has a perfect matching when $n$ is even and $G$ is factor-critical when $n$ is odd. (iv) For any connected $(n,β)$-graph $G$, the toughness $t(G)\ge \frac{1-β}β$. For any connected weakly $(n,β)$-graph $G$, $t(G)> \frac{5(1-β)}{11β}$ and if $n$ is large enough, then $t(G) >\left(\frac{1}{2}-\varepsilon\right)\frac{1-β}β$ for any $\varepsilon >0$.
