3
$\begingroup$

Define $$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$ and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as $$f_l(\alpha)=\lim_{n\to \infty}\frac{ex_l(n,\alpha n)}{{n\choose 2}}.$$

By Turán Theorem we have that $f_l(\alpha)=1-\frac{1}{l-1}$ for every $\alpha \geq \frac{1}{l-1}$.

How to prove that this limit exists for every $\alpha \in (0,1]$?

I was trying to prove that the sequence $(ex_l(n,\alpha n)/{n\choose 2})_n$ is monotone, but I could only prove that $$ex_l(n,s)\leq\frac{n \ ex_l(n-1,s)}{n-2},$$ which is not enough since $ex_l(n-1,\alpha n) \geq ex_l(n-1,\alpha(n-1)).$

I also thought of using that $\alpha(G) \leq \alpha n$ and $\alpha(G)\leq \alpha(n-1)$ only give different restrictions once every $\approx 1/\alpha$ values of $n$ in a row. But it would also be necessary to show that every jump is in the same direction, which I couldn't do.

Edit 1: In Simonovits and Sós survey on Ramsey-Turán theory, when defining $RT(n,L^{(r)},s)$ for $r$-uniform hypergraphs, they say that the limit $$\lim_{n \to \infty}\frac{RT(n,L^{(r)},\varepsilon n)}{n^r}$$ exists and follows relatively easily from vertex-multiplication. I don't quite know how vertex-multiplication works but maybe it helps.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I answered the question in detail for $RT(n, K_l, \alpha n)$ here on Math StackExchange.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Just for the record, this is the same as my answer from two weeks earlier, except that it provides all the straightforward details of the Fekete lemma type argument. $\endgroup$
    – domotorp
    Commented Oct 23, 2021 at 6:01
  • 1
    $\begingroup$ This is probably the difference between MO and MSE. (When writing my answer, I figured that to the MSE audience, those details would not be particularly straightforward.) $\endgroup$
    – Misha Lavrov
    Commented Oct 23, 2021 at 6:03
  • $\begingroup$ @domotorp As you said in a comment before, this Fekete lemma type argument didn't seem to be trivial. I agree the main idea of the proof was provided by you first, but it seems better for future reference to put the most complete answer as right. $\endgroup$
    – JPMarciano
    Commented Oct 23, 2021 at 23:26
5
$\begingroup$

New Answer: It indeed follows from vertex-multiplication. If you replace each vertex with a stable set of size $k$, then $\alpha(G)/n$ will not change, while $n^r$ and the number of edges both grow by a $k^r$ factor. This shows that $\lim_{n \to \infty}\frac{RT(n,L^{(r)},\varepsilon n)}{n^r}$ has a limit by a Fekete lemma type argument.

Old Answer: Many of these functions are not known to have a limit. In this case when someone proves a bound on them, in fact they show a bound for the liminf or limsup. Unfortunately, in many papers they refer to it as lim, which also bothers me a lot. Incidentally, I've just asked the same thing two weeks ago (about the uniform Turan density function) from Danial Kral'.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I believe that in this case it would be quite surprising if it is just a definition problem. Lüders, Reiher (2017) say it is well known and easy to confirm that this limit exists. Łuczak, Polcyn, Reiher (2020) also say that this limit exists, referring to Erdos, Hajnal, Sós, Szemerédi (1983), but I couldn't find it there. $\endgroup$
    – JPMarciano
    Commented Oct 7, 2021 at 16:37
  • $\begingroup$ @JPM You are right, this follows from vertex-multiplication. $\endgroup$
    – domotorp
    Commented Oct 7, 2021 at 19:06
  • $\begingroup$ Can you explain this idea a little bit better? Are you deleting the edge and adding vertices? $\endgroup$
    – JPMarciano
    Commented Oct 7, 2021 at 20:16
  • 1
    $\begingroup$ @JPM No, just blowing up vertices. For example, if your graph is just a $K_2$, the edge $uv$, then if $k=2$, the new graph becomes a $C_4$, $v_1u_1v_2u_2$. $\endgroup$
    – domotorp
    Commented Oct 7, 2021 at 20:53
  • 1
    $\begingroup$ @JPM No, that's not true for any sequence. Here we should use that the sequence $a_n$ is almost continuous, so something like $a_k$ and $a_{k+1}$ are not far, though even this does not seem to be trivial to prove, I'm positive this approach works. Regarding $L^{(r)}$, I don't see what to do. $\endgroup$
    – domotorp
    Commented Oct 8, 2021 at 5:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .