Skip to main content
MathOverflow

Timeline for Connected components $0-1$ matrices

Current License: CC BY-SA 3.0

53 events
when toggle format what by license comment
Apr 13, 2017 at 12:58 history edited CommunityBot
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Apr 13, 2017 at 12:19 history edited CommunityBot
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Dec 22, 2014 at 1:17 comment added fedja @Christian Remling Not in the slightest :-)) (wide grin). As to the first part, that is indeed an issue with all of us sometimes. Once the question is resolved as posed, let's see what is the simplest and clearest explicit construction we can come with. I'm as eager as The Masked Avenger to see it though I have no time to think of it myself at the moment.
Dec 21, 2014 at 22:55 history edited Turbo CC BY-SA 3.0
added 105 characters in body
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:54 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:53 vote accept Turbo
Dec 21, 2014 at 22:54
Dec 21, 2014 at 22:50 vote accept Turbo
Dec 21, 2014 at 22:53
Dec 21, 2014 at 22:49 history edited Turbo CC BY-SA 3.0
added 359 characters in body
Dec 21, 2014 at 22:44 vote accept Turbo
Dec 21, 2014 at 22:45
Dec 21, 2014 at 22:39 history edited Turbo CC BY-SA 3.0
added 443 characters in body
Dec 21, 2014 at 22:16 history edited Turbo CC BY-SA 3.0
added 816 characters in body
Dec 21, 2014 at 21:09 history edited Turbo CC BY-SA 3.0
deleted 384 characters in body
Dec 21, 2014 at 21:06 comment added Christian Remling @fedja: But maybe I think I have an idea what to do, even though I don't... Anyway, since you're being stubborn, I now wrote it up myself, I hope you don't mind :)
Dec 21, 2014 at 21:05 answer added Christian Remling timeline score: 11
Dec 21, 2014 at 21:03 comment added fedja @Turbo I have already explained how it ended as a comment ;-). Also, it is neither "my" (I wish I were 1/10000000 as brilliant as Paul Erdos), nor "idea" (the proof is complete, though the exposition may be somewhat terse). However I promise that if I find an explicit example before anybody else, I'll post it as an answer :-)
Dec 21, 2014 at 20:57 comment added fedja @Turbo We also have to take care of various possibilities of Mi that could make different matrices M ... Counting may give hints but unless lucky not a proof. Erm... What do you mean by that? Independent events remain independent regardless of the order in which you list them!
Dec 21, 2014 at 20:54 history edited Turbo CC BY-SA 3.0
added 334 characters in body
Dec 21, 2014 at 20:47 comment added fedja @The Masked Avenger I am hopeful for an explicit matrix of size 10 by 10 or smaller of at least 2 components. That can be easily done on a computer (at some point such matrices become an overwhelming majority). However, if the sentence is intended to mean "An explicit construction (nevermind the size) with a clear reason for impossibility", I concur :-).
Dec 21, 2014 at 20:40 comment added fedja @Christian Remling it's not what most of us would try first here Why??? Isn't "If you have no idea what to do, just do a random thing" as basic as "Eye for eye and tooth for tooth"? (at least, 50 or so years after Erdos demonstrated the efficacy of this principle in mathematics) :-). But, indeed, random graphs, random constructions, random sampling, etc. are beautiful and permeate all areas of modern science. Hail the fair Tyche! Coming back to Earth, I thought of posting it as an answer but then decided on a comment after seeing "Why is it on hold?" . Too late to change now.
Dec 21, 2014 at 19:58 comment added The Masked Avenger @fedja, sure. Hopefully the careful reader sees my recant a few comments later. I am hopeful for an explicit matrix of size 10 by 10 or smaller of at least 2 components.
Dec 21, 2014 at 19:35 comment added Christian Remling @fedja: That is beautiful, why don't you post it as an answer. It may be a standard trick (with hindsight), but it's not what most of us would try first here.
Dec 21, 2014 at 17:14 comment added fedja @The Masked Avenger Given that you claim a positive answer, it looks like we interpret the problem slightly differently again (just saying this in case one of us gets puzzled by the other's words :-) )
Dec 21, 2014 at 16:28 comment added fedja The answer is "No". Take a random size $n$ matrix with each entry being $1$ with probability $1/2$. Then the probability that we don't have any isolated $1$ is about $e^{-cn^2}$. The permutations are just $e^{Cn\log n}$, which (outside the state of Kansas) is a slower growing function. An old trick, of course, but still useful :-)
Dec 21, 2014 at 14:18 comment added Dima Pasechnik By definition, the diagonal matrix $I$ is connected.
Dec 21, 2014 at 13:24 history edited Turbo CC BY-SA 3.0
added 666 characters in body
Dec 21, 2014 at 13:06 comment added Dima Pasechnik Conjugation is certainly much harder to deal with.
Dec 21, 2014 at 12:57 comment added Dima Pasechnik do you require simultaneous permutations of rows and columns (i.e. conjugation by a permutation matrix)? Or you allow different permutations to permute rows and columns?
Dec 21, 2014 at 10:02 history rollback Turbo
Rollback to Revision 7
Dec 21, 2014 at 10:02 history edited Turbo CC BY-SA 3.0
deleted 1070 characters in body
Dec 21, 2014 at 5:58 history edited Turbo CC BY-SA 3.0
added 1072 characters in body
Dec 21, 2014 at 5:43 history edited Turbo CC BY-SA 3.0
added 613 characters in body
Dec 21, 2014 at 5:00 history reopened Turbo
Douglas Zare
j.c.
Allen Knutson
Peter Shor
Dec 21, 2014 at 4:39 history edited Turbo
edited tags
Dec 20, 2014 at 21:45 comment added Richard Stanley Why is this question on hold? It seems quite interesting to me.
Dec 20, 2014 at 21:10 history edited Turbo
edited tags
Dec 20, 2014 at 20:54 comment added Włodzimierz Holsztyński This question sounds so classically simple and charming that once you see it you cannot dismiss it. You have to say: yes, no, or I cannot answer it. There are no comments about the question being known. No simple argument was given to indicate that the problem is easy one way or another, so that its simplicity is deceptive. I see no reason why this question's value for MO should be doubted.
Dec 20, 2014 at 0:33 review Reopen votes
Dec 20, 2014 at 5:32
Dec 20, 2014 at 0:08 comment added The Masked Avenger trying for a minimal counterexample.
Dec 20, 2014 at 0:06 comment added The Masked Avenger Presently , all my attempts lack a piece of reasoning. I am now
Dec 18, 2014 at 9:04 history closed Misha
Ricardo Andrade
Yemon Choi
Gjergji Zaimi
Denis Serre 		Not suitable for this site
Dec 17, 2014 at 21:13 review Close votes
Dec 18, 2014 at 9:04
Dec 17, 2014 at 21:09 history edited Turbo CC BY-SA 3.0
added 237 characters in body
Dec 17, 2014 at 20:47 comment added The Masked Avenger Since you allow diagonal steps, all such matrices are connected. An inductive argument should handle an arbitrary rectangular 0-1 matrix.
Dec 17, 2014 at 20:41 history edited Turbo CC BY-SA 3.0
deleted 54 characters in body
Dec 17, 2014 at 20:35 history asked Turbo CC BY-SA 3.0
toggle format