Follow

"The Micro-world of Cographs", Alecu, Lozin, and de Werra, IWOCA 2020, https://doi.org/10.1007/978-3-030-48966-3_3 recently caught my attention.

Cographs (https://en.wikipedia.org/wiki/Cograph) have a simple structure, but there's still an interesting hierarchy of subclasses of graphs within them restricting different parameters of graph complexity to be bounded.

A typical result: Every cograph with large h-index must contain a large complete graph, balanced bipartite graph, or forest of many high-degree stars.

@JordiGH @mjd Yes, I'm pretty sure the term "cograph" was introduced by as a shorthand for "complement-reducible graphs". You can see the two names side-by-side in Corneil et al 1981 https://core.ac.uk/download/pdf/82262422.pdf but apparently Lerchs was already calling them that in 1972.

An unrelated category-theoretic meaning of cographs was already used by Szabo in 1975 (https://doi.org/10.1080/00927877508822067) so confusion over this term is far from new.

@mjd @11011110 I don't speak computation/logic very well, but this

"Codata definitions are equations over types that produce final algebras, instead of the initial algebras we get for data definitions,"

makes it sound like this really is about reversing arrows. I just don't know what those arrows might be.

@JordiGH @mjd Recursive algorithms compute data (finite sets of values) from complex inputs by mapping them downward, to simpler inputs. Corecursive algorithms compute codata (infinite sequences) from simple inputs by mapping them upward to more complex values.

A standard example is Fibonacci numbers. Recursion: fib(n)=fib(n-1)+fib(n-2), a combination of simpler values. Corecursion: generate the whole Fibonacci sequence from the simple base case (1,1) by repeatedly replacing (a,b) by (b,a+b).

jsiehler@jsiehler@mathstodon.xyz@11011110 That's a well-written article, very inviting for the reader.

My first graph theory class gave us, as an exercise, the problem of proving that the family generated from vertices, disjoint union and complement is precisely the family of P4-free graphs. I remember working hard on that; I'm going to go out to the barn later and see if I can still find my write-up.