Det visades nyligen av Fakcharoenphol et al. [9] att godtyckliga finita mått kan inbäddas i fördelningar över trädmått med förvrängning O(log n). Det är också känt att denna gräns är snäv eftersom det finns expander grafer som inte kan inbäddas i fördelningar över träd med bättre än  och (log n) distorsion. Vi visar att samma lägre gräns håller för inbäddningar i distributioner över alla mindre exkluderade familjer. Med tanke på en familj av grafer F som utesluter mindre M där  och M = k, konstruerar vi uttryckligen en familj av grafer med trädbredd-(k + 1) som inte kan inbäddas i en distribution över F med bättre än  och (log n) distorsion. Även om dessa mindre exkluderade graffamiljer är mer uttrycksfulla än träd, ger de inte asymmetriskt bättre approximationer i allmänhet. En viktig följd av detta är att grafer av trädbredd-k inte kan inbäddas i fördelningar över grafer av trädbredd-(k-3) med förvrängning mindre än  och (log n). Vi utökar också ett resultat av Alon et al. [1] genom att visa att planara grafer för någon k inte kan inbäddas i fördelningar över trädbredd-k grafer med bättre än  och (log n) distorsion.
Carroll och Goel REF visar att det finns grafer med trädbredd t, som inte kan inbäddas i fördelningar över grafer med undantag för minderåriga i storlek t - 1, utan att ådra sig en förväntad sträcka av  och (log n).
Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}