REVIEW 4 cited by
Crowns in linear $3$-graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
A \textit{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, ${\rm ex}(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 \textit{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 \left\lfloor{\frac{n - 3}{4}}\right\rfloor \leq {\rm ex}(n, C) \leq 2n, \] and in the construction providing the lower bound all but three vertices have degree $3$. We conjecture that ${\rm ex}(n, C) \sim \frac{3n}{2}$ but even if this were known it would not imply our main result. Our second result is a step towards a possible proof of ${\rm ex}(n,C) \leq \frac{3n}{2}$ (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.
Forward citations
Cited by 4 Pith papers
-
Linear Tur\'an Numbers of Uniform Hypertrees
For several r-uniform linear hypertrees with four edges, the maximum number of edges in a linear r-uniform hypergraph avoiding them is determined; the 4-uniform 4-edge path case is settled exactly.
-
An Upper Bound on the Linear Tur\'{a}n Number of $k$-Crowns
An upper bound is established for the linear Turán number ex_r^lin(n, C_{1,k}^r) of k-crowns in linear r-graphs.
-
Bounds on Linear Tur\'{a}n Number for Trees
Linear Turán number ex_r^lin(n,T_k^r) is at least n(k-1)/r for any r-uniform tree with k edges; exact upper bound (r+1)n/r for B_4^r with characterization, (2r-1)n/r for E_4^r, and matching lower construction for P_4^r.
-
Bounds on Linear Tur\'{a}n Number for Trees
The paper proves exact and near-exact linear Turán bounds for several small r-uniform trees, including a lower bound for the 4-edge path, but one upper-bound proof contains an unjustified assumption.
Discussion (0). Sign in to comment.