*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 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*<sup>th</sup> roots of unity, where *d* is the length of the cycle.
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). I had originally suspected that this might be unique: but this fails for some small instances, as the condition of being connected is less restrictive in the case *k*>1 than in the case *k*=1.<sup>†</sup>
**Question.** Is there any unique structure of any sort which arises in *H* for a connected *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 anywhere from 1 to *k* strongly connected components of this sort.