Flipping and Forking

Szymon Toru\'nczyk; Wojciech Przybyszewski

REVIEW 3 major objections 4 minor 1 cited by

Flipping and Forking

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In monadically stable relational structures, forking independence over a model is exactly flip independence at every radius.

desk verdict Genuinely new bridge between flips and forking in relational structures, but the main theorem's converse direction relies on an unproved distance bound in Lemma 48 that a referee must check. read the letter →

arxiv 2505.16745 v1 pith:3MZATAWF submitted 2025-05-22 cs.LO math.LO

Wojciech Przybyszewski , Szymon Toruńczyk This is my paper · ORCID

classification cs.LOmath.LO MSC 03C4503C13

keywords monadicallystableclassesforkingindependencefliprelationalstructuresflip-flatnessseparationgamenowheredensefinitemodeltheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to prove that forking independence, the model-theoretic notion of two elements being independent over a model, is exactly flip independence in monadically stable relational structures. Its central result (Theorem 16) states that for monadically stable $M \preceq N$, elements $a,b$ are forking independent over $M$ if and only if for every radius $r$ there is an $M$-flip of $N$ whose Gaifman graph has no path of length at most $r$ connecting $a$ and $b$. This matters because forking independence is the central tool of stability theory, yet it is defined through types and finite satisfiability, whereas flips are a finitary, algorithmic operation that has driven recent work on tractable first-order model-checking classes. If the theorem is right, a core logical notion becomes a local combinatorial separation property, and the graph-theoretic flip machinery extends to structures with relations of arbitrary arity. The paper also characterizes forking independence more precisely in monadically stable graphs and in structures with nowhere dense Gaifman graphs.

What carries the argument

The central object is the $S$-flip for relational structures and the flip-distance it induces: $\mathrm{flip-dist}_{S}(a,b)=\min\{r : a \not\mid^{r}_{S} b\}$. A flip rewrites all relations by quantifier-free definitions with parameters from $S$, so it preserves logical meaning relative to $S$ while changing Gaifman paths. Lemma 47 gives the metric triangle inequality for flip dependence, so over a model in a monadically stable structure, forking dependence is exactly finiteness of this flip-distance. The load-bearing pieces are the normality lemmas 46 and 48, which guarantee that one $M$-flip can separate both $a$ and $b$ from the entire model $M$ at a prescribed radius, together with Gaifman locality (Corollary 21) and definability of types (Theorem 28), which translate the large flip-distance into a definable separation of types.

What would settle it

To test the main theorem, look for a monadically stable pair $M \preceq N$ and elements $a,b\in N$ such that for every $r$ some $M$-flip has no Gaifman path of length $\le r$ between $a$ and $b$, yet some formula with parameters from $M\cup\{b\}$ holds of $a$ in $N$ and of no element of $M$; that would directly contradict Theorem 16. To test the auxiliary characterization, instantiate Lemmas 53--55 with a single ternary relation and check whether the separation game still forces flip-flatness.

Watch

Extended reading notes

Core claim

The authors introduce flips for arbitrary relational structures: $A'$ is an $S$-flip of $A$ when every relation of $A'$ is quantifier-free definable in $A$ with parameters from $S$, and vice versa. They define $a \mid^{r}_{M} b$ to mean that some $M$-flip of the structure separates $a$ from $b$ at Gaifman distance greater than $r$, and prove (Theorem 16) that in monadically stable structures $M \preceq N$, for all $a,b\in N$, $a \mid_{M} b$ holds if and only if $a \mid^{r}_{M} b$ holds for every $r\in\mathbb{N}$. Here $\mid_{M}$ is forking independence over the model $M$, understood through finite satisfiability: $\mathrm{tp}(a/M\cup\{b\})$ is finitely satisfiable in $M$. The proof rests on normality lemmas (46 and 48) showing that in existentially monadically dependent, atomic-stable structures a single flip can push the whole model $M$ away from $a$ and $b$ at arbitrarily large radius, after which Gaifman locality and definability of types convert the flip separation into finite satisfiability. A converse (Proposition 17) shows that if a stable structure $M$ has the flip/forking coincidence in every elementary extension and substructure, then $M$ is monadically stable.

Load-bearing premise

The load-bearing premise is that the graph-level normality lemma, asserting that one flip can push the elementary model $M$ arbitrarily far from both $a$ and $b$, survives the passage to arbitrary relational signatures; a separate fragile import is the unproved 'mutatis mutandis' transfer of Lemmas 53--55 that supports Theorem 19.

Editorial extensions

If this is right

In every monadically stable structure, forking independence over a model is a local combinatorial separation property: checking all finite radii against $M$-flips decides it.
Forking dependence on singletons over an elementary substructure forms an equivalence relation, with the flip-distance metric making transitivity immediate.
The flip-flatness and bounded-separation-rank conditions characterize monadically stable classes of relational structures (Theorem 19), so the graph-theoretic flip-decomposition toolbox now applies to higher-arity structures.
For structures with nowhere dense Gaifman graphs, forking independence over $M$ is the same as lying in different connected components after removing $M$ (Theorem 11), recovering and extending the earlier path-separation criterion for nowhere dense graphs.
In monadically stable graphs, forking dependence is equivalence in the transitive closure of the discrepancy relation that compares actual adjacency with adjacency predicted from $M$ (Theorem 9).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because flip independence at radius $r$ is finitary, Theorem 16 suggests an algorithmic route to forking independence: decide dependence by searching for $M$-flips and short Gaifman paths. The paper does not develop this algorithmic consequence, though it expects the related separation-rank condition to matter for tractability.
The flip-distance metric may extend density-independent complexity measures such as flip-width from graphs to arbitrary relational structures, giving a new parameter for higher-arity classes; this extension is not pursued in the paper.
The proof of Theorem 19 relies on three lemmas (53, 54, and 55) declared to follow "mutatis mutandis" from the graph versions without full proofs; if any of those transfers fails for relations of arity at least three, that characterization would need repair even though Theorem 16 might remain valid.
Proposition 17 gives the converse only under the assumption that $M$ is already stable; it is plausible that the flip/forking coincidence itself, stated for all elementary extensions and substructures, could serve as a defining property of monadic stability, and testing whether the stability assumption can be dropped would sharpen the boundary.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The central claim is a real bridge result: forking independence over models in monadically stable relational structures equals flip independence. And the paper is mostly honest about what it proves and what it inherits from the graph papers. But the converse direction of the main theorem rests on a distance bound in Lemma 48 that is asserted, not proved, and it is not obviously true in higher arities.

What is genuinely new: the S-flip definition for arbitrary relational structures (Definition 12), the finite-types-of-balls argument (Lemma 63), and the nowhere-dense case (Theorems 10 and 11). Theorem 10's proof via incidence graphs is clean; Theorem 11's separation criterion is a proper generalization of Ivanov. The flip-independence vs forking-independence equivalence is conceptually exactly what the graph flips literature was pointing at. I also like the Braunfeld-Laskowski converse, Proposition 17; it shows the authors thought about what the equivalence actually buys.

The soft spots. The stress-test note is right: Lemma 48's proof says the S from Lemma 67 is at distance at most 2 from U, 'for the same reason as in the case of graphs.' In graphs that bound is real — the parameters in the type definitions are witnesses at distance 1–2 (Lemma 57). Lemma 67 builds S from separating tuples and from the parameters of the ψ_i definitions, and nothing bounds their distance. In a higher-arity monadically stable structure, the atomic type of a tuple over M can depend on parameters far from the tuple; the paper's own closest-common-ancestor example is the right warning. If S reaches out that far, the flip can change edges far from U, and the controlled-distance iteration in Lemma 48 collapses. This is a genuine gap in Theorem 16's right-to-left direction, not a fatal objection — the theorem may be salvageable — but as written the central equivalence is not fully supported. There is also a garbled sentence in the proof of Theorem 16 ('Since a |⌣^{7q}_M bM, there is As N is interpretable...') right where the normality step does its work, plus a typo in Lemma 39. Fixable, but a referee needs to see the fixed argument.

The Section 7 'mutatis mutandis' transfers for Lemmas 53–55 are a lesser issue: the separation-game arguments from [21] and [15] look portable, but the flip notion here changes the language, so the transfers deserve at least a sketch.

Send it to review. The central claim is important enough that the Lemma 48 gap should be caught and fixed in the refereeing process, not buried. The intended readers are model theorists working on forking and the structural-graph-theory people who use flips; both will want this result, and both should be told to read Lemma 48 carefully.

Referee Report

3 major / 4 minor

Summary. This paper introduces a notion of S-flips and flip independence for arbitrary relational structures, generalizing the graph-theoretic flip operation. The main result, Theorem 16, asserts that for monadically stable structures M ≼ N, forking independence over M coincides with flip independence at every radius. The paper also gives combinatorial characterizations of monadically stable classes of relational structures via flip-flatness and separation rank (Theorem 19), characterizes nowhere dense relational structures (Theorem 10), and provides specialized forking characterizations for monadically stable graphs and for structures with nowhere dense Gaifman graphs (Theorems 9 and 11). The proofs of Theorem 16 are developed in detail in the appendices using definability of types, Gaifman locality, and Ramsey-theoretic tools.

Significance. If the main theorem is correct, it is a substantial conceptual contribution: it provides a purely combinatorial characterization of forking independence over models in monadically stable structures and explains the role of flips in monadically stable graph classes. The definitions of flips and flip independence for relational structures are natural, and the paper gives detailed appendix arguments with explicit constants from Gaifman locality. The paper also clearly separates the purely combinatorial notions from the model-theoretic ones and states its reliance on external results. However, the current manuscript contains proof gaps at load-bearing points in the appendix, so the significance is conditional on those gaps being repaired.

major comments (3)

[Appendix D.3, proof of Lemma 46] The opening normalization 'By Corollary 30, possibly after doing an ∅-flip, we can assume that for every relation R and every partition of its variables into two sets, there is no tuple outside M that is complete to M' is not established. Corollary 30 rules out the simultaneous existence of a complete tuple in one part and an anti-complete tuple in the conjugate part; it does not rule out a complete tuple by itself. Moreover, a single ∅-flip would have to eliminate complete tuples for all relations and all partitions simultaneously without creating new complete tuples for other partitions, and no argument is supplied for why this is possible. This normalization is used in the induction in Lemma 46, which in turn is used in both directions of Theorem 16 and in Lemma 52 for Theorem 50, so it is load-bearing.
[Appendix D.2-D.3, Lemma 67 and Lemma 48] The proof of Lemma 48 states that 'for the same reason as in the case of graphs, the set S constructed in Lemma 67 is at distance at most 2 from U.' In the graph analogue (Lemma 57 in Appendix B) this bound holds because S is built from separating witnesses chosen from the neighborhoods of the u_i and from parameters w_i^j that can be taken at distance at most 2 from u_i, as cited from [11, Lemma 2.10]. Lemma 67 constructs S from arbitrary separating tuples c_ij in M^z and from the parameters of the type-defining formulas psi_i supplied by Theorem 28; no distance bound on these parameters is stated or proved. In higher-arity monadically stable structures, the atomic type of an element over M can be governed by parameters arbitrarily far from the element, as illustrated by the closest-common-ancestor structure in Example 14. If such far-away parameters enter S, a flip based on S can change distances far from U, and the controlled-distance induction in Lemma 48 is unsupported. This is a genuine proof gap in the converse direction of Theorem 16, not a demonstrated counterexample to the theorem.
[Section 7, Lemmas 53-55] The combinatorial characterizations in Theorem 19 and Theorem 50 depend on Lemmas 53, 54, and 55, each of which is delegated to a 'mutatis mutandis' transfer of graph-theoretic arguments from [21] and [15]. This transfer is not routine: the flip operation in Definition 66 adds new relation symbols and changes the way distances in the Gaifman graph behave, and the separation game is defined in terms of the new flip independence relation. The paper should either provide the transferred proofs or give a detailed verification that the graph arguments apply unchanged to arbitrary finite relational languages. As written, the flip-flatness and separation-rank characterizations are not fully established.

minor comments (4)

[Section 2.3, Proposition 17] The statement reads 'Let M be a monadically stable structure and assume ... Then M is monadically stable.' The proof in Appendix D.4 and the surrounding text show that the intended assumption is that M is stable, not monadically stable; as printed the proposition is vacuous.
[Section 6.1, proof of Theorem 16] The sentence 'Since a |⌣^{7q}_M bM, there is As N is interpretable in N′ via a quantifier-free formula with parameters from M' is garbled and should be rewritten; in particular, the use of Lemma 49 to transfer finite satisfiability of tp(a/M) to N′ should be made explicit.
[Section 7, Lemma 55] Lemma 55 speaks of a 'definably flip-flat' class, but Definition 18 defines only 'flip-flat'; either define the former notion or state explicitly that the two notions coincide in the setting of the paper.
[Appendix D.2, Definition 66] The phrase 'an syntactic (α,S)-flip' should be 'a syntactic (α,S)-flip'; the spelling and article should be checked throughout the appendix.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: flip independence and forking independence are defined independently, and the cited graph lemmas from prior work are external, published results that do not assume the target equivalence.

full rationale

Flip independence (Definitions 15 and 45) is introduced as a purely combinatorial condition on distances in an S-flip (Definition 12), with no reference to forking; forking independence is imported as the standard finite-satisfiability relation over models (Definitions 25-26). Theorem 16 is then proved from separate combinatorial lemmas (Lemmas 46 and 48) developed in Appendix D, using definability of types (Theorem 28), Gaifman locality (Corollary 21), and Ramsey/Morley-sequence arguments (Lemmas 31, 63, and 67), none of which assumes the equivalence to be proved. The graph case (Theorem 8) cites Lemma 41 and Lemma 56 from [20], but those are independently published graph-theoretic results from prior ICALP work; they do not contain or assume the forking/flip equivalence. The transfers stated mutatis mutandis in Lemmas 53-55 from [21] and [15] are proof-completeness shortcuts, and Lemma 48 contains an unproved distance bound on the parameter set S from Lemma 67; these are correctness risks for the written proof, not examples of a prediction reducing by construction to a fitted input or of a notion defined in terms of the target notion. No parameter is fitted to data and then reported as a prediction, and the central equivalence is not assumed by the definitions or by the cited external lemmas. Self-citation is present and occasionally load-bearing, but it cites previously established, externally falsifiable results rather than the present theorem, so it does not constitute circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

All free parameter slots are empty: the paper contains no numerical fitting. The axioms are standard background theorems plus one notable domain-assumption: the transfer of three graph-specific lemmas to relational structures is asserted without full proof. The invented entities are new mathematical definitions (S-flips and flip independence), which carry independent evidence through their equivalence with existing model-theoretic forking.

assumptions (5)

standard math Gaifman locality theorem (Fact 20, Corollary 21): for formulas of quantifier rank q, satisfaction over tuples at distance > 7q reduces to local formulas.
Used in the proof of Theorem 16 and Theorem 11 to replace a global formula with a local one after a flip separates elements.
standard math Definability of types in stable theories (Theorem 28) and Harrington's Lemma (Lemma 29).
Used throughout Sections 4 and 6 to define expected neighborhoods/types of elements over an elementary substructure, e.g. in the definition of relation E′ and in Lemma 67.
standard math Braunfeld-Laskowski f.s. dichotomy theorem [9, Theorem 1.1]: a theory is monadically dependent iff it has the finite-satisfiability dichotomy.
Used in the proof of Proposition 17, the converse direction characterizing monadic stability.
domain assumption The graph-specific proofs of the Separation Game (Lemma 53), flip-flatness (Lemma 54), and 'flip-flat implies monadic stability' (Lemma 55) transfer unchanged to finite relational languages.
These lemmas are stated with 'mutatis mutandis' references to [21] and [15]; no full proof for relational structures is given in the paper.
standard math Podewski-Ziegler / [27, Proposition 5.7]: nowhere dense Gaifman graph classes are monadically stable (Lemma 60).
Used in Theorem 10, implication (1) to (2).

invented entities (2)

S-flip of a relational structure (Definition 12) independent evidence
purpose: Extends graph flips to arbitrary finite relational structures; a structure A′ is an S-flip of A if each relation of one is quantifier-free definable in the other with parameters from S.
The notion is defined explicitly and is then tied to the existing model-theoretic notion of forking independence by Theorem 16, providing an external benchmark; it also supports the combinatorial characterizations in Theorem 19.
flip independence relation |⌣^r_S (Definition 15) independent evidence
purpose: Combinatorial separation relation used to characterize forking independence.
The equivalence with forking independence (Theorem 16) and the converse (Proposition 17) give external falsifiable handles.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Flipping and Forking." pith.science (2026). https://pith.science/paper/3MZATAWF

@misc{pith2026250516745,
  author       = {Pith},
  title        = {Pith review of: Flipping and Forking},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3MZATAWF}},
  note         = {Machine review of arXiv:2505.16745}
}

abstract

Monadic stability and the more general monadic dependence (or NIP) are tameness conditions for classes of logical structures, studied in the 80's in Shelah's classification program in model theory. They recently emerged in algorithmic and structural graph theory and finite model theory as central notions in relation with the model checking problem for first-order logic: the problem was shown to be fixed-parameter tractable for inputs which come from a fixed class of graphs which is monadically stable, and is conjectured to be tractable in all monadically dependent classes. Several combinatorial characterizations of such graph classes turned out to be essential in their algorithmic treatment; they are all based on the fundamental operation of "flipping" a graph. We introduce the notions of $\textit{flips}$ and $\textit{flip independence}$ in arbitrary relational structures. We lift prior combinatorial characterizations of monadically stable graph classes to monadically stable classes of relational structures. We show the equivalence of flip independence with $\textit{forking independence}$ (over models) -- a logical notion of paramount importance in stability theory -- in monadically stable structures, shedding new light on the relevance of flips, also characterizing forking independence (over models) combinatorially. We give more precise descriptions of forking independence in the case of monadically stable graphs, and relational structures with a nowhere dense Gaifman graph.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
cs.DM 2026-07 accept novelty 7.5 of 10

Every monadically dependent hereditary graph class has almost-linear neighborhood complexity and n^{o(1)} radius-1 merge-width, witnessed by an efficient construction-sequence algorithm.

Reference graph

Works this paper leans on

16 extracted references · 14 canonical work pages · cited by 1 Pith paper

[15]

Do the same for each(M ¯y,S′)-class that is flipped

For each(M ¯x,S′)-class A that is flipped add to the language ofM′ a new relation symbol RA, interpreted asA⊆M|¯x|. Do the same for each(M ¯y,S′)-class that is flipped

work page
[1]

Sinceu̸|⌣ 1 GGv we havedistH′(u,v ) = 1. (2)→(3). Condition distH′(u,G ) > 1 means that we flipped inH the S-class which contains u (denote it byU) with everyS-class that contains a neighbor ofu in G. In particular, for everyS-class T we have thatu is either complete or anti-complete toT∩G. Observe thatG ≼H implies that for every nonemptyS-classT the setT...

work page
[2]

17 Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk

doi:10.1145/3618260.3649739. 17 Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes.CoRR, abs/2403.15201, 2024. arXiv: 2403.15201. 18 Zdeněk Dvořák. Induced subdivisions and bounded expansion.Eur. J. Comb., 69(C):143–148, mar 2018. doi:10.1016/j.ejc.2017.10.004. 19 Haim G...

arXiv 2024
[3]

if distH(v,U )>r ⩾ 3 then distH′(v,U )>r − 2, and

work page
[4]

Moreover, for everyv∈H\G,

unless there isu∈U which is complete toG, then for allv,w ∈H, if distH(w,S )> 1 then H|=E(v,w ) ⇐⇒ H′|=E(v,w ). Moreover, for everyv∈H\G,

work page
[6]

28 Flipping and Forking Proof

if distH(v,G )>r ⩾ 1 then distH′(v,G )>r . 28 Flipping and Forking Proof. Let{u1,...,u k} ⊆U contain one vertex from each type inTypesE(U/G). Let W0⊆G be obtained by taking for each pairui,uj∈U a vertexw∈G that is adjacent to exactly one ofui,uj. Moreover, for everyui that has a neighbor we take at least one such neighbor toW0. By Theorem 28, the neighbor...

work page
[7]

there exists anS-flip H′ of H for some finiteS⊆ G such that distH′(u,G ) > 1 and distH′(u,v ) = 1

work page
[8]

H|=ψu(v) xorE(u,v ), equivalently,u ↭G v. Proof. (1)→(2). LetH′ be anS-definable flip ofH for someS⊆G such thatdistH′(u,G )>

work page

Show all 16 references

[10]

the monotone closure ofC is monadically stable,
[11]

C is monadically stable andG is weakly sparse,
[12]

x and y are connected by a path of length at mostr which avoids all vertices fromS

C is monadically dependent andG is weakly sparse. The following lemma yields the implication (1)→(2) in Theorem 10. ▶ Lemma 60(Follows from [27, Proposition 5.7] and [32], see [7, Theorem 30]). LetC be a class of structures in a finite relational language such thatGaif (C) is ...
[13]

We will refer to these parts as(M ¯x,S′)-classes and (M ¯y,S′)-classes respectively

Partition M ¯x according toα(¯x; ¯y)-types overS′, andM ¯y according toα(¯y; ¯x)-types over S′. We will refer to these parts as(M ¯x,S′)-classes and (M ¯y,S′)-classes respectively
[14]

In the first case we say that the pair(A,B ) is not flipped and in the other we say that this pair is flipped

Change the interpretation ofR in M′ such that for every(M ¯x,S′)-class A and every (M ¯y,S′)-class B we have either M|=α(¯a,¯b) ⇐⇒ M′|=α(¯a,¯b) for every ¯a∈A,¯b∈B or M|=α(¯a,¯b) ⇐⇒ M′̸|=α(¯a,¯b) for every ¯a∈A,¯b∈B. In the first case we say that the pair(A,B ) is not flipped ...
[16]

We say that a structureN′ is asyntacticS-flip of N if it can be obtained fromN by a sequence of such operations

Interpretations of all the other relations remain unchanged. We say that a structureN′ is asyntacticS-flip of N if it can be obtained fromN by a sequence of such operations. Clearly an syntacticS-flip is a special case of anS-flip in the sense of Definition 12. In the proof be...
[1986]

32 Klaus-Peter Podewski and Martin Ziegler

doi:10.2307/2274072. 32 Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101–107, 1978. 33 Saharon Shelah. Monadic logic: Hanf Numbers, pages 203–223. Springer Berlin Heidelberg, Berlin, Heidelberg, 1986. doi:10.1007/BFb0098511. 34 Katrin...

1978
[2024]

6 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

doi:10.1145/3651151. 6 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width i: Tractable fo model checking.J. ACM, 69(1), November 2021.doi:10.1145/3486655. 7 Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos. Monadic NIP in M...

2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [15]

Do the same for each(M ¯y,S′)-class that is flipped

For each(M ¯x,S′)-class A that is flipped add to the language ofM′ a new relation symbol RA, interpreted asA⊆M|¯x|. Do the same for each(M ¯y,S′)-class that is flipped

work page

[2] [1]

Sinceu̸|⌣ 1 GGv we havedistH′(u,v ) = 1. (2)→(3). Condition distH′(u,G ) > 1 means that we flipped inH the S-class which contains u (denote it byU) with everyS-class that contains a neighbor ofu in G. In particular, for everyS-class T we have thatu is either complete or anti-complete toT∩G. Observe thatG ≼H implies that for every nonemptyS-classT the setT...

work page

[3] [2]

17 Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk

doi:10.1145/3618260.3649739. 17 Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes.CoRR, abs/2403.15201, 2024. arXiv: 2403.15201. 18 Zdeněk Dvořák. Induced subdivisions and bounded expansion.Eur. J. Comb., 69(C):143–148, mar 2018. doi:10.1016/j.ejc.2017.10.004. 19 Haim G...

arXiv 2024

[4] [3]

if distH(v,U )>r ⩾ 3 then distH′(v,U )>r − 2, and

work page

[5] [4]

Moreover, for everyv∈H\G,

unless there isu∈U which is complete toG, then for allv,w ∈H, if distH(w,S )> 1 then H|=E(v,w ) ⇐⇒ H′|=E(v,w ). Moreover, for everyv∈H\G,

work page

[6] [6]

28 Flipping and Forking Proof

if distH(v,G )>r ⩾ 1 then distH′(v,G )>r . 28 Flipping and Forking Proof. Let{u1,...,u k} ⊆U contain one vertex from each type inTypesE(U/G). Let W0⊆G be obtained by taking for each pairui,uj∈U a vertexw∈G that is adjacent to exactly one ofui,uj. Moreover, for everyui that has a neighbor we take at least one such neighbor toW0. By Theorem 28, the neighbor...

work page

[7] [7]

there exists anS-flip H′ of H for some finiteS⊆ G such that distH′(u,G ) > 1 and distH′(u,v ) = 1

work page

[8] [8]

H|=ψu(v) xorE(u,v ), equivalently,u ↭G v. Proof. (1)→(2). LetH′ be anS-definable flip ofH for someS⊆G such thatdistH′(u,G )>

work page