On existentially complete triangle-free graphs

DOI10.1007/S11856-020-1982-3MaRDI QIDQ2182038zbMATH OpenOpenAlexFDO

Authors Shoham Letzter, Julian Sahasrabudhe

Publication date 20 May 2020

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08817

zbMATH Keywords

partial embeddingRado graph

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For a positive integer $k$, we say that a graph is $k$-existentially complete if for every $0leqaleqk$, and every tuple of distinct vertices $x_1,ldots,x_a$, $y_1,ldots,y_{k-a}$, there exists a vertex $z$ that is joined to all of the vertices $x_1,ldots,x_a$ and none of the vertices $y_1,ldots,y_{k-a}$. While it is easy to show that the binomial random graph $G_{n,1/2}$ satisfies this property with high probability for $ksimclogn$, 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 with $k>frac8lognloglogn$, thus giving the first non-trivial, non-existence result on this "old chestnut" of Cherlin. We believe that this result breaks through a natural barrier in our understanding of the problem.

Recommendations

• Triply existentially complete triangle-free graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Triangle-free regular graphs
• Triangle-free graphs with large chromatic numbers
• Triangle-free subgraphs of random graphs

Cites work

• A family of countable homogeneous graphs
• Graphs whose every independent set has a common neighbour
• scientific article; zbMATH DE number 3941572 (Why is no real title available?)
• scientific article; zbMATH DE number 125198 (Why is no real title available?)
• Maximum degree in graphs of diameter 2
• Partitions and orientations of the Rado graph
• The random graph
• The strange logic of random graphs
• Triply existentially complete triangle-free graphs
• Two problems on homogeneous structures, revisited
• Universal graphs and universal functions

Cited in

(7)

• Triangulating remnants of complete graphs
• Exponential families of non-isomorphic triangulations of complete graphs
• Empty triangles in complete topological graphs
• Testing Triangle-Freeness in General Graphs
• On maximal triangle‐free graphs
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• Triply existentially complete triangle-free graphs

This page was built for publication: On existentially complete triangle-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182038)