Parameter grafik mana yang TIDAK terkonsentrasi pada grafik acak?

Telah diketahui secara umum bahwa banyak parameter grafik penting menunjukkan konsentrasi (kuat) pada grafik acak, setidaknya dalam beberapa kisaran probabilitas tepi. Beberapa contoh khas adalah jumlah kromatik, maksimum clique, set independen maksimum, maksimum pencocokan, jumlah dominasi, jumlah salinan dari Graf tetap, diameter, tingkat maksimum, jumlah pilihan (daftar mewarnai nomor), Lovasz $\theta$ -Jumlah, lebar pohon, dll.

Pertanyaan: Apa saja pengecualiannya, yaitu parameter grafik yang bermakna yang tidak terkonsentrasi pada grafik acak?

Edit. Definisi konsentrasi yang mungkin adalah ini:

$X_n$$n$$\epsilon>0$

$$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$$ $X_n$$p$ $$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$$ yang merupakan interval sesingkat mungkin (karena derajatnya bilangan bulat, tetapi nilai yang diharapkan mungkin tidak).

Catatan: Seseorang dapat membuat pengecualian buatan dari aturan konsentrasi. Sebagai contoh, misalkan , jika grafik memiliki jumlah sisi ganjil, dan 0 sebaliknya. Ini jelas tidak terkonsentrasi, tetapi saya tidak akan menganggapnya sebagai parameter yang bermakna .$X_n=n$

Banyak parameter komponen terhubung terbesar tidak terkonsentrasi untuk $G(n,p)$ jika $p=1/n$ dan lebih umum jika $p$ berada di jendela kritis. Contohnya adalah diameter dan ukuran komponen terbesar, ukuran komponen terbesar kedua, jumlah daun yang dimiliki komponen, dll.

Lihat misalnya

Aldous, David. "Kunjungan Brown, grafik acak kritis dan penggandaan multiplikasi." The Annals of Probability (1997): 812-854.

Nachmias, Asaf, dan Yuval Peres. "Grafik acak kritis: diameter dan waktu pencampuran." The Annals of Probability 36, no. 4 (2008): 1267-1286.

Addario-Berry, Louigi, Nicolas Broutin, dan Christina Goldschmidt. "Batas kontinum grafik acak kritis." Teori Probabilitas dan Bidang Terkait 152, no. 3-4 (2012): 367-406.

Kegagalan berkonsentrasi terjadi untuk beberapa properti penghitungan ( ), dan mungkin bagi banyak dari mereka.$\#\mathsf{P}$

Contoh sederhana adalah jumlah subgraf spanning ( ). Jumlah tepi dari grafik acak berfluktuasi oleh ± Θ ( n ) sehingga jumlah subgraf spanning berfluktuasi oleh faktor 2 Θ ( n ) , jauh dari faktor ( 1 + ϵ ) yang Anda gunakan dalam definisi konsentrasi Anda. .$2^m$$\pm \Theta(n)$$2^{\Theta(n)}$$(1+\epsilon)$

Untuk menunjukkan bahwa ini bukan contoh yang terisolasi, inilah argumen (tidak sepenuhnya teliti tetapi mungkin dapat dibuat teliti) untuk mengapa kegagalan berkonsentrasi juga harus benar dengan jumlah siklus Hamilton. Nilai yang diharapkan dari angka ini jelas : masing-masing ( n - 1 ) ! / 2 urutan siklik dari simpul memiliki 1 / 2 n kesempatan benar-benar menjadi siklus Hamiltonian. Dengan argumen yang sama, jumlah perubahan yang diharapkan untuk nomor ini disebabkan oleh memperkenalkan tepi baru adalah $(n-1)!/2^{n+1}$$(n-1)!/2$$1/2^n$ , lebih kecil dengan faktor linear. Jika jumlah siklus Hamiltonian sangat terkonsentrasi, sebagian besar membalik tepi akan menyebabkan sejumlah perubahan pada jumlah ini yang mendekati nilai yang diharapkan. Tetapi kemudianfluktuasi Θ ( n ) dalam jumlah tepi akan menyebabkan fluktuasi dalam jumlah siklus Hamilton yang sebanding dengan nilai yang diharapkan, bertentangan dengan asumsi konsentrasi yang kuat.$(n-2)!/2^{n-1}$$\Theta(n)$

Kandidat lain yang masuk akal untuk gagal berkonsentrasi meliputi jumlah pewarnaan (partisi simpul ke dalam set independen), jumlah korek api atau korek sempurna, atau jumlah pohon merentang.