On the sizes of vertex-$k$-maximal $r$-uniform hypergraphs

Abstract

Let $H=(V,E)$ be a hypergraph, where $V$ is a set of vertices and $E$ is a set of non-empty subsets of $V$ called edges. If all edges of $H$ have the same cardinality $r$, then $H$ is a $r$-uniform hypergraph; if $E$ consists of all $r$-subsets of $V$, then $H$ is a complete $r$-uniform hypergraph, denoted by $K_n^r$, where $n=|V|$. A hypergraph $H^{\prime }=(V^{\prime },E^{\prime })$ is called a subhypergraph of $H=(V,E)$ if $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. A $r$-uniform hypergraph $H=(V,E)$ is vertex-$k$-maximal if every subhypergraph of $H$ has vertex-connectivity at most $k$, but for any edge $e\in E(K_n^r)\setminus E(H)$, $H+e$ contains at least one subhypergraph with vertex-connectivity at least $k+1$. In this paper, we first prove that for given integers $n,k,r$ with $k,r\ge 2$ and $n\ge k+1$, every vertex-$k$-maximal $r$-uniform hypergraph $H$ of order $n$ satisfies $|E(H)|\ge {(}_r^n)-{(}_r^{n-k})$, and this lower bound is best possible. Next, we conjecture that for sufficiently large $n$, every vertex-$k$-maximal $r$-uniform hypergraph $H$ on $n$ vertices satisfies $|E(H)|\le {(}_r^n)-{(}_r^{n-k})+(\frac{n}{k}-2){(}_r^k)$, where $k,r\ge 2$ are integers. And the conjecture is verified for the case $r>k$.

arXiv admin note: text overlap with arXiv:1802.08843, arXiv:1805.11425

References in corpus (1)

• On the number of edges in a graph with no $(k+1)$-connected subgraphs