Problem 881: Divisor Graph Coloring

Mathematical Analysis

Theorem 1 (Chromatic Number)

Proof. The chromatic number equals the length of the longest chain in the divisibility poset.

Upper bound: Assign color $c(k) = v_2(k) + 1$ where $v_2(k)$ is the 2-adic valuation (largest power of 2 dividing $k$) … actually this does not work directly. Instead:

Partition $\{1, \ldots, n\}$ into antichains (sets with no divisibility relations). By Dilworth’s theorem, the minimum number of antichains needed equals the length of the longest chain.

Lower bound: The chain $1, 2, 4, 8, \ldots, 2^{\lfloor \log_2 n \rfloor}$ has length $\lfloor \log_2 n \rfloor + 1$, and all elements must receive distinct colors.

Upper bound: We exhibit $\lfloor \log_2 n \rfloor + 1$ antichains covering $\{1, \ldots, n\}$. For each $k$, write $k = 2^a \cdot m$ with $m$ odd. Assign color $a$. Two numbers with the same 2-adic valuation $a$ are $k_1 = 2^a m_1$ and $k_2 = 2^a m_2$ with $m_1, m_2$ odd. If $k_1 \mid k_2$, then $m_1 \mid m_2$, so they can share a chain. This doesn’t immediately give antichains.

Correct approach: The longest chain has length $\lfloor \log_2 n \rfloor + 1$ (since $1 \mid 2 \mid 4 \mid \cdots \mid 2^{\lfloor \log_2 n \rfloor} \leq n$). By Dilworth’s theorem, the minimum number of antichains = longest chain length. This equals $\chi(G_n)$ since coloring = antichain partition. $\square$

Theorem 2 (Dilworth’s Theorem)

In any finite partially ordered set, the maximum size of a chain equals the minimum number of antichains needed to partition the set.

Theorem 3 (Clique Number)

$\omega(G_n) = \lfloor \log_2 n \rfloor + 1 = \chi(G_n)$, so the graph is perfect on chains.

Proof. The chain $1, 2, 4, \ldots, 2^k$ forms a clique of size $k+1$ in $G_n$. This is maximum since any chain in the divisibility order of $\{1, \ldots, n\}$ has length at most $\lfloor \log_2 n \rfloor + 1$. $\square$

Concrete Numerical Examples

$G_8$: Divisibility Graph

Edges: $(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (2,4), (2,6), (2,8), (3,6), (4,8)$.

Longest chain: $1 \to 2 \to 4 \to 8$, length 4. So $\chi(G_8) = 4$.

Valid 4-coloring: assign color $= \lfloor \log_2 k \rfloor$:

• Color 0: $\{1\}$
• Color 1: $\{2, 3\}$
• Color 2: $\{4, 5, 6, 7\}$
• Color 3: $\{8\}$

Check: within each color class, no divisibility (e.g., $4 \nmid 5$, $5 \nmid 6$, etc.).

Verification Table

Edge Count of $G_n$

$|E(G_n)| = \sum_{k=1}^{n} (d(k) - 1)$ where $d(k)$ counts divisors of $k$ that are in $\{1, \ldots, n\}$. Actually:

For $n = 10$: $\sum \lfloor 10/k \rfloor = 10+5+3+2+2+1+1+1+1+1 = 27$, so $|E| = 27 - 10 = 17$.

Complexity Analysis

Answer

/*
 * Problem 881: Divisor Graph Coloring
 * chi(G_n) = floor(log2(n)) + 1 by Dilworth's theorem.
 * The longest chain 1, 2, 4, ..., 2^k determines the chromatic number.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int chromatic_number(ll n) {
    if (n <= 0) return 0;
    int chi = 0;
    while ((1LL << chi) <= n) chi++;
    return chi;
}

ll edge_count(int n) {
    ll total = 0;
    for (int k = 1; k <= n; k++)
        total += n / k - 1;
    return total;
}

bool verify_coloring(int n) {
    // color(k) = floor(log2(k))
    vector<int> color(n + 1);
    for (int k = 1; k <= n; k++) {
        int c = 0;
        while ((1 << (c + 1)) <= k) c++;
        color[k] = c;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
            if (color[i] == color[j]) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << "=== Chromatic Number ===" << endl;
    for (ll n : {1LL,2LL,4LL,8LL,10LL,16LL,100LL,1000LL,(ll)1e9,(ll)1e18}) {
        cout << "chi(G_" << n << ") = " << chromatic_number(n) << endl;
    }

    cout << "\n=== Coloring Verification ===" << endl;
    for (int n : {4, 8, 16, 32, 50}) {
        bool ok = verify_coloring(n);
        cout << "n=" << n << ": " << (ok ? "OK" : "FAIL") << endl;
        assert(ok);
    }

    cout << "\n=== Edge Counts ===" << endl;
    for (int n : {10, 50, 100, 500}) {
        cout << "|E(G_" << n << ")| = " << edge_count(n) << endl;
    }

    cout << "\nAnswer: chi(G_{10^18}) = " << chromatic_number((ll)1e18) << endl;
    return 0;
}

"""
Problem 881: Divisor Graph Coloring
Chromatic number of divisibility graph G_n on {1,...,n}.
Result: chi(G_n) = floor(log2(n)) + 1 (by Dilworth's theorem).
"""

from math import log2, floor

def chromatic_number(n):
    """chi(G_n) = floor(log2(n)) + 1."""
    if n <= 0:
        return 0
    return floor(log2(n)) + 1

def longest_chain(n):
    """Find the longest divisibility chain in {1,...,n}."""
    chain = [1]
    while chain[-1] * 2 <= n:
        chain.append(chain[-1] * 2)
    return chain

def valid_coloring(n):
    """Assign colors: color(k) = floor(log2(k))."""
    return {k: floor(log2(k)) for k in range(1, n + 1)}

def verify_coloring(n, coloring):
    """Check that no two adjacent vertices share a color."""
    for i in range(1, n + 1):
        for j in range(2 * i, n + 1, i):
            if coloring[i] == coloring[j]:
                return False, (i, j)
    return True, None

def edge_count(n):
    """Count edges in G_n: sum_{k=1}^{n} (floor(n/k) - 1)."""
    total = 0
    for k in range(1, n + 1):
        total += n // k - 1
    return total

def edge_count_fast(n):
    """O(sqrt(n)) edge count using floor block decomposition."""
    # sum floor(n/k) for k=1..n, then subtract n
    total = 0
    k = 1
    while k <= n:
        v = n // k
        kp = n // v
        total += v * (kp - k + 1)
        k = kp + 1
    return total - n

# --- Verification ---
print("=== Chromatic Number Verification ===")
for n in [1, 2, 3, 4, 5, 8, 10, 16, 32, 64, 100, 1000]:
    chi = chromatic_number(n)
    chain = longest_chain(n)
    coloring = valid_coloring(n)
    ok, conflict = verify_coloring(n, coloring)
    print(f"  n={n:>4}: chi={chi}, chain={chain}, "
          f"coloring valid={'OK' if ok else f'FAIL at {conflict}'}")
    assert ok
    assert len(chain) == chi

print("\n=== Edge Counts ===")
for n in [5, 10, 20, 50, 100]:
    e1 = edge_count(n)
    e2 = edge_count_fast(n)
    print(f"  |E(G_{n})| = {e1} (brute), {e2} (fast), Match: {'OK' if e1 == e2 else 'FAIL'}")
    assert e1 == e2

print("\n=== Color Classes for n=16 ===")
coloring = valid_coloring(16)
classes = {}
for k, c in coloring.items():
    classes.setdefault(c, []).append(k)
for c in sorted(classes):
    print(f"  Color {c}: {classes[c]}")

answer = chromatic_number(10**18)
print(f"\nAnswer: chi(G_{{10^18}}) = {answer}")

# --- 4-Panel Visualization ---