UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On existentially complete triangle-free graphs

Letzter, S; Sahasrabudhe, J; (2020) On existentially complete triangle-free graphs. Israel Journal of Mathematics , 236 (2) pp. 591-601. 10.1007/s11856-020-1982-3. Green open access

[img]
Preview
Text
ECTF_Final_april.pdf - Accepted version

Download (271kB) | Preview

Abstract

For a positive integer k, we say that a graph is k-existentially complete if for every 0 ⩽ a ⩽ k, and every tuple of distinct vertices x1, …, xa, y1, …, yk−a, there exists a vertex z that is joined to all of the vertices x1, …, xa and to none of the vertices y1, …, yk−a. While it is easy to show that the binomial random graph Gn,1/2 satisfies this property (with high probability) for k = (1 − o(1)) log2n, little is known about the “triangle-free” version of this problem: does there exist a finite triangle-free graph G with a similar “extension property”? This question was first raised by Cherlin in 1993 and remains open even in the case k = 4. We show that there are no k-existentially complete triangle-free graphs on n vertices with k>8lognloglogn, for n sufficiently large.

Type: Article
Title: On existentially complete triangle-free graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s11856-020-1982-3
Publisher version: https://doi.org/10.1007/s11856-020-1982-3
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107227
Downloads since deposit
4Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item