3
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ 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.) $\endgroup$ Dec 15, 2010 at 15:08
  • $\begingroup$ 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. $\endgroup$ Dec 15, 2010 at 16:08
  • $\begingroup$ 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 :) $\endgroup$
    – Pradipta
    Dec 15, 2010 at 16:09
  • $\begingroup$ 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. $\endgroup$ Dec 15, 2010 at 16:21
  • $\begingroup$ Thanks to both Andrew and Bill. I’ll take a look at both papers. $\endgroup$
    – Pradipta
    Dec 15, 2010 at 16:24

2 Answers 2

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Just emphasizing the upper bound of 1. I guess one could rephrase in the terms the maximum row sum as well. $\endgroup$
    – Pradipta
    Dec 15, 2010 at 19:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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