Timeline for Finding the set of all $0$-$1$ vectors in an affine subspace
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 19, 2015 at 12:31 | history | edited | Anurag | CC BY-SA 3.0 |
added information about the automorphism group
|
| Jan 19, 2015 at 4:25 | history | edited | Amritanshu Prasad | CC BY-SA 3.0 |
added 4 characters in body; edited title
|
| Jan 19, 2015 at 2:29 | history | edited | Anurag |
edited tags
|
|
| Jul 19, 2014 at 1:41 | answer | added | Max Alekseyev | timeline score: 2 | |
| Jul 10, 2014 at 0:26 | comment | added | Anurag | I should point out that the dancing links algorithm of Knuth (sagemath.org/doc/reference/combinat/sage/combinat/matrices/…) works pretty well for small cases. | |
| Jul 10, 2014 at 0:15 | history | edited | Anurag | CC BY-SA 3.0 |
added 1 character in body
|
| Jul 9, 2014 at 23:08 | history | edited | Anurag | CC BY-SA 3.0 |
added an alternate view of this problem using hypergraphs
|
| Jul 8, 2014 at 11:12 | comment | added | Anurag | It's only for those cases, the so called thin geometries, where it amounts to finding perfect matchings. I had posted another question regarding that earlier (mathoverflow.net/questions/168241/…). But in more general cases it doesn't reduce to finding perfect matchings. | |
| Jul 8, 2014 at 11:09 | comment | added | Emil Jeřábek | I can’t say I know anything about incidence geometry, but if your problem amounts to finding perfect matchings as your last comment suggests, there are efficient polynomial-time algorithms for that. | |
| Jul 8, 2014 at 10:58 | history | edited | Anurag | CC BY-SA 3.0 |
Removed the example which simply did not have any such solution.
|
| Jul 8, 2014 at 10:57 | comment | added | Anurag | @NoamD.Elkies: Thank you for pointing it out. I should have put a better example. The particular ones that I am working with are generalized polygons. For example, if you look at the flag geometry of classical projective plane of order $q$ then you get a generalized hexagon of order $(q,1)$ which certainly has such a solution (corresponding to a perfect matching in the incidence graph of the projective plane). | |
| Jul 7, 2014 at 19:36 | comment | added | Gerhard Paseman | If you want to take advantage of symmetry, then you can shave off an order of magnitude or more running time by looking at just isomorphism types of structures built from a few columns. If there is a solution, there will be "lots" of them, and Robert Israel's suggestion has a chance of finishing quickly. Gerhard "Ask Me About System Design" Paseman, 2014.07.07 | |
| Jul 7, 2014 at 19:31 | comment | added | Gerhard Paseman | Also, the column sum better divide the number of rows of the matrix, otherwise you're stopped at the starting gate. Given the quotient q, one is "reduced" to n choose q possibilities. Gerhard "Divide And Conquer Also Works" Paseman, 2014.07.07 | |
| Jul 7, 2014 at 18:24 | comment | added | Noam D. Elkies | For a finite projective plane (whether classical or not) there can't be any solution, because you're asking for a set $S$ of points that meets every line in just one point, but then $|S|>1$ and the line through any two points of $S$ yields a contradiction. | |
| Jul 7, 2014 at 18:12 | answer | added | Robert Israel | timeline score: 4 | |
| Jul 7, 2014 at 17:53 | history | asked | Anurag | CC BY-SA 3.0 |