Spreading linear triple systems and expander triple systems

DOI10.1016/J.EJC.2020.103155zbMATH Open1447.05039arXiv1906.03149OpenAlexW3027109856MaRDI QIDQ2198982FDOQ2198982

Zoltán Blázsik, Zoltán Lóránt Nagy

Publication date: 15 September 2020

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The existence of Steiner triple systems STS(n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading property of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. This property is strongly connected to the connectivity of the structure and of the so-called influence maximization. We also discuss how the results are related to ErdH{o}s' conjecture on locally sparse STSs, influence maximization, subsquare-free Latin squares and possible applications in finite geometry.

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

Recommendations

• On a conjecture of Erdős on locally sparse Steiner triple systems
• Further 6-sparse Steiner triple systems
• Threshold for Steiner triple systems
• On 6-sparse Steiner triple systems
• scientific article; zbMATH DE number 3874089

zbMATH Keywords

Steiner triple systems

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of finite geometries (05B25) Triple systems (05B07)

Cites Work

• Directed hypergraphs and applications
• Additive combinatorics
• The difference between consecutive primes. II
• On the Approximability of Influence in Social Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• An asymptotic isoperimetric inequality
• Recognising \(k\)-connected hypergraphs in cubic time
• Systèmes triples de Steiner non engendrés par tous leurs triangles. (Steiner triple systems not surrounded by their triangles)
• Sur la structure de certains systèmes triples de Steiner
• A Direct Construction for Latin Squares Without Proper Subsquares
• Subsquare-free Latin squares of odd order
• Hypergraph expanders from Cayley graphs
• Large girth approximate Steiner triple systems
• Title not available (Why is that?)

Cited In (1)

• On a conjecture of Erdős on locally sparse Steiner triple systems

This page was built for publication: Spreading linear triple systems and expander triple systems

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