Sifat global dari kelas herediter?

Kelas struktur herediter (misalnya grafik) adalah yang ditutup di bawah substruktur yang diinduksi, atau setara, ditutup di bawah penghapusan verteks.

Kelas grafik yang mengecualikan minor memiliki properti bagus yang tidak bergantung pada minor yang dikecualikan tertentu. Martin Grohe menunjukkan bahwa untuk kelas grafik tidak termasuk minor ada algoritma polinom untuk isomorfisme, dan logika titik tetap dengan penghitungan menangkap waktu polinomial untuk kelas grafik ini. (Grohe, Fixed-Point Definability dan Waktu Polinomial pada Grafik dengan Anak-anak yang Dikecualikan , LICS, 2010.) Ini dapat dianggap sebagai properti "global".

Adakah properti "global" serupa yang dikenal untuk kelas herediter (baik grafik atau struktur yang lebih umum)?

Akan lebih baik melihat setiap jawaban fokus hanya pada satu properti tertentu.

Sifat turun-temurun sangat "kuat" dalam arti berikut.

Noga Alon dan Asaf Shapira menunjukkan bahwa untuk setiap properti herediter , jika grafik G membutuhkan lebih dari ϵ n 2 tepi untuk ditambahkan atau dihapus untuk memenuhi P , maka ada subgraf dalam G , dengan ukuran paling banyak f P ( ε ) , yang tidak memuaskan P . Di sini, fungsi f hanya tergantung pada properti P (dan bukan pada ukuran grafik G , misalnya). Erd telah membuat dugaan seperti itu hanya tentang sifat k- colorability.${\cal P}$$G$$\epsilon n^2$${\cal P}$$G$$f_{\cal P}(\epsilon)$${\cal P}$$f$${\cal P}$$G$$k$

Memang, Alon dan Shapira membuktikan fakta kuat berikut: diberikan , untuk setiap ϵ dalam ( 0 , 1 ) , ada N ( ϵ ) , h ( ϵ ) dan δ ( ϵ ) sedemikian rupa sehingga jika suatu graf G memiliki setidaknya N simpul dan kebutuhan setidaknya ε n 2 tepi ditambahkan / dihapus untuk memuaskan P , maka setidaknya δ sebagian kecil dari subgraphs diinduksi pada h P . Jadi, jika ${\cal P}$$\epsilon$$(0,1)$$N(\epsilon)$$h(\epsilon)$$\delta(\epsilon)$$G$$N$$\epsilon n^2$${\cal P}$$\delta$$h$ simpul, subgraph disebabkan melanggar${\cal P}$$\epsilon$ dan properti diperbaiki, untuk menguji apakah grafik input memenuhi P atau ${\cal P}$${\cal P}$$\epsilon$ jauh dari memuaskan , maka kita hanya perlu menanyakan tepi subgraf acak yang diinduksi secara acak dengan ukuran konstan dari grafik dan periksa apakah memenuhi properti atau tidak. Tester tersebut akan selalu menerima grafik memuaskan P dan akan menolak grafik ε -far dari memuaskan dengan probabilitas konstan. Selain itu, setiap properti yang dapat diuji satu sisi dalam hal ini adalah properti turun temurun! Lihat kertas karya Alon dan Shapira untuk detailnya.${\cal P}$${\cal P}$$\epsilon$

This may not be quite what you had in mind, but there are known restrictions on how many graphs on $n$ vertices there can be in a hereditary class of graphs. For example, there is no hereditary class of graphs that has between $2^{\Omega(n)}$ and $2^{o(n\log{n})}$ graphs on $n$ vertices.

Reference: E. Scheinerman, J. Zito, On the Size of Hereditary Classes of Graphs, Journal of Combinatorial Theory Series B

This is related to Travis's answer. In fact, it could be considered a stronger version.

A paper by Bollob\'as and Thomason (Combinatorica, 2000) shows that in Erd\H{o}s-R\'enyi random graphs $G_{n,p}$ (with $p$ some fixed constant), every hereditary property can be approximated by what they call a basic property. Basic almost means graphs whose vertex sets are unions of $r$ classes, $s$ of which span cliques and $r-s$ of which span independent sets, but not quite. This approximation is used to characterise the size of a largest $\mathcal{P}$-set as well as the $\mathcal{P}$-chromatic number of $G_{n,p}$, where $\mathcal{P}$ is some fixed hereditary property. If $p$ permitted to vary, the behaviour is not well-understood.

For more background to this and related work, there is a survey by Bollob\'as (Proceedings of the ICM 1998) which also gives an enticing conjecture along these lines but for hypergraphs.

I find the deep connection between hereditary properties and Szem\'eredi's Regularity Lemma very intriguing, as it was used both here and in the Alon and Shapira result.

Suresh's answer about the AKR conjecture got me thinking about the same conjecture for hereditary properties. I think (unless I've made a mistake) I can show that all non-trivial hereditary properties have (randomized and deterministic) decision tree complexity $\Theta(n^2)$, which settles the AKR conjecture for such properties (up to constants).

I tried to search the literature to see if this has been shown somewhere, but I couldn't find a reference. So either I couldn't find it but it exists, or the theorem is uninteresting, or I've made an error.

So, this is another example of a global property of all hereditary graph properties.

According to the Erdős–Hajnal conjecture, every hereditary family has the property that the graphs in it either have cliques or independent sets of polynomial size (that is, $\Omega(n^c)$ for some $c>0$ that depends on the family but not on the graph). This is in contrast to random graphs, where the largest clique and the largest independent set are both logarithmic.

This is the "reverse" direction, but the well known Aanderaa-Rosenberg-Karp conjecture applies to graph properties that are monotone upwards (i.e if G satisfies the property, then so does any graph on the same nodes whose edge set contains E(G)).