4
$\begingroup$

I asked a related question on math.stackexchange here but would now like to obtain a better bound. This question comes from a graph theory problem. I'll restate the new question here:

For $i=1,2,\ldots,n$, let $d_i$ be a sequence of positive integers satisfying $d_1\geq\cdots\geq d_n$ with $2\leq d_i\leq n-1$, and $r_i$ a sequence of positive real numbers that satisfy the following system of equations:

$$d_i=\sum_{j=1}^n \frac{r_ir_j}{1+r_ir_j}$$

for each $i=1,2\ldots,n$.

I have additional constraints that $d_1+\cdots+d_n$ is even and for every $1\leq k\leq n$,

$$\sum_{i=1}^k d_i < k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$$

(this is the strict Erdos Gallai theorem for the degrees of a graph).

Question: Can we find a qualitative bound on $r_i$ in terms of $n$? I would ideally like a bound of the form $n^c$ for some constant $c$ (that doesn't depend on $n$, $r_i$ or $d_i$). If such a bound doesn't exist, is there a counterexample or are there additional "mild" conditions on the $d_i$'s that can yield such a bound (for example, $d^2_{\mbox{max}}:=d^2_n\leq \frac{1}{2}\sum_{i=1}^nd_i$ gives a bound of $n^7$). ?

Notice that in the previous question, a bound of $n^{2n}$ was obtained but, sadly the posted argument doesn't seem to yield a better bound, unless I'm missing something obvious.

Improve this question
$\endgroup$
8
  • $\begingroup$ Why is d_i > 1? Is it not possible to have 1 or 0 as part of the degree sequence? Gerhard "Ask Me About System Design" Pasman, 2012.10.04 $\endgroup$
    – Gerhard Paseman
    Oct 4, 2012 at 21:42
  • $\begingroup$ @Gerhard Paseman: It's true that you can have 1 or 0 in the degree sequence. However, if $d_i=0$, then unless $r_k$ are all zero, it would mean $r_i$ is zero. Effectively I'm trying to look at the worst case scenario when $d_i\neq 0$. I'm discounting $d_i=1$ for more specific reasons related to what I'm trying to apply this too. $\endgroup$
    – Alex R.
    Oct 5, 2012 at 2:22
  • $\begingroup$ Did you rather mean to write $2\leq r_i\leq n-1$? $\endgroup$
    – Dima Pasechnik
    Oct 8, 2012 at 7:55
  • $\begingroup$ @Dima Pasechnik: No, but I see my word ordering might make it seem like that. I'll change it, thanks. $\endgroup$
    – Alex R.
    Oct 8, 2012 at 17:54
  • $\begingroup$ Perhaps you gain something by looking at the alternate formulation using c_i = n - d_i. Have you tried working with c_i? Gerhard "Ask Me About Alernative Arithmetic" Paseman, 2012.10.08 $\endgroup$
    – Gerhard Paseman
    Oct 8, 2012 at 22:43

0

Reset to default

Your Answer

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