SPREADING LINEAR TRIPLE SYSTEMSAND EXPANDER TRIPLE SYSTEMS

Nagy, Zoltán Lóránt and Blázsik, Zoltán L. (2019) SPREADING LINEAR TRIPLE SYSTEMSAND EXPANDER TRIPLE SYSTEMS. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 88 (3). pp. 977-984. ISSN 0862-9544

Preview

Text document.pdf Download (500kB) | Preview

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. A linear triple system on a vertex set V has the spreading, or respectively weakly spreading property if any sufficiently large subset V_0\V contains a pair of vertices with which a vertex of V from V_0 forms a triple of the system. Here the condition on V_0 refers to |V_0| >=4 or V_0 is the support of more than onetriples, respectively. This property is strongly connected to the connectivity of the structure the so-called influence maximisation. We also discuss how the results are related to Erdős' conjecture on locally sparse STSs, subsquare-free Latin-squares and possible applications in finite geometry.

Actions (login required)

Edit Item