Timeline for Partitioning a matrix with bounded row sums
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2011 at 0:00 | history | edited | Pradipta | CC BY-SA 2.5 |
deleted 64 characters in body
|
| Mar 2, 2011 at 0:00 | comment | added | Pradipta | You’re right...I must have been not thinking. | |
| Mar 1, 2011 at 23:43 | comment | added | Gerhard Paseman | If A is symmetric, then transpose A = A, so you have nothing left to do. Or do I misunderstand? Gerhard "Ask Me About System Design" Paseman, 2011.03.01 | |
| Mar 1, 2011 at 23:08 | history | edited | Pradipta | CC BY-SA 2.5 |
new version
|
| Dec 17, 2010 at 16:46 | vote | accept | Pradipta | ||
| Dec 16, 2010 at 15:58 | answer | added | Pradipta | timeline score: 0 | |
| Dec 16, 2010 at 0:29 | history | edited | Pradipta | CC BY-SA 2.5 |
Missing condition per fedja's observation
|
| Dec 16, 2010 at 0:28 | comment | added | Pradipta | Aha, you are correct. The diagonal is zero. I am updating the description. | |
| Dec 15, 2010 at 23:36 | comment | added | fedja | Something is wrong with the question as posed: take the lower triangular matrix with small positive elements $b_{ij}$ below the diagonal and the diagonal elements $d_i$ making sum $1$ in each row. Now, if every element $a_{km}$ is greater than the sum of all $a_{ij}$ with $i<k$, you cannot even choose a two-element $I_p$ and the answer becomes $n$. | |
| Dec 15, 2010 at 21:00 | comment | added | Suvrit | sorry, i oversaw the $j \in I_k$. | |
| Dec 15, 2010 at 19:43 | comment | added | Pradipta | @Suvrit: two colors? one for $j$, one for everyone else. | |
| Dec 15, 2010 at 19:26 | answer | added | izmirlig | timeline score: 0 | |
| Dec 15, 2010 at 17:28 | comment | added | Suvrit | what happens to the matrix: $a_{ij}=1$ for $j=1$ and $0$ otherwise? | |
| Dec 15, 2010 at 16:35 | history | edited | Pradipta | CC BY-SA 2.5 |
minor notation fix
|
| Dec 15, 2010 at 16:24 | comment | added | Pradipta | Thanks to both Andrew and Bill. I’ll take a look at both papers. | |
| Dec 15, 2010 at 16:21 | comment | added | Andrew D. King | Yes, that's what I mean. Here is the link for the original Alon-Tarsi paper springerlink.com/content/u627qn50r7013363 , but you might get more out of it by looking at the papers which cite it, for example onlinelibrary.wiley.com/doi/10.1002/jgt.20500/abstract . The proof of their result, which relates to list colourings, uses combinatorial nullstellensatz, which is useful but intimidating. Better to look at what you can do using their theorem as a black box, first. | |
| Dec 15, 2010 at 16:09 | comment | added | Pradipta | Well, when you say "the maximum out-degree to any colour" if you mean, the maximum weighted out-degree from any node to nodes of the same color, they yes. I actually didn’t know about the theorem you mention :) | |
| Dec 15, 2010 at 16:08 | comment | added | Bill Johnson | Look at A remark on finite-dimensional $P\sb{\lambda }$-spaces by J. Bourgain Studia Mathematica [0039-3223] Bourgain yr: 1982 vol: 72 iss: 3 pg: 285 -289. | |
| Dec 15, 2010 at 15:08 | comment | added | Andrew D. King | So to rephrase the question, you take an edge-weighted digraph with maximum in-degree $k$, and you want to $t$-colour the vertices such that the maximum out-degree to any colour is $k$, right? (I guess you know about the Alon-Tarsi list colouring theorem.) | |
| Dec 15, 2010 at 14:30 | history | asked | Pradipta | CC BY-SA 2.5 |