Crowns in linear 3-graphs

MaRDI QIDQ6374159zbMATH OpenFDO

Authors Alvaro Carbonero, Willem Fletcher, Jing Guo, András Gyárfás, Rona Wang, Shiyu Yan

Publication date 30 July 2021

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Triple systems (05B07)

Abstract: A extit{linear $3$-graph}, $H=(V,E)$, is a set, $V$, of vertices together with a set, $E$, of $3$-element subsets of $V$, called edges, so that any two distinct edges intersect in at most one vertex. The linear Tur'an number, $mex(n,F)$, is the maximum number of edges in a linear $3$-graph $H$ with $n$ vertices containing no copy of $F$. We focus here on the extit{crown}, $C$, which consists of three pairwise disjoint edges (jewels) and a fourth edge (base) which intersects all of the jewels. Our main result is that every linear $3$-graph with minimum degree at least $4$ contains a crown. This is not true if $4$ is replaced by $3$. In fact the known bounds of the Tur'an number are [ 6 leftlfloor{frac{n - 3}{4}} ight floor leq { m ex}(n, C) leq 2n, ] and in the construction providing the lower bound all but three vertices have degree $3$. We conjecture that $mex(n,C)simfrac3n2$ but even if this were known it would not imply our main result. Our second result is a step towards a possible proof of $mex(n,C)leqfrac3n2$ (i.e., determining it within a constant error). We show that a minimal counterexample to this statement must contain certain configurations with $9$ edges and we conjecture that all of them lead to contradiction.

This page was built for publication: Crowns in linear $3$-graphs

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