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?
> 
> 
> 



Maximum genus of an abstract "cycle complex"
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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Graph_embedding) $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"](https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA661#v=onepage&q&f=false)) 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). 


