Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-12T08:47:12.368Z Has data issue: false hasContentIssue false

On Triple Systems with Independent Neighbourhoods

Published online by Cambridge University Press:  11 October 2005

ZOLTÁN FÜREDI
Affiliation:
Rényi Institute of Mathematics of the Hungarian Academy of Sciences Budapest, PO Box 127, Hungary-1364 and Department of Mathematics, University of Illinois at Urbana-Champaign Urbana, IL61801, USA (e-mail: furedi@renyi.hu, z-furedi@math.uiuc.edu
OLEG PIKHURKO
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University Pittsburgh, PA 15213-3890, USA (URL address: http://www.math.cmu.edu/~pikhurko)
MIKLÓS SIMONOVITS
Affiliation:
Rényi Institute of Mathematics of the Hungarian Academy of Sciences Budapest, PO Box 127, Hungary-1364 (e-mail: miki@renyi.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let ${\cal H}$ be a 3-uniform hypergraph on an $n$-element vertex set $V$. The neighbourhood of $a,b\in V$ is $N(ab):= \{x: abx\in E({\cal H})\} $. Such a 3-graph has independent neighbourhoods if no $N(ab)$ contains an edge of ${\cal H}$. This is equivalent to ${\cal H}$ not containing a copy of $\mathbb{F} :=\{ abx$, $aby$, $abz$, $xyz\}$.

In this paper we prove an analogue of the Andrásfai–Erdös–Sós theorem for triangle-free graphs with minimum degree exceeding $2n/5$. It is shown that any $\mathbb{F}$-free 3-graph with minimum degree exceeding $(\frac{4}{9}-\frac{1}{125})\binom{n}{2}$ is bipartite, (for $n> n_0$), i.e., the vertices of ${\cal H}$ can be split into two parts so that every triple meets both parts.

This is, in fact, a Turán-type result. It solves a problem of Erdös and T.Sós, and answers a question of Mubayi and Rödl that

\[\ex(n,\mathbb{F}_{3,2})=\max\limits_{\alpha}(n-\alpha)\left({\alpha\atop2}\right)\].

Here the right-hand side is $\frac{4}{9}\binom{n}{3}+O(n^2)$. Moreover $e({\cal H})={\rm ex}(n,\mathbb{F})$ is possible only if $V({\cal H})$ can be partitioned into two sets $A$ and $B$ so that each triple of ${\cal H}$ intersects $A$ in exactly two vertices and $B$ in one.

Information

Type
Paper
Copyright
2005 Cambridge University Press