1
$\begingroup$

For each $(i,j)\in \mathbb{N}^2$, $a(i,j)=1$ or $0$, and 1) $a(i,i)=0$ for all $i$; 2)for fixed $i$, there is at most one $j$ such that $a(i,j)=1$. Suppose we know that there is a finite $\kappa$ such that \begin{equation} \sum_{i\in S, j\in S^{C}}a(i,j)\le\kappa\end{equation} for any subset $S$ of $\mathbb{N}$,then one can show $\sum a(i,j)$ is bounded by $3\kappa$.

I am asking what is the largest possible value of $\sum a(i,j)$.

For people who are interested in the background, I am considering an operator $T\in\mathcal{L}(\ell^2)$. With respect to the natural basis, the entries of $T$ are $a(i,j)$. The existence of $\kappa$ in the first inequality is the same as \begin{equation}rank(TP-PTP)\le\kappa\end{equation} for all orthogonal projections $P$ in the masa (maximal abelian, self-adjoint subalgebra) of diagonal operators.

In a recent paper by Popov, Marcoux and Radjavi (Almost Invariant Halfspaces and Approximate Commutation), they have shown $\sum a(i,j)$ is bounded by $3\kappa$ (Thm 4.7), but in almost all examples I can think of, $\sum a(i,j)\le 2\kappa$, so I wonder whether the coefficient can be improved.

Again, I think the problem has been reduced to a purely algebraic or number theoretic problem in the first two paragraph of this post.

Thanks very much!

  • 0
    Do you mean $\sum_{i\neq j} a(i,j)$? Else why couldn't $a(i,i)=1$ for all $i$?2012-06-22
  • 0
    @ErickWong Thanks! I have corrected my post by imposing $a(i,i)=0$ for all $i$. This corresponds to a trivial case in the original problem.2012-06-23
  • 0
    Citation for the Popov et al. paper?2012-06-23
  • 0
    When you write, "in *almost* all the examples I can think of...," can you give an example where $2k$ doesn't work?2012-06-23
  • 0
    @GerryMyerson Sorry, I mean all the example I can think of. I tried some finite dimensional matrices they all obey the $\le 2\kappa$ rule. I added a link to the paper.2012-06-23
  • 0
    I feel that [this paper](http://people.maths.ox.ac.uk/scott/Papers/acyclic.pdf) of Alon et al must have considerable bearing on the problem, but I can't seem to reconcile the first sentence of the abstract with the $3 \kappa$ result. Unless I'm missing something, they seem to be in contradiction.2012-06-23
  • 0
    @ErickWong Sorry I do not know much about graph theory and combinatorics. Could you explain a little bit what is the main idea and results of Alon's paper and why you think there is a contradiction?2012-06-23
  • 0
    @HuiYu: Let's make sure I understand the question correctly: doesn't $a(1,2)=a(2,3)=a(3,1)=1$ achieve $\sum a(i,j) = 3\kappa$ for $\kappa=1$?2012-06-23
  • 2
    Cross post on MO http://mathoverflow.net/questions/100417/how-many-1s-could-be-there-in-this-sequence2012-06-23

1 Answers 1

1

I believe there is a small counterexample with $\kappa=3$: $$\left( \begin{array}{ccccc} 0&1&1&0&0\\ 0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1\\ 1&1&0&0&0 \end{array} \right).$$ More generally, it is easy to prove an upper bound of $4 \kappa$, and I am inclined to believe it is asymptotically best possible (I guess the Alon paper cites a bound of the form $4 \kappa - O(\sqrt{\kappa}))$.

For the modified problem, where each row can have at most one 1, the stated upper bound $3\kappa$, assuming it is now accurate, is achieved by taking multiple disjoint copies of $\left( \begin{array}{ccc} 0&1&0\\ 0&0&1\\ 1&0&0\\ \end{array} \right)$. This satisfies the constraint using $\kappa$ copies for a total of $3\kappa$.

  • 1
    Yes. You are right. I was thinking about the original problem in the paper and forgot some other cases. I now realize that my problem here is not equivalent to the one I was thinking. Anyway, thanks!2012-06-23
  • 0
    Hi, I changed the problem a little bit. I made "for each $i$, there is at most one $j$ such that $a(i,j)=1$" a restriction on the matrix. I think know the problem is equivalent to the problem in the paper. So we have $3\kappa$ as an upper bound. I wonder whether this can be improved. Thanks!2012-06-23
  • 0
    @HuiYu I still don't see how this additional condition changes the $3 \times 3$ example I posted in the comments above.2012-06-23
  • 0
    That still works. But in that case we have $\sum a(i,j)\le 2\kappa+1$, so maybe the bound is $2\kappa+1$. Asymptotically it might be $2\kappa+const$.2012-06-23
  • 0
    @HuiYu In the $6\times 6$ version formed from two copies of the $3\times 3$ example, I get $\kappa = 2$ with the matrix adding up to $6$. How do you arrive at $2\kappa+1$?2012-06-23