Forbidding K₂,t traces in triple systems

DOI10.37236/9760MaRDI QIDQ2662345zbMATH OpenOpenAlexFDO

Authors Ruth Luo, Sam Spiro

Publication date 12 April 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

degenerate graphsTurán number

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Extremal combinatorics (05D99)

Abstract: Let $H$ and $F$ be hypergraphs. We say $H$ contains $F$ as a trace if there exists some set $SsubseteqV(H)$ such that $H{|}_S:=EcapS:EinE(H)$ contains a subhypergraph isomorphic to $F$. In this paper we give an upper bound on the number of edges in a $3$-uniform hypergraph that does not contain $K_{2,t}$ as a trace when $t$ is large. In particular, we show that $li{m}_{toinfty}li{m}_{noinfty}fracmathrmex(n,mathrm{Tr}_3(K_{2,t}))t^{3/2}{n}^{3/2}=frac16.$ Moreover, we show $frac12n^{3/2}+o(n^{3/2})leqmathrmex(n,mathrm{Tr}_3(C_4))leqfrac56n^{3/2}+o(n^{3/2})$.

Review text

Summary: Let \(H\) and \(F\) be hypergraphs. We say \(H\) contains \(F\) as a trace if there exists some set \(S \subseteq V(H)\) such that \(H|_S:=\{E\cap S: E \in E(H)\}\) contains a subhypergraph isomorphic to \(F\). In this paper we give an upper bound on the number of edges in a \(3\)-uniform hypergraph that does not contain \(K_{2,t}\) as a trace when \(t\) is large. In particular, we show that \[\lim_{t\to \infty}\lim_{n\to \infty} \frac{\text{ex}(n, \text{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.\] Moreover, we show \(\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \text{ex}(n, \text{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})\).

Recommendations

• Forbidding complete hypergraphs as traces
• New bounds for a hypergraph bipartite Turán problem
• Traces of hypergraphs
• scientific article; zbMATH DE number 3887691
• The asymptotic number of triple systems not containing a fixed one

Cites work

• 3-uniform hypergraphs and linear cycles
• 3-uniform hypergraphs avoiding a given odd cycle
• A note on the maximum size of Berge-\( C_4\)-free hypergraphs
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Cycles of even length in graphs
• Extremal results for Berge hypergraphs
• Forbidden families of minimal quadratic and cubic configurations
• Forbidding complete hypergraphs as traces
• General lemmas for Berge-Turán hypergraph problems
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Hypergraphs with no cycle of a given length
• Many \(T\) copies in \(H\)-free graphs
• New asymptotics for bipartite Turán numbers
• On 3-uniform hypergraphs without a cycle of a given length
• On a problem of K. Zarankiewicz
• On Graphs that do not Contain a Thomsen Graph
• On the structure of linear graphs
• Pentagons vs. triangles
• The probabilistic method
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Cited in

(4)

• Forbidding complete hypergraphs as traces
• Disjoint representability of sets and their complements
• Edge Multiplicity and Other Trace Functions
• On forbidding graphs as traces of hypergraphs

This page was built for publication: Forbidding \(K_{2,t}\) traces in triple systems

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