2
$\begingroup$

Suppose $n,k$ are positive integers such that $k\mid n$.

Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every matching having $k$ edges.

Let $g(n,k)$ be the maximum of $m(H)$ where $H$ runs over all such graphs. Then it is easy to see that $(\frac{n}{k})^2\leq g(n,k)\leq \frac{n(n+1-k)}{k}$.

Is there any better upper bound of $g(n,k)$?

Improve this question
$\endgroup$
4
  • $\begingroup$ I guess you mean "Consider a bipartite graph H...". Can you please check if my edits agree with what you mean? $\endgroup$
    – Wolfgang
    Commented Jul 8, 2016 at 17:36
  • 1
    $\begingroup$ In the case when $k$ is linear in $n$, some sharp bounds are given by Fox, Huang and Sudakov: people.math.ethz.ch/~sudakovb/linear-induced-matchings.pdf $\endgroup$
    – Shagnik
    Commented Jul 8, 2016 at 22:15
  • $\begingroup$ Wolfgang: Yes, your edits agree with what I mean. Thank you! $\endgroup$
    – user173856
    Commented Jul 9, 2016 at 8:56
  • $\begingroup$ Shagnik: Thank you very much for your help! $\endgroup$
    – user173856
    Commented Jul 9, 2016 at 8:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .