Ramsey theory আর extremal combinatorics-এর পরিচয়

১ · বিশৃঙ্খলায় শৃঙ্খলা — Ramsey-র প্রশ্ন

পর্ব ৩২ “Pigeonhole principle — সহজ থেকে generalized”-এ বাজারঘরের ছয়জন রাইডারের গল্প দেখেছেন: প্রতি দুজন হয় সহকর্মী, নয়তো অপরিচিত; ছয়জনে সবসময় তিনজন পরস্পর সহকর্মী বা তিনজন পরস্পর অপরিচিত। গ্রাফের ভাষায়, complete graph K₆-এর প্রতিটি edge লাল (সহকর্মী) বা নীল (অপরিচিত) করলে একটি একরঙা ত্রিভুজ থাকবেই। এই পর্বে সেই প্রশ্নকে সাধারণ করি।

একই কথা একটিমাত্র গ্রাফ দিয়ে বলা যায়: লাল edge-গুলোকে গ্রাফ G ধরুন, তাহলে নীল edge হলো G-এর complement. লাল K_s মানে G-তে s আকারের একটি clique (পরস্পর যুক্ত vertex-এর দল), আর নীল K_t মানে t আকারের একটি independent set. তাই R(s, t) হলো সবচেয়ে ছোট N, যাতে N-vertex-এর প্রতিটি গ্রাফে s-clique বা t-independent set থাকে। সংজ্ঞা থেকে সরাসরি দুটি তথ্য:

• প্রতিসাম্য: R(s, t) = R(t, s), কারণ দুই রং অদলবদল করলেই হয়।
• প্রান্তিক মান: R(2, t) = t. K_t-এ একটিও লাল edge থাকলে সেটি লাল K₂, না থাকলে পুরোটা নীল K_t; আর K_t−1-কে পুরো নীল করলে দুটোই এড়ানো যায়।

একটি Ramsey সংখ্যা জানতে দুই দিকের প্রমাণ লাগে। ওপরের সীমা R ≤ N মানে K_N-এর প্রতিটি রঙে নকশাটি আছে। নিচের সীমা R > N − 1 মানে K_N−1-এর একটি “ভালো” রং দেখানো, যাতে নকশাটি নেই। পর্ব ৩২-এ R(3, 3) ≤ 6 প্রমাণ হয়েছে pigeonhole দিয়ে, আর K₅-এর পঞ্চভুজ-তারকা রং (বাহু লাল, কর্ণ নীল) দেখিয়েছে R(3, 3) > 5. দুই মিলে R(3, 3) = 6. বড় s, t-তে এই দুই দিকের ফাঁক কতটা কঠিন হতে পারে, সেটাই এই পর্বের প্রথম অর্ধেকের গল্প।

২ · Ramsey-র উপপাদ্য — দুটি ওপরের সীমা

প্রথম প্রশ্ন: R(s, t) কি সবসময় সসীম? অর্থাৎ যেকোনো s, t-এর জন্য কি এমন N আছে? উত্তর হ্যাঁ, আর প্রমাণটি একই সঙ্গে একটি সংখ্যাগত সীমাও দেয়।

প্রমাণ (s + t-এর ওপর induction; ভিত্তি R(2, t) = t আর R(s, 2) = s সসীম):

1. N = R(s − 1, t) + R(s, t − 1) নিন (induction-এর অনুমানে দুটিই সসীম), আর K_N-এর যেকোনো লাল-নীল রং ধরুন। — সেটআপ
2. একটি vertex v বাছুন। v থেকে N − 1টি edge. যাদের সঙ্গে v-এর edge লাল, তারা সেট A; নীল হলে সেট B. তাহলে |A| + |B| = N − 1. — ভাগ
3. যদি |A| ≤ R(s − 1, t) − 1 আর |B| ≤ R(s, t − 1) − 1 হতো, তবে |A| + |B| ≤ N − 2, বিরোধ। তাই |A| ≥ R(s − 1, t) অথবা |B| ≥ R(s, t − 1). — pigeonhole
4. ক্ষেত্র |A| ≥ R(s − 1, t): A-এর ভেতরের রঙে হয় লাল K_s−1, নয়তো নীল K_t. নীল K_t হলে কাজ শেষ। লাল K_s−1 হলে তার প্রতিটি vertex v-এর সঙ্গে লাল edge-এ যুক্ত, তাই v যোগ করলে লাল K_s. — R(s − 1, t)-এর সংজ্ঞা
5. ক্ষেত্র |B| ≥ R(s, t − 1): একই যুক্তিতে লাল K_s, নয়তো B-এর নীল K_t−1 আর v মিলে নীল K_t. ∎ — প্রতিসাম্য

নিচের stepper s = t = 3-এ একটি নির্দিষ্ট রঙে প্রমাণটি চালায়। এখানে R(2, 3) + R(3, 2) = 3 + 3 = 6, অর্থাৎ পর্ব ৩২-এর ফলই নতুন করে আসে।

1N = R(2,3) + R(3,2) = 62v = 0: 5টি edge, |A| + |B| = 53লাল: 1, 2, 3 · নীল: 4, 54|A| = 3 ≥ R(2,3) = 352–3 লাল ⇒ লাল {0, 2, 3}6নইলে 1, 2, 3 নীল K₃

এখন recursive অসমতাকে একটি বদ্ধ সূত্রে বাঁধি। এখানে binomial coefficient C(n, k) আর Pascal-এর অভেদ C(n − 1, k − 1) + C(n − 1, k) = C(n, k) লাগবে (পর্ব ৩৪)।

1. ভিত্তি (s = 2 বা t = 2): C(t, 1) = t = R(2, t), আর C(s, s − 1) = s = R(s, 2). — প্রান্তিক মান
2. ধাপ: s, t ≥ 3 আর s + t-এর ছোট সব জোড়ায় দাবি সত্য ধরুন। উপপাদ্য ২.১ আর induction-এর অনুমান থেকে R(s, t) ≤ C(s + t − 3, s − 2) + C(s + t − 3, s − 1). — strong induction
3. Pascal-এর অভেদে ডান দিক = C(s + t − 2, s − 1). — পর্ব ৩৪
4. s = t = k-এ C(2k − 2, k − 1) হলো (1 + 1)^2k−2 = 4^k−1-এর বিস্তারের একটি পদ, আর k ≥ 2-এ অন্য পদও আছে, তাই কঠোরভাবে ছোট। ∎ — binomial theorem

এই সীমা কতটা ভালো? R(3, 4)-এ দুটিই দেয় 10. একটি সূক্ষ্ম parity যুক্তি একে 9-এ নামায়।

1. a = R(s − 1, t), b = R(s, t − 1), N = a + b − 1 (বিজোড়)। বিরোধের জন্য ধরুন K_N-এর এমন রং আছে যাতে লাল K_s বা নীল K_t নেই। — বিরোধ
2. উপপাদ্য ২.১-এর ধাপ ৪–৫ অনুযায়ী প্রতিটি vertex-এর লাল degree ≤ a − 1 আর নীল degree ≤ b − 1. দুটির যোগ N − 1 = a + b − 2, তাই প্রতিটি vertex-এর লাল degree ঠিক a − 1. — সমতা জোর করে
3. a জোড়, তাই a − 1 বিজোড়। বিজোড় সংখ্যক (N) vertex-এর প্রতিটির লাল degree বিজোড় হলে লাল degree-র যোগ বিজোড়। কিন্তু handshake lemma অনুযায়ী এই যোগ লাল edge-সংখ্যার দ্বিগুণ, জোড়। বিরোধ। ∎ — পর্ব ৫৭

R(2, 4) = 4 আর R(3, 3) = 6 দুটিই জোড়, তাই R(3, 4) ≤ 9. পরের অংশে K₈-এর একটি ভালো রং দেখাবে R(3, 4) > 8, অর্থাৎ R(3, 4) = 9. তারপর R(4, 4) ≤ R(3, 4) + R(4, 3) = 18, আর এটিও হুবহু সত্য মান।

৩ · নিচের সীমা — নির্মাণ, এলোমেলো রং আর জানা মান

নিচের সীমার জন্য একটি “ভালো” রং দেখাতে হয়। ছোট ক্ষেত্রে সবচেয়ে সফল কৌশল হলো circulant রং: vertex 0, 1, …, n − 1 বৃত্তে বসান, আর edge {i, j}-এর রং ঠিক করুন শুধু পার্থক্য (j − i) mod n দিয়ে। তাহলে বৃত্ত ঘোরালে রং বদলায় না, আর একটি vertex-এর চারপাশ যাচাই করলেই প্রায় সব বোঝা যায়। K₅-এর পঞ্চভুজ রংটিও তাই: পার্থক্য ±1 লাল।

কেন কাজ করে? লাল ত্রিভুজ i, j, k-তে j − i আর k − j দুটি লাল পার্থক্য, আর তাদের যোগ k − i-কেও লাল হতে হবে। কিন্তু {1, 4, 7}-এর যেকোনো দুটির যোগ mod 8-এ 2, 5, 0, 3 বা 6, কখনো 1, 4 বা 7 নয়। নীল K₄-এর জন্য চারটি vertex লাগবে যাদের কোনো দুটি পাশাপাশি বা বিপরীত নয়; অষ্টভুজে পাশাপাশি নয় এমন চারটি vertex মানে প্রতি দ্বিতীয় vertex, যেমন 0, 2, 4, 6, কিন্তু 0 আর 4 বিপরীত। হাতের এই যুক্তি নিচের ব্লক সরাসরি গুনে মেলায়, আর একই কৌশলে আরও দুটি বিখ্যাত রং পরীক্ষা করে: K₁₃-এ পার্থক্য {1, 5, 8, 12} লাল (R(3, 5) > 13), আর K₁₇-এ mod 17-এর বর্গ সংখ্যাগুলো লাল, যাকে Paley graph বলে (R(4, 4) > 17).

from itertools import combinations

def circulant(n, diffs):
    """Red edge {i, j} when (j - i) mod n is in diffs; every other edge is blue."""
    return {frozenset((i, j)) for i, j in combinations(range(n), 2)
            if (j - i) % n in diffs}

def biggest(n, red, colour):
    """Largest set of vertices whose every pair has the given colour."""
    best = 1
    for k in range(2, n + 1):
        found = False
        for S in combinations(range(n), k):
            if all((frozenset(p) in red) == (colour == "red")
                   for p in combinations(S, 2)):
                found = True
                break
        if not found:
            break
        best = k
    return best

cases = [("R(3,4) > 8", 8, {1, 4, 7}),
         ("R(3,5) > 13", 13, {1, 5, 8, 12}),
         ("R(4,4) > 17", 17, {1, 2, 4, 8, 9, 13, 15, 16})]
for name, n, diffs in cases:
    red = circulant(n, diffs)
    r, b = biggest(n, red, "red"), biggest(n, red, "blue")
    print(f"{name}: K{n}, {len(red)} red + {n*(n-1)//2 - len(red)} blue edges;"
          f" largest red clique {r}, blue clique {b}")

# R(4,4) uses the quadratic residues mod 17 (Paley graph)
print("squares mod 17:", sorted({x * x % 17 for x in range(1, 17)}))

R(3,4) > 8: K8, 12 red + 16 blue edges; largest red clique 2, blue clique 3
R(3,5) > 13: K13, 26 red + 52 blue edges; largest red clique 2, blue clique 4
R(4,4) > 17: K17, 68 red + 68 blue edges; largest red clique 3, blue clique 3
squares mod 17: [1, 2, 4, 8, 9, 13, 15, 16]

বড় k-তে হাতে বানানো রং আর কাজ করে না। পর্ব ৪৩ “Probabilistic method আর randomized algorithm”-এ Erdős-এর ১৯৪৭ সালের probabilistic method দেখেছেন: এলোমেলো রঙে একরঙা K_k-এর প্রত্যাশিত সংখ্যা 1-এর কম হলে ভালো রং আছে, ফলে R(k, k) > 2^k/2. সেই প্রমাণ এখানে আর দোহরাই না। দুই সীমা পাশাপাশি রাখলে

2^k/2 < R(k, k) < 4^k−1 (k ≥ 3),

অর্থাৎ বৃদ্ধি সূচকীয়, কিন্তু ভিত্তি √2 আর 4-এর মাঝে কোথায়, তা আজও অজানা (ভাবনার প্রশ্ন ৩)। জানা ছোট মানগুলো নিচে; এগুলো Stanisław Radziszowski-এর নিয়মিত হালনাগাদ হওয়া জরিপ “Small Ramsey Numbers” (Electronic Journal of Combinatorics) অনুযায়ী উল্লেখ করা হয়।

শেষ সারি দেখায় উপপাদ্যটি যেকোনো r রঙে চলে: R(s₁, …, s_r) সসীম, প্রমাণ §২-এর মতোই। এমনকি গ্রাফের বদলে k-উপাদানের subset-কে রং করলেও (hypergraph Ramsey) সসীমতা থাকে; Frank Ramsey-র ১৯৩০ সালে প্রকাশিত মূল উপপাদ্য ছিল এই সাধারণ রূপে (ভাবনার প্রশ্ন ১)।

৪ · সংখ্যায় Ramsey — Schur, van der Waerden আর Erdős–Szekeres

বাজারঘর ১ থেকে n নম্বরের কুপনকে দুই ক্যাম্পেইনে ভাগ করতে চায়, লাল আর নীল। শর্ত: একই ক্যাম্পেইনের দুটি কুপন নম্বরের যোগফল (একই নম্বর দুবার নিলেও) সেই ক্যাম্পেইনের কোনো নম্বর হবে না, যাতে “দুটি মিলিয়ে তৃতীয়টি” ধরনের প্রতারণা না হয়। n কত পর্যন্ত এটি সম্ভব?

1. R_r = R(3, 3, …, 3) (r রং) নিন, যা সসীম (§৩)। N = R_r − 1 ধরুন, আর {1, …, N}-এর যেকোনো r-রং χ নিন। — সেটআপ
2. vertex 0, 1, …, N নিয়ে K_N+1 বানান; edge {i, j}-এর রং χ(|i − j|). |i − j| সবসময় 1 থেকে N-এর মধ্যে, তাই রং সংজ্ঞায়িত। — পার্থক্যে রং
3. K_N+1 = K_Rr, তাই একটি একরঙা ত্রিভুজ i < j < k আছে। — Ramsey
4. x = j − i, y = k − j, z = k − i নিন। তিনটি একই রঙের, আর x + y = z. ∎ — বীজগণিত

দুই রঙে R(3, 3) = 6, তাই N = 5: 1..5-এর যেকোনো দুই রঙে একরঙা x + y = z আছে। আর 1..4-এ রং {1, 4} লাল, {2, 3} নীল সফল (1 + 1 = 2 আর 2 + 2 = 4 রং পাল্টায়, 1 + 3 = 4 রং মেলে না)। তাই বাজারঘর বড়জোর ৪টি কুপন পর্যন্ত যেতে পারে; সবচেয়ে বড় এমন n-কে Schur number S(r) বলে, আর S(2) = 4. তিন রঙে S(3) = 13 জানা।

একই ধাঁচের আরেকটি বিখ্যাত ফল arithmetic progression (সমান্তর ধারা) নিয়ে। দৈর্ঘ্য k-এর সমান্তর ধারা মানে a, a + d, …, a + (k − 1)d, যেখানে d ≥ 1.

সাধারণ উপপাদ্যের প্রমাণ (রঙের “color focusing” নামের একটি দ্বৈত induction) দীর্ঘ, এখানে বাদ রাখছি; প্রমাণটি পাওয়া যায় Graham, Rothschild আর Spencer-এর বই “Ramsey Theory”-তে। কিন্তু W(2, 3) = 9-এর দাবি যাচাই করা সহজ: 1..8-এর সব 2⁸ = 256টি রং আর 1..9-এর 512টি রং গুনুন। নিচের ব্লক তা করে, আর Schur-এর S(2) = 4-ও মেলায়।

from itertools import product

def has_mono_ap(col):                 # col[i] = colour of i+1
    n = len(col)
    for a in range(n):
        for d in range(1, n):
            if a + 2 * d >= n:
                break
            if col[a] == col[a + d] == col[a + 2 * d]:
                return True
    return False

def has_mono_schur(col):              # x + y = z, x = y allowed
    n = len(col)
    return any(col[x - 1] == col[y - 1] == col[x + y - 1]
               for x in range(1, n + 1) for y in range(x, n + 1) if x + y <= n)

for n in (8, 9):
    good = [c for c in product("RB", repeat=n) if not has_mono_ap(c)]
    print(f"1..{n}: {2**n} colourings, {len(good)} with no one-colour 3-AP")
    if good:
        print("   e.g.", "".join(good[0]))
for n in (4, 5):
    good = [c for c in product("RB", repeat=n) if not has_mono_schur(c)]
    print(f"Schur 1..{n}: {len(good)} sum-free colourings", "".join(good[0]) if good else "")

1..8: 256 colourings, 6 with no one-colour 3-AP
   e.g. RRBBRRBB
1..9: 512 colourings, 0 with no one-colour 3-AP
Schur 1..4: 2 sum-free colourings RBBR
Schur 1..5: 0 sum-free colourings 

Erdős–Szekeres আবার, এবার Ramsey-র চোখে

পর্ব ৩২-এ Erdős–Szekeres theorem প্রমাণ করেছেন: (r − 1)(s − 1) + 1টি ভিন্ন সংখ্যার যেকোনো ক্রমে দৈর্ঘ্য r-এর বর্ধমান বা দৈর্ঘ্য s-এর হ্রাসমান subsequence আছে। Ramsey দিয়ে দুর্বলতর রূপটি এক লাইনে আসে। ক্রম a₁, …, a_N-এ i < j জোড়াকে লাল রাঙান যদি a_i < a_j, নইলে নীল। একটি লাল K_r-এর সব জোড়া বর্ধমান, অর্থাৎ সেটি দৈর্ঘ্য r-এর বর্ধমান subsequence; নীল K_s হ্রাসমান। তাই N ≥ R(r, s) যথেষ্ট। r = s = 4-এ Ramsey চায় 18টি পদ, Erdős–Szekeres মাত্র 10. শিক্ষা: Ramsey সাধারণ নিশ্চয়তা দেয়, কিন্তু সমস্যার বিশেষ কাঠামো (এখানে “বর্ধমান” সম্পর্কের transitivity) কাজে লাগালে সীমা অনেক কড়া হয়।

৫ · Extremal graph theory — Mantel-এর উপপাদ্য

Ramsey জিজ্ঞেস করে: গ্রাফ বা তার complement-এ নকশা কখন অনিবার্য? Extremal graph theory জিজ্ঞেস করে একটু ভিন্ন প্রশ্ন: একটি নিষিদ্ধ নকশা এড়িয়ে একটি গ্রাফে সর্বোচ্চ কয়টি edge রাখা যায়? বাজারঘরের ভাষায়: n-টি জেলা-গুদামের মধ্যে সরাসরি রুট বসাতে চাই, কিন্তু নিরাপত্তা-নিয়মে কোনো তিনটি গুদাম পরস্পর সরাসরি যুক্ত থাকতে পারবে না। সর্বোচ্চ কয়টি রুট?

একটি স্বাভাবিক উত্তর: গুদামগুলো দুই দলে ভাগ করুন, আর শুধু দুই দলের মধ্যে রুট দিন। এটি complete bipartite graph K_a,b, যার a · b-টি edge, আর কোনো ত্রিভুজ নেই (ত্রিভুজের তিন vertex-এর দুটি একই দলে পড়বে)। a + b = n হলে a · b সবচেয়ে বড় যখন দুই দল সমান বা প্রায় সমান: ⌊n/2⌋ · ⌈n/2⌉ = ⌊n²/4⌋. এর চেয়ে ভালো কি সম্ভব?

প্রথম প্রমাণ (degree গুনে): d(v) মানে vertex v-এর degree.

1. যেকোনো edge uv নিন। u আর v-এর কোনো সাধারণ প্রতিবেশী w থাকলে u, v, w একটি ত্রিভুজ হতো। তাই N(u) আর N(v) disjoint, আর d(u) + d(v) ≤ n. — triangle-free
2. এই অসমতা m-টি edge-এ যোগ করুন: ∑_{uv ∈ E} (d(u) + d(v)) ≤ n · m. — যোগ
3. বাম দিকে প্রতিটি vertex v ঠিক d(v)-টি edge-এ আছে, আর প্রতিবার d(v) যোগ করে; তাই বাম দিক = ∑_v d(v)². — double counting
4. Cauchy–Schwarz অসমতা (বা “বর্গের গড় ≥ গড়ের বর্গ”): (∑ d(v))² ≤ n · ∑ d(v)². Handshake lemma-য় ∑ d(v) = 2m. — CS আর পর্ব ৫৭
5. মিলিয়ে: 4m² ≤ n · ∑ d(v)² ≤ n · n · m, তাই m ≤ n²/4, আর m পূর্ণসংখ্যা বলে m ≤ ⌊n²/4⌋. ∎ — বীজগণিত

নিচের stepper একটি ৬-vertex-এর triangle-free গ্রাফে প্রতিটি ধাপের সংখ্যা দেখায়: ৫-চক্র 1–2–3–4–5–1, আর বাড়তি vertex 6, যা 1 আর 3-এর সঙ্গে যুক্ত। লক্ষ করুন গ্রাফটি bipartite নয় (বিজোড় চক্র আছে), তবু প্রমাণ চলে।

1n = 6, m = 7, ত্রিভুজ নেই2d = 3,2,3,2,2,2 · ∑d = 143প্রতি edge: N(u) ∩ N(v) = ∅4d(u) + d(v) ≤ 65∑d² = 34 ≤ n·m = 426(∑d)² = 196 ≤ 6·34 = 204

দ্বিতীয় প্রমাণ (induction): n = 1, 2-এ সত্য (0 ≤ 0, 1 ≤ 1). n ≥ 3 আর n − 2-এর জন্য সত্য ধরুন। G-তে edge না থাকলে কিছু প্রমাণের নেই; নইলে একটি edge uv নিন।

1. প্রথম প্রমাণের ধাপ ১: d(u) + d(v) ≤ n. — triangle-free
2. u আর v মুছে দিলে মোছা edge-সংখ্যা d(u) + d(v) − 1 (uv দুবার গোনা হয়েছে), যা ≤ n − 1. — গণনা
3. বাকি G′-এর n − 2টি vertex, আর সেটিও triangle-free; induction-এর অনুমানে তার edge ≤ ⌊(n − 2)²/4⌋ = ⌊n²/4⌋ − n + 1. — (n − 2)²/4 = n²/4 − n + 1
4. তাই m ≤ (⌊n²/4⌋ − n + 1) + (n − 1) = ⌊n²/4⌋. ∎ — যোগ

নিচের ব্লক n ≤ 7-এ সব গ্রাফের মধ্যে সর্বোচ্চ edge-এর triangle-free গ্রাফ খোঁজে (branch and bound: edge একে একে যোগ বা বাদ, আর বাকি সব যোগ করেও রেকর্ড ভাঙা অসম্ভব হলে সেই শাখা ছেঁটে ফেলা), আর ⌊n²/4⌋-এর সঙ্গে মেলায়। শেষে K₄-হীন গ্রাফেও একই খোঁজ চালায়, যা §৬-এর Turán-এর উপপাদ্যের সঙ্গে মিলবে।

from itertools import combinations

def max_edges(n, r):
    """Most edges of a graph on n vertices with no K_r (branch and bound)."""
    pairs = list(combinations(range(n), 2))
    adj = [set() for _ in range(n)]
    best = [0, None]
    def closes_kr(u, v):              # would edge uv finish a K_r?
        common = adj[u] & adj[v]
        return any(all(b in adj[a] for a, b in combinations(S, 2))
                   for S in combinations(sorted(common), r - 2))
    def go(i, m):
        if m + len(pairs) - i <= best[0]:
            return                    # cannot beat the best: prune
        if i == len(pairs):
            best[0], best[1] = m, [sorted(a) for a in adj]
            return
        u, v = pairs[i]
        if not closes_kr(u, v):
            adj[u].add(v); adj[v].add(u)
            go(i + 1, m + 1)
            adj[u].discard(v); adj[v].discard(u)
        go(i + 1, m)
    go(0, 0)
    return best

for n in range(2, 8):
    m, g = max_edges(n, 3)
    print(f"n={n}: triangle-free max {m:2}, floor(n^2/4) = {n*n//4:2},"
          f" degrees {sorted(len(a) for a in g)}")
def turan(n, k):                      # edges of T(n, k): k nearly equal parts
    parts = [n // k + (i < n % k) for i in range(k)]
    return (n * n - sum(p * p for p in parts)) // 2
for n in (5, 6, 7):
    print(f"n={n}: K4-free max {max_edges(n, 4)[0]}, Turan T(n,3) {turan(n, 3)}")

n=2: triangle-free max  1, floor(n^2/4) =  1, degrees [1, 1]
n=3: triangle-free max  2, floor(n^2/4) =  2, degrees [1, 1, 2]
n=4: triangle-free max  4, floor(n^2/4) =  4, degrees [2, 2, 2, 2]
n=5: triangle-free max  6, floor(n^2/4) =  6, degrees [2, 2, 2, 3, 3]
n=6: triangle-free max  9, floor(n^2/4) =  9, degrees [3, 3, 3, 3, 3, 3]
n=7: triangle-free max 12, floor(n^2/4) = 12, degrees [3, 3, 3, 3, 4, 4, 4]
n=5: K4-free max 8, Turan T(n,3) 8
n=6: K4-free max 12, Turan T(n,3) 12
n=7: K4-free max 16, Turan T(n,3) 16

৬ · Turán-এর উপপাদ্য — K_r+1 এড়ালে সেরা গ্রাফ

ত্রিভুজের বদলে K₄, K₅ নিষিদ্ধ হলে? Mantel-এর গঠন স্বাভাবিকভাবে বাড়ে: দুই দলের বদলে r দল।

T(n, r)-এ কোনো K_r+1 নেই: r + 1টি vertex-এর দুটি একই দলে পড়বে (pigeonhole), আর তারা যুক্ত নয়। দলের আকার n₁, …, n_r হলে edge-সংখ্যা (n² − ∑ n_i²)/2, কারণ মোট n² ক্রমজোড়া থেকে একই দলের জোড়া বাদ দিয়ে দুই দিকের গণনা ২ দিয়ে ভাগ করতে হয়। যেমন T(10, 3)-এ দল 4, 3, 3: (100 − 16 − 9 − 9)/2 = 33টি edge.

r = 2-এ এটিই Mantel. সাধারণ প্রমাণ এখানে দিচ্ছি না; Aigner আর Ziegler-এর “Proofs from THE BOOK”-এ পাঁচটি আলাদা প্রমাণ আছে, আর তার একটি Mantel-এর induction প্রমাণেরই বিস্তার (একটি বৃহত্তম clique সরিয়ে induction). শেষ অসমতাটি আসে কারণ ∑ n_i² ≥ n²/r (আবার Cauchy–Schwarz). ওপরের ব্লকে n = 5, 6, 7-এ K₄-হীন সর্বোচ্চ 8, 12, 16, ঠিক T(n, 3)-এর মান।

৭ · Sperner-এর উপপাদ্য আর LYM অসমতা

এবার গ্রাফ ছেড়ে সেটের পরিবার। বাজারঘর ৪ ধরনের পণ্য (চাল, ডাল, তেল, চিনি; নাম 1, 2, 3, 4) থেকে কম্বো অফার বানায়; প্রতিটি অফার পণ্যের একটি subset. নিয়ম: কোনো অফার আরেকটির ভেতরে থাকতে পারবে না, নইলে ক্রেতা বড় অফারের পণ্য থেকে ছোট অফারটি নিজেই বানিয়ে নিয়ম ফাঁকি দিতে পারে। সর্বোচ্চ কয়টি অফার সম্ভব?

পর্ব ৫৬ “Partial order, Hasse diagram, topological sort আর lattice”-এর ভাষায়: power set P([n]) (এখানে [n] = {1, …, n}) ⊆ সম্পর্কে একটি poset, আর প্রশ্নটি হলো এর বৃহত্তম antichain, অর্থাৎ পরস্পর অতুলনীয় subset-এর পরিবার। একটি স্বাভাবিক উত্তর: একই আকারের সব subset (একটি “স্তর”), কারণ একই আকারের দুটি আলাদা সেট একে অপরের ভেতরে থাকতে পারে না। সবচেয়ে বড় স্তর মাঝেরটি।

প্রমাণের চাবি একটি গণনা। P([n])-এর একটি maximal chain হলো ∅ ⊂ {a₁} ⊂ {a₁, a₂} ⊂ ⋯ ⊂ [n], প্রতিবার একটি করে উপাদান যোগ; ছবিতে নিচ থেকে শীর্ষে একটি পথ। উপাদান যোগের ক্রম একটি permutation, তাই maximal chain ঠিক n!-টি। আকার k-এর একটি সেট A কয়টি chain-এ আছে? প্রথমে A-এর k উপাদান যেকোনো ক্রমে (k! উপায়), তারপর বাকি n − k উপাদান ((n − k)! উপায়): k!(n − k)!-টি।

1. প্রতিটি A ∈ F ঠিক |A|!(n − |A|)!-টি maximal chain-এ আছে। — ওপরের গণনা
2. একটি chain-এর যেকোনো দুটি সেট তুলনীয়, আর F-এর কোনো দুটি সেট তুলনীয় নয়; তাই প্রতিটি chain F-এর বড়জোর একটি সেট ধরে। — antichain-এর সংজ্ঞা
3. অতএব F-এর সেটগুলোর chain-সংখ্যার যোগ মোট chain-সংখ্যা ছাড়ায় না: ∑ |A|!(n − |A|)! ≤ n!. — disjoint গণনা
4. দুই দিক n! দিয়ে ভাগ করলে ∑ 1/C(n, |A|) ≤ 1. ∎ — C(n, k) = n!/(k!(n − k)!)

Sperner-এর প্রমাণ: C(n, k) সবচেয়ে বড় k = ⌊n/2⌋-এ, তাই প্রতিটি পদ 1/C(n, |A|) ≥ 1/C(n, ⌊n/2⌋). LYM থেকে |F| / C(n, ⌊n/2⌋) ≤ 1. ∎ বাজারঘরের উত্তর: ৪টি পণ্যে বড়জোর C(4, 2) = 6টি অফার, যেমন সব দুই-পণ্যের কম্বো। প্রমাণের নামটি তিনজনের আদ্যক্ষর: Lubell (১৯৬৬), Yamamoto (১৯৫৪) আর Meshalkin (১৯৬৩), যাঁরা স্বাধীনভাবে এটি পান বলে উল্লেখ করা হয়।

1maximal chain: 4! = 242|A| = 2: 2!·2! = 4টি chain3|A| = 3: 3!·1! = 6টি chain4কোনো chain-এ F-এর দুটি নেই54 + 4 + 4 + 6 = 18 ≤ 2463/6 + 1/4 = 3/4 ≤ 1

নিচের ব্লক n ≤ 5-এ P([n])-এর সব antichain তালিকা করে, বৃহত্তমটির আকার C(n, ⌊n/2⌋)-এর সঙ্গে মেলায়, আর সর্বোচ্চ LYM-যোগ নির্ভুল ভগ্নাংশে (fractions) বের করে। Antichain-এর সংখ্যাগুলো Dedekind সংখ্যা, যা পর্ব ৬৯-এ monotone Boolean function গোনার সময় এসেছে।

from fractions import Fraction
from math import comb

def antichains(n):
    """Every antichain of subsets of {0..n-1}; a subset is a bitmask."""
    sets = sorted(range(2 ** n), key=lambda s: bin(s).count("1"))
    out = []
    def grow(i, chosen):
        out.append(chosen)
        for j in range(i, len(sets)):
            s = sets[j]               # keep s only if incomparable with all
            if all(s & t != s and s & t != t for t in chosen):
                grow(j + 1, chosen + [s])
    grow(0, [])
    return out

for n in range(1, 6):
    A = antichains(n)
    big = max(len(a) for a in A)
    lym = max(sum(Fraction(1, comb(n, bin(s).count("1"))) for s in a)
              for a in A)
    print(f"n={n}: {len(A):5} antichains, largest {big:2},"
          f" C(n,n//2) = {comb(n, n // 2):2}, max LYM sum = {lym}")

n=1:     3 antichains, largest  1, C(n,n//2) =  1, max LYM sum = 1
n=2:     6 antichains, largest  2, C(n,n//2) =  2, max LYM sum = 1
n=3:    20 antichains, largest  3, C(n,n//2) =  3, max LYM sum = 1
n=4:   168 antichains, largest  6, C(n,n//2) =  6, max LYM sum = 1
n=5:  7581 antichains, largest 10, C(n,n//2) = 10, max LYM sum = 1

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: Ramsey সীমা

(ক) R(3, 4)-এর recursive আর binomial সীমা বের করুন; parity দিয়ে উন্নত করুন। (খ) R(3, 4) = 9 আর R(2, 5) = 5 জেনে R(3, 5) আর R(4, 4)-এর ওপরের সীমা দিন।

1. (ক) R(2, 4) + R(3, 3) = 4 + 6 = 10; C(3 + 4 − 2, 2) = C(5, 2) = 10. 4 আর 6 দুটিই জোড়, তাই উপপাদ্য ২.৩-এ R(3, 4) ≤ 9.
2. (খ) R(3, 5) ≤ R(2, 5) + R(3, 4) = 5 + 9 = 14 (সত্য মানের সমান)। R(4, 4) ≤ R(3, 4) + R(4, 3) = 18 (এটিও সত্য মান); binomial সীমা শুধু C(6, 3) = 20 দেয়।

অঙ্ক ২: গুদামের রুট

বাজারঘরের ১০টি গুদাম। (ক) কোনো তিনটি পরস্পর সরাসরি যুক্ত না হলে সর্বোচ্চ কয়টি রুট? (খ) কোনো চারটি পরস্পর যুক্ত না হলে?

1. (ক) Mantel: ⌊100/4⌋ = 25, গুদামগুলো ৫ + ৫ দুই দলে ভাগ করে K_5,5.
2. (খ) Turán, r = 3: দল 4, 3, 3; edge (100 − 16 − 9 − 9)/2 = 33. যাচাই: (1 − 1/3) · 100/2 ≈ 33.3, আর 33 ≤ 33.3. (scratch-এ মেলানো।)

অঙ্ক ৩: কম্বো অফার

৬ ধরনের পণ্য থেকে কম্বো অফার, কোনো অফার আরেকটির ভেতরে নয়। (ক) সর্বোচ্চ কয়টি? (খ) কেউ ৮টি দুই-পণ্যের অফার আর ১০টি তিন-পণ্যের অফার একসঙ্গে প্রস্তাব করলেন। LYM দিয়ে দেখান এটি antichain হতে পারে না।

1. (ক) Sperner: C(6, 3) = 20, সব তিন-পণ্যের কম্বো।
2. (খ) LYM-যোগ 8/C(6, 2) + 10/C(6, 3) = 8/15 + 10/20 = 31/30 > 1, তাই কোথাও একটি দুই-পণ্যের অফার একটি তিন-পণ্যের অফারের ভেতরে পড়বেই। লক্ষ করুন মোট সংখ্যা 18 < 20, তবু অসম্ভব: Sperner-এর চেয়ে LYM সূক্ষ্মতর।

প্রমাণের ভুল ধরুন: “triangle-free মানেই bipartite”

একজন লিখলেন: “ত্রিভুজ না থাকলে গ্রাফটি দুই দলে ভাগ হয়, অর্থাৎ bipartite. দলের আকার a আর b হলে edge ≤ ab ≤ ⌊n²/4⌋. তাই Mantel প্রমাণিত। ∎”

ভুল কোথায়: প্রথম বাক্যটি মিথ্যা। Bipartite graph মানে কোনো বিজোড় চক্র নেই (পর্ব ৫৭); ত্রিভুজ না থাকা শুধু দৈর্ঘ্য 3-এর চক্র নিষেধ করে। C₅ triangle-free কিন্তু bipartite নয়, আর §৫-এর stepper-এর গ্রাফও তাই। উপসংহারটি সত্য হলেও প্রমাণটি অবৈধ, কারণ সব triangle-free গ্রাফকে এটি ধরে না। সঠিক প্রমাণে degree-র যুক্তি (§৫) লাগে, যা কোনো দুই-দলের কাঠামো ধরে নেয় না।

৯ · AI-এর যুগে — Ramsey আর extremal দাবি যাচাই

এই বিষয়ে AI সহকারী সংজ্ঞা ঠিক বলে, কিন্তু সংখ্যা, শর্ত আর সাম্প্রতিক ফলে নিয়মিত ভুল করে। Ramsey সংখ্যা নিয়ে প্রশ্নের উত্তর বছরে বছরে বদলায়, আর অনেক মডেল পুরনো সীমা আত্মবিশ্বাসের সঙ্গে বলে। কয়েকটি পরিচিত ভুল:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ওপরের আর নিচের সীমা দুটিই আছে, আর নিচের সীমায় একটি নির্দিষ্ট রং দেওয়া
• প্রতিটি উপপাদ্যের শর্ত (s, t ≥ 3, simple graph, antichain) মিলিয়ে দেখেছি
• প্রমাণে চক্রাকার যুক্তি বা উল্টো দিক প্রমাণ নেই, induction-এর ভিত্তি আছে
• সংখ্যাগুলো ছোট ক্ষেত্রে brute force-এ নিজে চালিয়ে মিলিয়েছি
• সাম্প্রতিক সীমা আর সালের দাবি মূল জরিপ বা প্রবন্ধে মিলিয়েছি, বানানো সূত্র নেই

এই বিষয়ের দাবিগুলোর একটি সুবিধা আছে: নিচের সীমা মানে একটি নির্দিষ্ট রং, আর রং দেওয়া থাকলে কম্পিউটার কয়েক মিলিসেকেন্ডে তা যাচাই করে। কঠিন অংশ ওপরের সীমা, যেখানে সব রং দেখতে হয়; সেখানে প্রমাণের প্রতিটি ধাপ নিজে পড়ুন।