I'm working in a setting involving constraints on a system which involves k-uniform hypergraphs, where the constraints are satisfiable if there is an injective function mapping each edge to one of the vertices it touche. The ways that these constraints can be solved is small when that mapping is bijective, due to something like feedback-loops which have fixed points.

This motivates the following problem, which I expect may have been considered before in different terms:

Definitions.

• A k-map on a set V is just a function $F: V \to \mathscr P(V)$, mapping each v ∈ V to some set $F(v) \subseteq V$ with cardinality k, such that $v \notin F(v)$.

• The hypergraph of F is simply the hypergraph H with vertex-set V, and whose edges are all sets of the form $e_v = \{v\} \cup F(v)$ for each v ∈ V. Really, we're interested in a sort of directed hypergraph defined by F: this is perhaps most easily defined using an incidence-matrix-cum-adjacency-matrix defined on $\mathbb C^V$, $$ A_{u,v} = \begin{cases} 1 & \text{if $u \in F(v)$;} \\\\ 0 & \text{otherwise.} \end{cases} $$

• We say that F is connected if the hypergraph of F is connected.

Observation.

Note that a 1-map on a set V is essentially just a function on V, and corresponds to a garden-variety digraph without loops which (a) consists of multiple components, where (b) each component consists of a collection of disjoint trees directed to their roots, with a directed cycle defined between the roots of the trees.

The digraph for a connected 1-map contains exactly one directed cycle (which happens also to be the only undirected cycle in the digraph). This state of affairs is witnessed by the fact that $A$ has a +1-eigenspace of dimension 1, which is spanned by the indicator function for the cycle. The cycle is also the support for several other eigenvectors (each of which also have multiplicity 1), one for each of the d^th roots of unity, where d is the length of the cycle.

Question.

I'm interested in such unique structures, but in the hypergraphs which correspond to k-maps for all k ≥ 1.

For k artbitrary, it is clear that $A$ has a non-trivial k-eigenspace (as the matrix $A - kI$ is singular, which may be verified by considering the sums of its columns). Is it clear that k will always have multiplicity 1, provided that F is connected?

• If yes, are there any natural structures in H which relates in some way to the k-eigenspace of $A$?

• If no, is there any unique structure of any sort which arises in H for a connected k-map?

The cycles in the 1-maps are exactly the relevant structure for the problem I'm looking at; I'm singling out the eigenvectors of $A$ as the thing which looks most like a feedback loop in equilibrium. However, any unique structure arising in situations like this may be pertinent.