Seberapa besar varian dari treewidth dari grafik acak dalam G (n, p)?

23

Saya mencoba untuk menemukan seberapa dekat dan sebenarnya, ketika dan adalah konstanta yang tidak bergantung pada n (jadi ). Perkiraan saya adalah whp, tetapi saya belum dapat membuktikannya.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n )tw(G)E[tw(G)]G∈G(n,p=c/n)c>1E[tw(G)]=Θ(n)tw(G)≤E[tw(G)]+o(n)

graph-theory co.combinatorics treewidth random-graphs Kostas
sumber
1
Apa motivasi untuk pertanyaan itu? (yaitu mengapa tertarik pada masalah ini?)
Kaveh
6
Yah ... saya bertanya-tanya berapa banyak pengetahuan tentang beberapa tepi dapat mempengaruhi estimasi treewidth (pengetahuan tentang keberadaan masing-masing tepi dapat mempengaruhi treewidth oleh paling banyak satu), dan itu membawa saya ke pertanyaan ini (yang jauh lebih menarik)
Kostas
2
Secara khusus, ini memiliki implikasi untuk batas atas penghitungan model dalam rezim yang memuaskan untuk instance acak SAT (dan kuantum-SAT), dalam fase grafik Erdos-Renyi acak yang memiliki komponen terhubung yang besar. Sejauh kita peduli tentang SAT acak sebagai topik ilmu komputer teoretis, dan juga pendekatan yang melibatkan treewidth untuk membatasi kompleksitas #SAT dan masalah serupa, pertanyaan ini bermotivasi baik.
Niel de Beaudrap

Jawaban:

13

Anda tidak perlu menghitung varians untuk membuktikan konsentrasi tw (G (n, p)) di sekitar ekspektasinya. Jika dua grafik G 'dan G berbeda oleh satu titik maka treewidth mereka berbeda paling banyak satu. Anda dapat menggunakan metode standar, ketidaksetaraan Hoeffding-Azuma yang diterapkan pada Martingale eksposur sudut untuk menunjukkan, misalnya,

P(|tw(G(n,p))−Etw(G(n,p))|>t)≤3e−t2/(2n) ,

jadi probabilitas di atas cenderung ke 0, jika, katakanlah .t=n0.51

Metode pertama kali diterapkan untuk membuktikan konsentrasi untuk bilangan kromatis . Lihat B. Bollobás, Grafik acak. Springer New York, 1998, halaman 298.G(n,p)

Valentas
sumber