1-Factorizations of Pseudorandom Graphs
1-Factorizations of Pseudorandom Graphs
复制标题
1-伪随机图的因式分解
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Vishesh Jain
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Vishesh Jain
图G的1因子是Edge-disexind匹配的集合常规的匡威很容易被认为是错误的，我们会发现一个常规的伪和图形。图G（即，在N顶点上的d-regular图最多为λ，其第二大特征值最多为λ），只要n是偶数，c_0≤d≤n-n-1（其中c_0 = c_0）（其中c_0 = c_0（其中） ε）仅取决于ε），尤其是λ≤d^1-ε，因为（众所周知）典型的随机D-regrular d-regular Gragr G_N，D是这样的图形对于所有C_0≤d≤n-1，在典型的G_N中进行1次分化，从而扩展到Janson获得的所有D结果的所有可能值，并独立于Molloy，Robalewska，Robinson和Wormald延伸到固定d。此外，我们还获得了此类图G的不同1次拟合数的下限，该数字在已知的上限中降低了指数底部的2倍。即使在最简单的情况下，我们的证明是概率的，并且可以轻松地将其变成多项式时间（随机）算法， ^nd /2也比以前最著名的下限。
A 1-factorization of a graph G is a collection of edge-disjoint perfect matchings whose union is E(G). A trivial necessary condition for G to admit a 1-factorization is that |V(G)| is even and G is regular; the converse is easily seen to be false. In this paper, we consider the problem of finding 1-factorizations of regular, pseudorandom graphs. Specifically, we prove that for any ε > 0, an (n, d,λ)-graph G (that is, a d-regular graph on n vertices whose second largest eigenvalue in absolute value is at most λ) admits a 1-factorization provided that n is even, C_0 ≤ d ≤ n-1 (where C_0=C_0(ε) is a constant depending only on ε), and λ ≤ d^1-ε. In particular, since (as is well known) a typical random d-regular graph G_n, d is such a graph, we obtain the existence of a 1-factorization in a typical G_n, d for all C_0 ≤ d ≤ n-1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1-factorizations of such graphs G which is off by a factor of 2 in the base of the exponent from the known upper bound. This lower bound is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph. Our proofs are probabilistic and can be easily turned into polynomial time (randomized) algorithms.