1
$\begingroup$

I am currently trying to understand the construction of maximal graph which contains no $K_4$ and sub-linear number of independent points in the graph. The original paper On a Ramsey–Turán type problem, although ground-breaking, is very hard to parse. It also glosses over some crucial details and claims some really non-trivial identities. I am listing some of them below (but there are probably more questions one can ask).

  • Is there a way to partition a hyper-sphere of dimension $n$ into $N$ equal parts and bounded diameters?
  • Aren't $C$ and $A$, as defined in the paper, very close to each other? Importantly, doesn't that imply that $\delta > 1$ (and that's it)?
  • Can anyone explain the argument made to find the diameter of the spherical cap that, as claimed on top of page 3?
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note: Erdős's name is spelled with ő ("o with double acute"), not ö ("o with diaeresis"). I have edited accordingly. I also edited out an institutionally gated link to the article, and replaced it with a DOI link. $\endgroup$
    – LSpice
    Commented Oct 15, 2023 at 19:18
  • 1
    $\begingroup$ @LSpice Thank you, I forgot about the gated link :) $\endgroup$
    – total dependent random choice
    Commented Oct 16, 2023 at 4:08
  • $\begingroup$ Re, no worries. Is there a missing word or words in your third bullet point ("… the diameter of the spherical cap that, as claimed …")? $\endgroup$
    – LSpice
    Commented Oct 16, 2023 at 11:31
  • 1
    $\begingroup$ An alternative presentation of the Bollobás-Erdős construction appears in this paper by Balogh and Lenz (sections 3, 4) arxiv.org/pdf/1109.4428.pdf $\endgroup$
    – hdur
    Commented Oct 18, 2023 at 13:32
  • 1
    $\begingroup$ Name of the paper referenced by @hdur: Balogh and Lenz - On the Ramsey–Turán numbers of graphs and hypergraphs. $\endgroup$
    – LSpice
    Commented Oct 18, 2023 at 19:22

1 Answer 1

Reset to default
2
$\begingroup$

I found an excellent account of this problem in the thesis of John Lenz: xtremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors Lenz, John E.

Improve this answer
$\endgroup$

You must log in to answer this question.

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