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
    Oct 15 at 19:18
  • 1
    $\begingroup$ @LSpice Thank you, I forgot about the gated link :) $\endgroup$
    – Samyak Jha
    Oct 16 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
    Oct 16 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
    Oct 18 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
    Oct 18 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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.