3
$\begingroup$

Let $f : \Bbb N \to \Bbb N$ be a nondecreasing function that satisfies $f(8) \geq 1$ and $f(n)\geq 2f(\lceil \frac n2-n^{2/3} \rceil)$. Can we deduce that there exists some positive constant $c$ such that $f(cn) \geq n$?

This is the crux of the question; now here is the context.

Let us call a directed graph $t$-big if all its indegrees and outdegrees are at least $t$.

I was suggested at proving the following claim using a particular method that I'm not certain about its validity.

Claim. There exists some constant $C>0$ such that every $Ck$-big graph contains at least $k$ vertex-disjoint even cycles.

The suggestion was to repeatedly partition the graph into two graphs and argue on each of them, showing that the aggregated error is "small enough".

The following two lemmas are used, and known to be true:

Lemma 1. For every $t$-big graph there is a coloring of its vertices in red and blue, such that the red graph is $\frac t2-t^{2/3}$-big and the blue graph is also $\frac t2-t^{2/3}$-big.

Lemma 2. Every $8$-big graph contains an even cycle.

Note that if we didn't have the "error term" $t^{2/3}$, then we could take $C=8$ and get the required claim. I would like to say that if we start with a graph that is $Ck$-big, for some suitably chosen $C>8$, then the error obtained by repeatedly using lemma 2 will be small enough, because we do approximately $\log k$ steps.

By letting $f(t)$ be the number of vertex-disjoint even cycles guaranteed by being $t-big$, we arrive at the question at the start of the post.

Can it be made to work?

$\endgroup$
3
  • 1
    $\begingroup$ I think that's possible. There should be two steps: the first is to prove $f(n)\ge A\,n-B\,n^{2/3}$ by some specialized induction (if it's valid for $2^{k-1}\le n<2^k$, it's also valid for $2^k\le n<2^{k+1}$), the second one is to prove $A\,n-B\,n^{2/3}\ge A'\,n$, but that's easy. I haven't worked out the details, yet. $\endgroup$
    – user436658
    Commented May 26, 2017 at 20:03
  • $\begingroup$ I agree with ProfessorVector. On the other hand, to investigate more tight lower bounds for the function $f$, I wrote a simple program. Remark that for each $n\ge 8$ we have $f(n)\ge 2^{g(n)}$, where $g(n)$ is the smallest non-decreasing function such that $g(8)=0$ and $g(n)\geq 1+g(\lceil \frac n2-n^{2/3} \rceil)$. $\endgroup$
    – Alex Ravsky
    Commented May 27, 2017 at 12:53
  • $\begingroup$ The program calculated values of $g(n)$ up to $n=50000$ and, provided there were no rounding errors, the sequence of values at which $g$ consecutively jumps by $1$ is $36, 119, 332, 841, 1998, 4543, 10014, 21577, 45709,\dots$, see also the graph of $\log_2$ of these jumps. $\endgroup$
    – Alex Ravsky
    Commented May 27, 2017 at 12:53

0

Reset to default

You must log in to answer this question.