Return to Question

I'm working in a setting involving conmstraints 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.

• 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.

Note that a 1-map on a set V is essentially just a function on V which has no fixed points, which 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; 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^th 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.^† Of course, it could be that I should be looking at an algebraic object other than $A$ as defined above.

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.

• 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.

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^th 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,^† 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.

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.

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.^†

Question. Is there any unique structure of any sort which arises in H for a connected k-map?

Note that a 1-map on a set V is essentially just a function on V which has no fixed points, which 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; 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^th 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.^† Of course, it could be that I should be looking at an algebraic object other than $A$ as defined above.

Question. Is there any unique structure of any sort which arises in every connected hypergraph H which corresponds to a k-map?

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.

† 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.

I'm working in a setting involving conmstraints 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.

† 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.