MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A$ be a $n \times n$ matrix with non-negative entries $a_{ij}$, where $a_{ij}$ is the entry in the $i^{th}$ row and $j^{th}$ column. Assume $\sum_{1 \leq j \leq n} a_{ij} \leq 1$ for all $1 \leq i \leq n$. Also assume $a_{ii} = 0$ for all $1 \leq i \leq n$.

I want to partition the index set $I = \{1, 2 \ldots n\}$ into minimum number of sets $I_1, I_2, \ldots I_t$ so that the column sum is bounded by $1$ in each sub-matrix defined by the sets, or more formally:

  1. $\cup_{1 \leq k \leq t} I_k = I$
  2. For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$
  3. The number $t$ is minimized

I can construct examples where $t$ has to be at least $2$, on the other hand, $t = \Theta(\log n)$ would suffice for all such matrices. I am wondering if a tighter bound exists.

Motivation: this is a sort of generalization of the coloring problem in bounded out-degree digraphs. If a di-graph has out-degree upper bounded by $k$ it can be colored with $k + 1$ colors.

share|cite|improve this question
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.) – Andrew D. King Dec 15 '10 at 15:08
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. – Bill Johnson Dec 15 '10 at 16:08
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 :) – Pradipta Dec 15 '10 at 16:09
Yes, that's what I mean. Here is the link for the original Alon-Tarsi paper , but you might get more out of it by looking at the papers which cite it, for example . 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. – Andrew D. King Dec 15 '10 at 16:21
Thanks to both Andrew and Bill. I’ll take a look at both papers. – Pradipta Dec 15 '10 at 16:24

Why the qualification "bounded row-sums" for a matrix of finite dimension?

share|cite|improve this answer
Just emphasizing the upper bound of 1. I guess one could rephrase in the terms the maximum row sum as well. – Pradipta Dec 15 '10 at 19:42
up vote 0 down vote accepted

Ok, I think there are examples where $\Omega(\log n)$ colors are needed.

Here’s an example, let $a_{ij} = \frac{1}{i}$ for $j < i$ and $a_{ij} = \frac{1}{j^2}$ for $j > i$. Then $\sum_{j} a_{ij} = \frac{i-1}{i} + \sum_{j > i} \frac{1}{j^2} = O(1)$. Of course, the bound is $O(1)$ instead of $1$, but that can be normalized and all that.

However, note that $\sum_j a_{j1} = \Omega(\log n)$ and if we only have $o(\log n)$ partitions, this sum cannot be "distributed" into small enough parts.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.