10
$\begingroup$

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$, $$ \int_{[0,1]^{2n}} \prod_{\substack{1 \le i, j \le n \\ i \neq j}}(1 - x_iy_j) \, dx_1 \cdots dx_n dy_1 \cdots dy_n = (e^{-1}+o(1))\frac{n \log n}{n!}. $$ The LHS can be rewritten, using the language of graphons, as $t(H_n, W)$, where $H_n$ is $K_{n,n}$ minus a perfect matching and $W(x,y) = 1 - xy$.

  • Is there a general technique for determining the asymptotic expression of $t(H_n, W)$ as $n \to \infty$, for a fixed graphon $W$ and a nice sequence of graphs $H_n$ (e.g., $K_n$, $K_{n,n}$)?

  • Are there other interesting cases where the asymptotics have been determined (perhaps with applications)?

$\endgroup$
  • $\begingroup$ I think Jan Hladky and coauthors did quite some work on this kind of thing - the short version seems to be that there probably is no such technique, even for nice sequences of graphs, unless you also place restrictions on your graphon. One can easily enough encode hard problems into the graphon. But maybe the answer becomes positive if the graphon has a nice structure (say polynomial, or piecewise polynomial)? In any case, I probably cannot help much, normally I would ask you such a question. $\endgroup$ – user36212 Jun 14 '16 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.