Sierpinski products of r-uniform hypergraphs

Keywords: Hypergraph products, cliques, chromatic numbers.

Abstract

If H1 and H2 are r-uniform hypergraphs and f is a function from the set of all (r − 1)-element subsets of V(H1) into V(H2), then the Sierpiński product H1fH2 is defined to have vertex set V(H1) × V(H2) and hyperedges falling into two classes:
(g, h1)(g, h2)⋯(g, hr), such that g ∈ V(H1) and h1h2hr ∈ E(H2),
and
(g1, f({g2, g3, …, gr}))(g2, f({g1, g3, …, gr}))⋯(gr, f({g1, g2, …, gr − 1})),
such that g1g2gr ∈ E(H1). We develop the basic structure possessed by this product and offer proofs of numerous extremal properties involving connectivity, clique numbers, and strong chromatic numbers.

Published
2021-03-17
Section
Articles