*Edit: The problem has been slightly revised, as I discovered that one of the questions I asked has an answer in the negative.*
I'm working in a setting involving constraints on a system described by a *k*-uniform hypergraph, where the constraints are satisfiable if there is an injective function mapping each edge to one of the vertices it touches. The ways that these constraints can be satisfied is limited when that mapping is bijective, which may be due to something like feedback-loops of dependencies 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*.
* We're interested not just in the hypergraph defined by F, but a sort of *directed* hypergraph: 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.**
A 1-map on a set *V* is essentially just a function on *V* which has no fixed points. This corresponds to a garden-variety digraph without loops which **(a)** consists of multiple components, where **(b)** each component consists of a collection of at least two 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 just the one directed cycle (which happens also to be the only *undirected* cycle in the digraph; provided of course the directed cycle has length at least 3). 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 spanning another eigenspace of dimension 1), one for each of the *d*<sup>th</sup> roots of unity, where *d* is the length of the cycle.
I'm interested in such unique structures — such as the unique cycle, or the nondegenerate eigenspace — but in the hypergraphs which correspond to *k*-maps for all *k* ≥ 1. For *k* arbitrary, 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); however, the condition of being connected is less restrictive in the case *k*>1 than in the case *k*=1,<sup>†</sup> so that space may have dimension larger than 1. Of course, it could be that I should be looking at an algebraic object other than $A$ as defined above, or a "purely" combinatorial structure.
**Question.** Is there any unique structure of any sort which arises in every connected hypergraph *H* which corresponds to a *k*-map?
---
† It is not difficult to show that every {0,1}-matrix, with a null diagonal and columns each summing to the same constant, are valid adjacency matrices $A$ for some *k*-map. A simple 2-map whose 2-eigenspace has dimension 2 can be given by
$$ A =
\left[\begin{array}{c|ccc|ccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\
\hline
1 & 0 & 1 & 1 & 0 & 0 & 0 \\\\
0 & 1 & 0 & 1 & 0 & 0 & 0 \\\\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\\\
\hline
1 & 0 & 0 & 0 & 0 & 1 & 1 \\\\
0 & 0 & 0 & 0 & 1 & 0 & 1 \\\\
0 & 0 & 0 & 0 & 1 & 1 & 0
\end{array}\right]\\,: $$
the blocks correspond to "strongly connected" components in the directed hypergraph.
The fact that the 2-eigenspace has dimension 2 can be attributed to the fact that there are two such strongly connected components, which are closed under the action of the map F described by this matrix. (The cycle in a connected 1-map is also the unique strongly connected component closed under F.) Generalizing this example, a connected *k*-map may have an arbitrary number of strongly connected components of this sort, for *k* > 1.