A unified combinatorial view beyond some spectral properties
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 (n−∣X∣)(n−∣Y∣)∣X∣∣Y∣≤β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)≥min{1+β1−β,21}⋅(n−1). If in addition G is a (U,W)-bipartite graph with ∣W∣≥t∣U∣ where t≥1, then α′(G)≥min{t(1−2β2),1}⋅∣U∣. (ii) For any (n,β)-graph G, α′(G)≥min{2(1+β)2−β,21}⋅(n−1). If in addition G is a (U,W)-bipartite graph with ∣W∣≥∣U∣ and no isolated vertices, then α′(G)≥min{1/β2,1}⋅∣U∣. (iii) If G is a weakly (n,β)-graph for 0<β≤1/3 or an (n,β)-graph for 0<β≤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)≥β1−β. For any connected weakly (n,β)-graph G, t(G)>11β5(1−β) and if n is large enough, then t(G)>(21−ε)β1−β for any ε>0.
