Timeline for Existence of a permutation matrix on a restricted support
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2017 at 18:46 | comment | added | Gerhard Paseman | An example that is helpful for me is the matrix with last k rows and last k columns filled with 1's, and 0's in the upper left. If k is less than d/2, this matrix contains no permutation matrix in your sense. Gerhard "Or In My Sense Either" Paseman, 2017.06.18. | |
| S Jun 18, 2017 at 12:16 | history | suggested | Daniel Soudry | CC BY-SA 3.0 |
Explained mapping to bipartite graph; changed A,B to X,Y to avoid confusion with question notation; and added definition of n(S)
|
| Jun 18, 2017 at 9:38 | comment | added | Fedor Petrov | We do not need Hall's theorem when $k\geqslant \lceil d/2\rceil$. If $(a_i,b_i),i=1,\dots,k$ is a maximal matching and $a,b$ are the vertices from $A,B$ uncovered by it, then by pigeonhole principle there exists $i$ such that $a$ is joined with $b_i$ and $b$ with $a_i$, this allows to increase our matching. | |
| Jun 18, 2017 at 9:07 | comment | added | Daniel Soudry | Many thanks! I missed this connection. | |
| Jun 18, 2017 at 9:06 | vote | accept | Daniel Soudry | ||
| Jun 18, 2017 at 9:06 | review | Suggested edits | |||
| S Jun 18, 2017 at 12:16 | |||||
| Jun 18, 2017 at 8:13 | history | answered | Douglas Zare | CC BY-SA 3.0 |