Spreading linear triple systems and expander triple systems

DOI10.1016/J.EJC.2020.103155MaRDI QIDQ2198982zbMATH OpenOpenAlexFDO

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

Publication date 15 September 2020

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• A Direct Construction for Latin Squares Without Proper Subsquares
• Additive combinatorics
• An asymptotic isoperimetric inequality
• Directed hypergraphs and applications
• Hypergraph expanders from Cayley graphs
• Large girth approximate Steiner triple systems
• On the approximability of influence in social networks
• Overlap properties of geometric expanders (extended abstract)
• Recognising \(k\)-connected hypergraphs in cubic time
• Subsquare-free Latin squares of odd order
• Sur la structure de certains systèmes triples de Steiner
• Systèmes triples de Steiner non engendrés par tous leurs triangles. (Steiner triple systems not surrounded by their triangles)
• The difference between consecutive primes. II

Cited in

(3)

• Spreading linear triple systems and expander triple systems
• Steiner triple systems and spreading sets in projective spaces
• 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)