A unified combinatorial view beyond some spectral properties

Abstract

Let $\beta >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,\beta )$-graph if $\frac{|X||Y|}{(n-|X|)(n-|Y|)}\le {\beta }^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,\beta )$-graph if in addition $X$ and $Y$ are not necessarily disjoint. Our main results include the following. (i) For any weakly $(n,\beta )$-graph $G$, the matching number ${\alpha }^{\prime }(G)\ge \min \left\{\frac{1-\beta }{1+\beta },\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 ${\alpha }^{\prime }(G)\ge \min \{t(1-2{\beta }^2),1\}\cdot |U|$. (ii) For any $(n,\beta )$-graph $G$, ${\alpha }^{\prime }(G)\ge \min \left\{\frac{2-\beta }{2(1+\beta )},\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 ${\alpha }^{\prime }(G)\ge \min \{1/{\beta }^2,1\}\cdot |U|$. (iii) If $G$ is a weakly $(n,\beta )$-graph for $0<\beta \le 1/3$ or an $(n,\beta )$-graph for $0<\beta \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,\beta )$-graph $G$, the toughness $t(G)\ge \frac{1-\beta }{\beta }$. For any connected weakly $(n,\beta )$-graph $G$, $t(G)>\frac{5(1-\beta )}{11\beta }$ and if $n$ is large enough, then $t(G)>\left(\frac{1}{2}-\epsilon \right)\frac{1-\beta }{\beta }$ for any $\epsilon >0$.