Independence in hypergraphs

Yu. A. Sushkov

Zapiski Nauchnykh Seminarov POMI, Modules and algebraic groups, Tome 114 (1982), pp. 196-204

Résumé

Suppose an integral function $\gamma(|A|)\geqslant q_1$ defined on the subsets of edges of a hypergraph $(X,U,\Gamma)$ satisfies the following two conditions: 1) any set $W\subseteq U$ such that $|\Gamma A|\geqslant\gamma(|A|)$ for any $A\subseteq W$ is matroidally independent; 2) if $W$ is an independent set, then there exists a unique partition $W=T_1+T_2+\dots+T_v$ such that $|\Gamma T_i|=\gamma(|T_i|)$, $i\in1:v$, and for any $A\subseteq W$, $|\Gamma A|=\gamma(|A|)$ there exists a $T_i$ such that $A\subseteq T_i$. The form of such a function is found, in terms of parameters of generalized connected components, hypercycles, and hypertrees.