Constrained intersection representations and forbidden patterns

arXiv:2611.16849 · cs.DM, math.CO · Submitted 2026-11-12 · Read on arXiv

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

Where the paper says it

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.

The research explores whether this dichotomy is a general phenomenon across various graph classes. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

A significant result is the proof that a class of ordered intersection graphs cannot be characterized by any finite set of forbidden patterns. p. 0
Where the paper says it

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.

Furthermore, the paper presents a dual impossibility result: while there exists a pattern-defined class that lacks an intersection representation closed under natural operations like translation and scaling, such representations can be found if more exotic representations are permitted. p. 0
Where the paper says it

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.

The paper establishes hierarchies between pattern-defined classes (e. p. 5

Where the paper says it

) See Figure 2 for illustrations of the geometric configurations. Both the pattern-defined classes and the geometry-defined classes form hierarchies.

g., constrained intervals, constrained rectangles) and geometry-defined classes (e. p. 4
Where the paper says it

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.

g., constrained string graphs). p. 3
Where the paper says it

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.

Specific inclusions are shown:

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

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

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

Where the paper says it

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

Similarly, Theorem 10 demonstrates that the class C<a does not admit a standard constrained intersection characterization. p. 9
Where the paper says it

Based on these axioms, we prove that C < a does not admit a standard constrained intersection characterization. ▶ Theorem 10.

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

Where the paper says it

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.

g., C ab < C abc) are also established, with the proof showing that if C abc admitted a characterization by a grounded intersection representation, it would imply an inclusion not present in the established hierarchy (Proposition 52). p. 9
Where the paper says it

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.

The final conclusion is Conjecture 14: there is no finite set of patterns that characterizes grounded monotone string graphs. p. 6

Where the paper says it

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!

The research also suggests avenues for future exploration into more creative geometries and the structure of orderings corresponding to geometric representations.

The proof structure for Theorem 8 relies on cocomparability suns and the directed height graph Dh(G, <). p. 8

Where the paper says it

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

The proof of Theorem 13 involves showing that any equivalent ordering to a cocomparability sun fails to admit a grounded monotone string representation. p. 2
Where the paper says it

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.

This is achieved by showing that any such ordering must reproduce a pattern from the finite set F, leading to an induced subgraph whose directed height graph contains a cycle whose size contradicts the girth established for the larger graph. p. 9
Where the paper says it

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.

The analysis also details the construction of specific directed cycles in Dh(G, <') for various configurations.

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

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

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

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

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

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