Almost all triple systems with independent neighborhoods are semi-bipartite

DOI10.1016/J.JCTA.2011.01.006zbMATH Open1231.05188arXiv1002.1925OpenAlexW2153349536MaRDI QIDQ2431618FDOQ2431618

Authors: József Balogh, Dhruv Mubayi 

Publication date: 15 April 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: The neighborhood of a pair of vertices $u,v$ in a triple system is the set of vertices $w$ such that $uvw$ is an edge. A triple system $HH$ is semi-bipartite if its vertex set contains a vertex subset $X$ such that every edge of $HH$ intersects $X$ in exactly two points. It is easy to see that if $HH$ is semi-bipartite, then the neighborhood of every pair of vertices in $HH$ is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets $[n]$ and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the ErdH os-Kleitman-Rothschild theorem to triple systems. The proof uses the Frankl-R"odl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.

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

Recommendations

• On Triple Systems with Independent Neighbourhoods
• Simple neighbourhoods in triple systems
• Almost all triangle-free triple systems are tripartite
• Quadruple systems with independent neighborhoods
• scientific article; zbMATH DE number 4049658

zbMATH Keywords

semi-bipartiteindependent neighborhoodsspeed of hypergraph property

Mathematics Subject Classification ID

Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Triple systems (05B07)

Cites Work

• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Weak hypergraph regularity and linear hypergraphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The number of graphs without forbidden subgraphs
• The typical structure of graphs without given excluded subgraphs
• Title not available (Why is that?)
• The fine structure of octahedron-free graphs
• Extremal problems on set systems
• Three-graphs without two triples whose symmetric difference is contained in a third
• On Triple Systems with Independent Neighbourhoods
• The asymptotic number of triple systems not containing a fixed one
• The structure of almost all graphs in a hereditary property
• Excluding induced subgraphs: critical graphs
• Almost all triangle-free triple systems are tripartite
• Quadruple systems with independent neighborhoods
• On the Turán number of triple systems
• Almost all hypergraphs without Fano planes are bipartite
• Hypergraphs with independent neighborhoods

Cited In (13)

• Discrete metric spaces: structure, enumeration, and 0-1 laws
• Structure and enumeration theorems for hereditary properties in finite relational languages
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Independent sets in hypergraphs
• The structure of almost all graphs in a hereditary property
• Exact results on the number of restricted edge colorings for some families of linear hypergraphs
• Almost all triangle-free triple systems are tripartite
• Rainbow Erdös-Rothschild problem for the Fano plane
• Some Cubic Time Regularity Algorithms for Triple Systems
• The typical structure of sparse \(K_{r+1}\)-free graphs
• Simple neighbourhoods in triple systems
• Counting \(r\)-graphs without forbidden configurations
• The typical structure of maximal triangle-free graphs

This page was built for publication: Almost all triple systems with independent neighborhoods are semi-bipartite

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