Maximum genus of an abstract "cycle complex"

Question

Let us define an abstract "cycle complex" as the following combinatorial object: it is $(V, C)$, where $V$ is a set of $n$ nodes, $C$ is a set of $c$ cyclically ordered subsets of $V$, each of size exactly $s$, and it is assumed that two sets in $C$ intersect on at most one node. Let us define the genus of $(V, C)$ as the minimum genus of an orientable surface in which $(V, C)$ can be embedded. By "embedded," we mean that we can place the nodes $V$ in the surface such that:

1. Each set $X \in C$ is represented by a connected region of the surface,
2. If the nodes on the boundary of this region are read in clockwise order, we get exactly the set of nodes in $X$ in their given circular ordering
3. The intersection of the regions corresponding to $X_1, X_2 \in C$ is the same as $X_1 \cap X_2$. That is, the regions are disjoint if $X_1 \cap X_2 = \emptyset$, or it is exactly their single point of intersection if there is one.

Question 1: Is there a "real name" for this combinatorial object that I can search for to find relevant literature?

Question 2: I am specifically interested in extremal upper bounds on the genus $g$, i.e. results of the form "$g \le f(n, c, s)$" for some function $f$. Is anything like this known?

Answer 1

Let's first consider the special case that each node appears in exactly two sets in $C$. (Nodes that only appear in one set are irrelevant and can be deleted without changing the possible embeddings, and I will say something about nodes that appear in more than 2 sets later).

Then we can define the "dual" of a cycle complex $(V,C)$ with each set in $C$ of size $s$ to be the $s$-regular graph $G=(V',E')$ where there is a vertex $v_X\in V'$ for each set $X\in C$ and an edge $e_w\in E'$ for each node $w\in V$. Then the cyclic orderings of each set $X$ determine a cyclic ordering of the edges around each vertex $v_X$ and this gives rise to a rotation system. I have not tried to write out a formal proof but I believe your notion of embedding agrees with the notion of embedding there.

So at least in this special case, Question 2 is equivalent to determining the genus of the rotation system. In fact, if you just want a bound in terms of $n,c,s$ then we can just ask about the genus of the graph $G$, or actually the "genus distribution" of the graph. These are well-studied problems and a simple upper bound for the maximum genus of the graph (see e.g. Section 3.4.7 of Gross and Tucker's book "Topological Graph Theory" or Theorem 16.2.3 in Gross and Yellen's book "Graph Theory and Its Applications") is (using the notation from your question):

$$g\leq \frac{\lfloor n-c+1\rfloor}{2}.$$

I'm not sure if $s$-regularity buys us anything, but maybe someone who knows can add a comment / answer.

I think you can reduce general cycle complexes to the above case as follows: For each node $x$ which appears in more than two sets in $C$, do the following. Suppose that $x$ appears in sets $X_1,\dots, X_k$. Then replace $x$ in $X_1,\dots,X_k$ by $k$ new nodes $x_1,\dots,x_k$ (and delete $x$ from $V$). Then create a new set $X_x$ which contains $x_1,\dots,x_k$ with some cyclic ordering $\sigma_x$.

When you're finished, you don't quite have a cycle complex under your definition since the $C'$ are not necessarily of size $s$. However, you can still apply the previous construction to get a graph and a rotation system, and the genus will be the minimum genus of the rotation system under all possible choices of the $\{\sigma_x\}$. I don't immediately see how to find a good bound for this, but it seems possible. In particular I'll leave it to you to figure out if there's a useful analogue of the "simple bound" above.

Note that we had to make choices of the $\sigma_x$ so we can't map general cycle complexes to rotation systems (so they don't give a perfect answer to your Question 1).