Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimit shape of perfect matchings on contracting bipartite graphs
53
0
0.0
(
0
)
Authors
Zhongyang Li
Ask ChatGPT about the research
No Arabic abstract
We consider random perfect matchings on a general class of contracting bipartite graphs by letting certain edge weights be 0 on the contracting square-hexagon lattice in a periodic way. We obtain a deterministic limit shape in the scaling limit. The results can also be applied to prove the existence of multiple disconnected liquid regions for all the contracting square-hexagon lattices with certain edge weights, extending the results proved in [13] for contracting square-hexagon lattices where the number of square rows in each period is either 0 or 1.
rate research
Read More
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to K{o}nigs work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(min{m, frac{n^{2.5}ln n}{d}})$; this minimum can never be larger than $O(n^{1.75}sqrt{ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(frac{nln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Kargers sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(msqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $ln^2 n$).
We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m sqrt{n})$ time, in regular bipartite graphs, a perfect matching is known to be computable in $O(m)$ time. Very recently, the $O(m)$ bound was improved to $O(min{m, frac{n^{2.5}ln n}{d}})$ expected time, an expression that is bounded by $tilde{O}(n^{1.75})$. In this paper, we further improve this result by giving an $O(min{m, frac{n^2ln^3 n}{d}})$ expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of $n$ alone, the algorithm takes expected time $O((nln n)^{1.5})$. To obtain this result, we design and analyze a two-stage sampling scheme that reduces the problem of finding a perfect matching in a regular bipartite graph to the same problem on a subsampled bipartite graph with $O(nln n)$ edges that has a perfect matching with high probability. The matching is then recovered using the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karp gives us an $tilde{O}(n^{1.5})$ running time, we present a tighter analysis for our special case that results in the stronger $tilde{O}(min{m, frac{n^2}{d} })$ time mentioned earlier. Our proof of correctness of this sampling scheme uses a new correspondence theorem between cuts and Halls theorem ``witnesses for a perfect matching in a bipartite graph that we prove. We believe this theorem may be of independent interest; as another example application, we show that a perfect matching in the support of an $n times n$ doubly stochastic matrix with $m$ non-zero entries can be found in expected time $tilde{O}(m + n^{1.5})$.
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G subseteq K_{n,n}$ has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $G subseteq K_{n,n}$ contains one of these minimum weight perfect matchings.
A well-known conjecture by Lovasz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with $n$ vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically $cgamma^n$, where $c>0$ and $gamma sim 1.14196$ is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
We consider the spectral gap of a uniformly chosen random $(d_1,d_2)$-biregular bipartite graph $G$ with $|V_1|=n, |V_2|=m$, where $d_1,d_2$ could possibly grow with $n$ and $m$. Let $A$ be the adjacency matrix of $G$. Under the assumption that $d_1geq d_2$ and $d_2=O(n^{2/3}),$ we show that $lambda_2(A)=O(sqrt{d_1})$ with high probability. As a corollary, combining the results from Tikhomirov and Youssef (2019), we confirm a conjecture in Cook (2017) that the second singular value of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. This also implies that the second eigenvalue of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. Assuming $d_2=O(1)$ and $d_1=O(n^2)$, we further prove that for a random $(d_1,d_2)$-biregular bipartite graph, $|lambda_i^2(A)-d_1|=O(sqrt{d_1(d_2-1)})$ for all $2leq ileq n+m-1$ with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook, Goldstein, and Johnson (2018) for random $d$-regular graphs and several new switching operations we defined for random bipartite biregular graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
