<p>I am interested in hypergraphs with interfaces, I'll call them simply &quot;graphs&quot; in the following.</p>
<p>Formally, a graph of sort <span class="math-container">$k$</span> is a tuple <span class="math-container">$(V,E,i)$</span> with <span class="math-container">$E\subseteq V^+$</span> is the set of edges, each edge is not necessarily binary, for instance <span class="math-container">$v_1v_2v_3$</span> links distinct vertices <span class="math-container">$v_1,v_2,v_3$</span> in this order.
The interface <span class="math-container">$i\in V^k$</span> is a list of <span class="math-container">$k$</span> distinct vertices.</p>
<p>A context is a graph together with a distinguished edge <span class="math-container">$h$</span> called its &quot;hole&quot;. Thus a context has both a sort, and an &quot;arity&quot;, which is the arity of its hole.</p>
<p>If <span class="math-container">$C$</span> is a context of sort <span class="math-container">$n$</span> and arity <span class="math-container">$k$</span>, and <span class="math-container">$G$</span> is a graph of sort <span class="math-container">$k$</span>, we define the substitution <span class="math-container">$C[G]$</span> as the graph obtained by removing replacing the hole of <span class="math-container">$C$</span> by <span class="math-container">$G$</span>, and identifying the vertices of the interface of <span class="math-container">$G$</span> with those of the hole of <span class="math-container">$C$</span>. The interface of <span class="math-container">$C[G]$</span> is that of <span class="math-container">$C$</span>.</p>
<p>I call &quot;island&quot; of a graph <span class="math-container">$G$</span> a subgraph <span class="math-container">$I$</span> such that there exists a context <span class="math-container">$C$</span> with <span class="math-container">$G=C[I]$</span>. Note that it implies that <span class="math-container">$I$</span> is an induced subgraph, except possibly for edges between vertices of its interface.</p>
<p>Notice that if <span class="math-container">$I$</span> is an island of <span class="math-container">$G=(V,E,i)$</span>, then vertices from <span class="math-container">$i$</span> can only appear in <span class="math-container">$I$</span> at the interface.
For instance, if <span class="math-container">$G$</span> is a triangle with binary edges and interface <span class="math-container">$v_1v_2v_3$</span> (all three vertices of <span class="math-container">$G$</span>), then its islands of sort <span class="math-container">$2$</span> are all pairs of distincts vertices, but the whole <span class="math-container">$G$</span> is not, because the interface of <span class="math-container">$G$</span> cannot be &quot;inside&quot; an island.</p>
<p>I want to understand the structure of maximal islands with a fixed sort. For instance here is a conjecture: for every pair of maximal binary islands, either they are the same when forgetting interfaces, or they intersect only on their interfaces.</p>
<p>Do you know of any paper or reference where this concept is studied ?</p>

CC BY-SA 4.0
2024-04-12T11:53:31.353Z
Can you explain the terminology? What is a "context"? Is "interface" the same thing as an "island"?
Emil Jeřábek
CC BY-SA 4.0
2024-04-15T10:08:00.163Z
@EmilJeřábek I added the necessary formalism, indeed it was needed.
Denis
CC BY-SA 4.0
2024-04-15T11:06:07.873Z
I’m still quite lost. First, any way I look at it, any graph $G$ is an island of itself, hence in particular, the only maximal island of $G$ is $G$? Second, how is $I$ an induced subgraph of $G$? Given a graph $G$, what stops me from e.g. making $G=C[I]$ where $C$ is the same as $G$ with a hole listing all vertices, and $I$ the empty graph on the same number of vertices?
Emil Jeřábek
CC BY-SA 4.0
2024-04-15T11:06:27.553Z
Is there any paper where these concepts are properly defined?
Emil Jeřábek
CC BY-SA 4.0
2024-04-17T16:28:09.760Z
@EmilJeřábek I added precisions and an example showing why $G$ is not always an island of itself, for some fixed island sort. Indeed the induced subgraph property is only true for edges involving at least one inner (ie non-interface) vertex.
Denis
<reference-request><graph-theory>
Induced subgraphs with interface
Denis
# Induced subgraphs with interface

(Asked by: username_0 on 2024-04-11)

I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following.

Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, each edge is not necessarily binary, for instance $v\_1v\_2v\_3$ links distinct vertices $v\_1,v\_2,v\_3$ in this order.
The interface $i\in V^k$ is a list of $k$ distinct vertices.

A context is a graph together with a distinguished edge $h$ called its "hole". Thus a context has both a sort, and an "arity", which is the arity of its hole.

If $C$ is a context of sort $n$ and arity $k$, and $G$ is a graph of sort $k$, we define the substitution $C[G]$ as the graph obtained by removing replacing the hole of $C$ by $G$, and identifying the vertices of the interface of $G$ with those of the hole of $C$. The interface of $C[G]$ is that of $C$.

I call "island" of a graph $G$ a subgraph $I$ such that there exists a context $C$ with $G=C[I]$. Note that it implies that $I$ is an induced subgraph, except possibly for edges between vertices of its interface.

Notice that if $I$ is an island of $G=(V,E,i)$, then vertices from $i$ can only appear in $I$ at the interface.
For instance, if $G$ is a triangle with binary edges and interface $v\_1v\_2v\_3$ (all three vertices of $G$), then its islands of sort $2$ are all pairs of distincts vertices, but the whole $G$ is not, because the interface of $G$ cannot be "inside" an island.

I want to understand the structure of maximal islands with a fixed sort. For instance here is a conjecture: for every pair of maximal binary islands, either they are the same when forgetting interfaces, or they intersect only on their interfaces.

Do you know of any paper or reference where this concept is studied ?

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: Can you explain the terminology? What is a "context"? Is "interface" the same thing as an "island"?  
> **username_0**: @EmilJeřábek I added the necessary formalism, indeed it was needed.  
> **username_1**: I’m still quite lost. First, any way I look at it, any graph $G$ is an island of itself, hence in particular, the only maximal island of $G$ is $G$? Second, how is $I$ an induced subgraph of $G$? Given a graph $G$, what stops me from e.g. making $G=C[I]$ where $C$ is the same as $G$ with a hole listing all vertices, and $I$ the empty graph on the same number of vertices?  
> **username_1**: Is there any paper where these concepts are properly defined?  
> **username_0**: @EmilJeřábek I added precisions and an example showing why $G$ is not always an island of itself, for some fixed island sort. Indeed the induced subgraph property is only true for edges involving at least one inner (ie non-interface) vertex.  

---

## 0 answers

