Constrained intersection representations and forbidden patterns
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Constrained intersection representations and forbidden patterns".
Jane: Here's the gist of the paper. The study investigates the relationship between two graph classes: those defined by geometric intersections (grounded) and those defined by forbidden substructures (patterns).
Tom: The research explores whether this dichotomy is a general phenomenon across various graph classes.
Jane: Key contributions include identifying a family of patterns on four vertices and establishing a natural hierarchy for intersection graphs of strings whose classes are interleaved.
Tom: A significant result is the proof that a class of ordered intersection graphs cannot be characterized by any finite set of forbidden patterns.
Paper summary: Tom: We've talked about how the paper identifies a family of patterns on four vertices and sets up a hierarchy for intersection graphs of strings. Basically, the thesis is to explore if the way we define graphs geometrically versus by forbidding substructures is just a general thing across different graph classes.
Jane: The paper claims they find this connection but then immediately shows it's not as simple as you might think. They identify these patterns and establish a hierarchy for intersection graphs of strings that are nicely interleaved, which raises hopes about proving those connections >
Lu: Then they follow up with a major result, proving that a class of ordered intersection graphs simply cannot be characterized by any finite set of forbidden patterns, even though there's another class that *is* defined by patterns >
Meng: That’s the core tension they are exploring: can we always describe these complex structures just by looking for forbidden shapes, or is geometry a fundamentally different language?
Lalam: They also have this dual impossibility result where they show that while there's a pattern-defined class that doesn't have certain natural operations like translation and scaling, you *can* find representations if you allow more exotic ways to represent the graphs >
Tom: So, it’s not a simple yes or no to this dichotomy; it’s about finding the right kind of representation—geometric versus pattern-based—for specific graph classes.
Jane: And they establish hierarchies between pattern-defined classes, like constrained rectangles and constrained string graphs, showing how they fit into a structure relative to geometry-defined classes >
Lu: Specifically, they show inclusions like constrained bigrounded string graphs being a subset of C less than ab and constrained monotone string graphs being a subset of C less than abc >
Meng: Those inclusions are important because they give us concrete boundaries for where these graph classes live in relation to each other based on their complexity >
Lalam: And they prove there's no finite set of patterns that characterizes constrained monotone string graphs, which is a really strong statement about the unordered setting >
Conclusion: Tom: So, looking at "Constrained intersection representations and forbidden patterns," the authors are essentially showing that the way we define structure matters greatly depending on whether we are talking about ordered or unordered graphs >
Jane: They’re arguing that these two approaches—geometric intersections and forbidden patterns—are not just two separate tools, but they interact in a very specific, hierarchical way that depends on the class of graph you're looking at >
Lu: The main implication is that for some classes, you can never capture the full structure just by looking at a finite set of local forbidden patterns >
Meng: This means if we’re building systems where we rely heavily on pattern recognition, we need to be careful because there might be structural elements that require a more global or geometric view to understand them >
Lalam: And the title itself points to this interplay between constraints and representation, showing that what you choose as your constraint—geometric or forbidden—determines the kind of structure you can actually represent >
Université Claude Bernard Lyon 1 · CNRS · Université Paris Cité
cs.DM, math.CO
Submitted: 2026-11-12
Updated: 2026-11-12
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 90/100
The gist: The study investigates the relationship between two graph classes: those defined by geometric intersections (grounded) and those defined by forbidden substructures (patterns).
Key concepts
- Grounded Graph Classes
- These are graph classes defined by how elements intersect geometrically in a space. The paper focuses on 'grounded' representations, which involve specific intersection constraints like those found in string graphs or interval representations. These definitions relate the structure of the graph directly to spatial arrangements.
- Forbidden Patterns
- This refers to a set of small, specific subgraphs that are explicitly excluded from belonging to a certain class. The goal is to see if any finite collection of these forbidden patterns can completely describe an entire complex class of graphs. The study investigates the limits of this pattern-based description.
- Constrained Monotone String Graphs
- These are specific types of string graphs where the constraints involve monotonicity—meaning certain structural properties must increase or decrease consistently along a sequence. The paper proves that these graphs cannot be fully described by any finite set of forbidden patterns, highlighting a limitation in pattern-based characterization for these geometrically defined structures.
- Intersection Representation
- This is a way to define a graph based on how geometric objects (like intervals or threads) overlap. The paper introduces 'grounded threads' and 'first-interval intersection' constraints as specific, non-standard ways to represent graphs, showing that these geometric representations are distinct from pattern definitions.
Terminology
Summary
The study investigates the relationship between two graph classes: those defined by geometric intersections (grounded) and those defined by forbidden substructures (patterns). p. 0 Constrained intersection representations and
forbidden patterns
Laurent Feuilloley #
Université Claude Bernard Lyon 1, CNRS, LIRIS
Michel Habib #
Université Paris Cité, CNRS, IRIF
Amalia Sorondo #
Université Paris Cité, CNRS, IRIF
Abstract
We study the interplay between two types of graph classes: the ones defined by intersections of
geometric objects and the ones defined by the absence of a substructure. More precisely, we study
intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch,
and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered
induced subgraphs. More precisely, we study
intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch,
and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered
induced subgraphs. These two approaches are fundamentally different, but it is known that several
interesting graph classes have both types of characterizations, and we aim to understand whether
this is a general phenomenon.Where the paper says it
Where the paper says it
Key contributions include identifying a family of patterns on four vertices and establishing a natural hierarchy for intersection graphs of strings whose classes are interleaved. p. 0 Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection
graphs of strings whose classes are nicely interleaved. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we
study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy
that admits no intersection representation, if we require this representation to be closed under
natural operations such as translation and scaling. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy
that admits no intersection representation, if we require this representation to be closed under
natural operations such as translation and scaling. However, it turns out that if we allow slightly
more exotic intersection representations, then we can find one for this pattern-defined class.Where the paper says it
Where the paper says it
Where the paper says it
The paper establishes hierarchies between pattern-defined classes (e. p. 5 ) See Figure 2
for illustrations of the geometric configurations. Both the pattern-defined classes and the geometry-defined classes form hierarchies. We
refer to Figure 2 for a visual aid in this discussion. Constrained intervals
Constrained rectangles = C
<
b
C
<
a
Constrained bigrounded strings
C
<
ab
Constrained monotone strings
C
<
abc
Constrained strings
C
<
abcd
Figure 2 Diagram representing the interleaving of pattern-defined and geometry-defined classes
we study. First, if a
graph is known to be some kind of intersection graph of grounded strings, then it inherits the
results on outer-string graphs, for example the subexponential-time algorithm for maximum
independent set [23]. Closer to our paper, the algorithm of [17] for computing a maximum
independent set on constrained rectangle graphs uses the geometry characterization and not
the ordering: it is a dynamic program whose induction relation corresponds to rectangles being
included in some area of the plane.Where the paper says it
Where the paper says it
Where the paper says it
-
Constrained bigrounded string graphs C<ab. p. 5
Where the paper says it
) We also consider constrained monotone string graphs, where in addition the curves must be increasing and monotone in both axes. Finally, we consider constrained bigrounded string graphs which correspond to x-monotone curves (i.
-
Constrained monotone string graphs C<abc. p. 5
Where the paper says it
For patterns: C < a ⊆ C< ab ⊆ C< abc ⊆ C< abcd follows from the definitions of pattern-defined classes, see [22] (one can also replace C < a by C < b ). For geometric classes, it is clear that constrained string graphs contain both constrained monotone string graphs and constrained bigrounded string graphs.
-
Constrained string graphs C<abcd. p. 5
Where the paper says it
For patterns: C < a ⊆ C< ab ⊆ C< abc ⊆ C< abcd follows from the definitions of pattern-defined classes, see [22] (one can also replace C < a by C < b ). For geometric classes, it is clear that constrained string graphs contain both constrained monotone string graphs and constrained bigrounded string graphs.
Theorem 8 proves that there is no finite set of patterns that characterizes constrained monotone string graphs, achieved by constructing a family of ordered graphs called cocomparability suns whose directed height graph has arbitrarily large directed girth, leading to a contradiction if they were characterized by a finite pattern set. p. 8 This is illustrated by Figure 6. Next, we prove that there is an infinite family of ordered graphs, that we call the
cocomparability suns, such that the corresponding directed graphs Dh have arbitrarily large
directed girth (that is, their smallest directed cycle can be arbitrarily large). Based on these axioms, we prove that C
<
a does not admit a standard constrained intersection characterization. ▶ Theorem 10.Where the paper says it
Where the paper says it
The paper introduces non-standard geometric representations utilizing grounded threads
and the first-interval intersection
constraint, showing that C<a is exactly the class of ordered graphs admitting a constrained first-interval intersection representation of threads (Theorem 12).
Extensions to the unordered setting employ an Constrained intervals
Constrained rectangles = C
<
b
C
<
a
Constrained bigrounded strings
C
<
ab
Constrained monotone strings
C
<
abc
Constrained strings
C
<
abcd
Figure 2 Diagram representing the interleaving of pattern-defined and geometry-defined classes
we study. The arcs represent inclusions in the natural order, thick arcs represent strict inclusions. There is a contradiction between the last two items. Pattern-defined class with no geometry characterization
We have just established that some natural geometry-defined classes cannot be captured by
forbidden patterns.ordering gadget
and a generalized Cycle Lemma (Lemma 47), leading to Theorem 13, which states there is no finite set of patterns that characterizes grounded monotone string graphs. Strict inclusions between unordered pattern-defined classes (e. p. 4Where the paper says it
Where the paper says it
The final conclusion is Conjecture 14: there is no finite set of patterns that characterizes grounded monotone string graphs. p. 6 2
At that point, the natural strategy is: (1) to take the Pach-Tomon graph, transform it
into a pattern by replacing the edges that are not in the graph by forbidden edges, (2) to
add it to Pabc in the list of forbidden patterns, and (3) to hope that this new set of forbidden
patterns characterizes constrained monotone string graphs. We prove that not only this would not work, but there is no characterization of constrained
monotone string graphs using a finite number of patterns!Where the paper says it
The proof structure for Theorem 8 relies on cocomparability suns and the directed height graph Dh(G, <). p. 8 Cocomparability
suns are described in Figure 6, and the (long) formal definition is Definition 36 in Section 5. 2k
2k − 2
4
2
2k + 1
2k + 3
4k − 3
4k − 1
2k − 1
3 5
1
2k + 2
4k − 4 4k − 2
4k
·
·
·
·
·
·
·
·
·
·
·
·
···
···
2k
2k − 2
4
2
2k + 1
2k + 3
4k − 3
4k − 1
2k − 1
3 5
1
2k + 2
4k − 4 4k − 2
4k
·
·
·
·
·
·
·
·
·
·
·
·
···
···
Figure 6 The ordered graph (G, <) (left) and its directed height graph Dh(G, <) (right). An important clarification is needed here: Theorem 2 is stated for ordered graphs, but in
the literature one finds the unordered version: for an unordered graph G, G has an ordering
with a grounded rectangle representation if and only if there exists an ordering that does not
contain the pattern Pb. Unordered graphs are more standard than ordered graphs, but going
from one to the other via the existential quantification on the ordering is artificial: the proof
naturally considers the grounding ordering and the ordering avoiding the pattern to be the
same. By construction, Dh(K, <K) is a directed subgraph of Dh(G, <). But then, as the
directed girth of Dh(G, <) was strictly greater than the size of Dh(K, <K), the directed
height graph Dh(K, <K) is necessarily acyclic.Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve pattern recognition for intersection graphs by using forbidden patterns to characterize classes of ordered graphs, which allows for finite characterizations in NP. This enables efficient recognition algorithms for classes like interval and permutation graphs by building an ordering that avoids specific patterns.
-
Develop a framework to determine if a graph admits a standard grounded intersection representation by checking the existence of two intersecting shapes u and v such that there is a ball around the grounding point of shape v that the shape of u does not intersect. This allows for distinguishing classes like C<a from others based on geometric properties rather than just pattern avoidance.
-
Create an algorithm to test if an ordered graph belongs to a class defined by geometric intersection representations, such as constrained monotone string graphs, by checking if its directed height graph Dh(G, <) is a directed acyclic graph. This provides a combinatorial criterion for membership in these classes.
-
Implement techniques to extend results from ordered graphs to unordered settings using cycle extensions and ordering gadgets. This allows for the study of unordered pattern-defined classes and provides tools to strengthen inclusion hierarchies between classes like Cabc and Cabcd.
-
Design a method to construct non-standard constrained intersection representations, specifically using grounded threads with first-interval intersection constraints, to characterize the class C. This representation allows for a more nuanced geometric understanding of pattern avoidance that is not captured by standard grounded representations.
Abstract
We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy that admits no intersection representation, if we require this representation to be closed under natural operations such as translation and scaling. However, it turns out that if we allow slightly more exotic intersection representations, then we can find one for this pattern-defined class.
Sources
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds