ఒక స్థిర సాంద్రత వద్ద యాదృచ్ఛిక జాలాలకు రంగులు వేయడం అసాధ్యమవుతుంది
ఒక గ్రాఫ్ (graph) — లంకెలతో కలిపిన చుక్కలు — ఒక రంగుల పెట్టె తీసుకోండి. q రంగులతో ఒక సరైన రంగుల అమరిక (proper colouring) ప్రతి చుక్కకు q రంగుల్లో ఒకదాన్ని ఇస్తుంది, అనుసంధానమైన రెండు చుక్కలకు ఎప్పుడూ ఒకే రంగు రాకుండా. లంకెలు తక్కువగా ఉంటే, అది సులభం. ఎక్కువగా ఉంటే, అది అసాధ్యమవుతుంది.
ఇప్పుడు గ్రాఫ్ను యాదృచ్ఛికంగా నిర్మించండి: n చుక్కలు, ప్రతి జత ఒక చిన్న సంభావ్యతతో స్వతంత్రంగా అనుసంధానమవుతుంది, తద్వారా ఒక చుక్కకు సగటున d పొరుగు చుక్కలు ఉంటాయి. d పెరిగే కొద్దీ, యాదృచ్ఛిక గ్రాఫ్ “q రంగులతో దాదాపు నిశ్చితంగా (almost surely) రంగు వేయదగినది” అనే స్థితి నుంచి “దాదాపు నిశ్చితంగా కాదు” అనే స్థితికి మారుతుంది. ఈ మార్పు సరిగ్గా ఎక్కడ జరుగుతుంది? మూడు నుంచి మొదలుకొని ఏ స్థిర రంగుల సంఖ్య q కైనా, ఆ ప్రశ్నే కేంబ్రిడ్జ్ విశ్వవిద్యాలయానికి (University of Cambridge) చెందిన గైయా కారెనినీ (Gaia Carenini) రాసిన కొత్త పత్రపు అంశం.
ఊగిసలాడే అవకాశమున్న ఒక మార్పు
గ్రంథసూచిలో పేర్కొన్న 1999 నాటి ఒక పత్రంలో, అక్లియోప్టాస్ (Achlioptas), ఫ్రీడ్గట్ (Friedgut) ఈ పరివర్తన ఆకస్మికమైనదని (sharp) నిరూపించారు: ప్రతి పరిమాణం n కు, ఒక కీలకమైన సగటు డిగ్రీ (average degree) d_q(n) ఉంటుంది — దానికి కొంచెం కింద గ్రాఫ్ దాదాపు నిశ్చితంగా రంగు వేయదగినది, కొంచెం పైన దాదాపు నిశ్చితంగా కాదు. మార్పు జరిగే కిటికీ కుంచించుకుపోయి శూన్యమవుతుంది.
కానీ దాంతో ఒక లొసుగు మిగిలింది. గ్రాఫ్లు పెద్దవయ్యే కొద్దీ ఆ కీలక విలువే ఊగిసలాడటాన్ని (oscillating) ఏదీ నిరోధించలేదు — ఒక పరిమాణం గల గ్రాఫ్లకు ఒక చోట, పెద్దవాటికి కొంచెం వేరే చోట ఉంటూ, ఎప్పటికీ స్థిరపడకుండా. అక్లియోప్టాస్–ఫ్రీడ్గట్ అభిసరణ పరికల్పన (Achlioptas–Friedgut convergence conjecture) ఇలా జరగదని చెబుతుంది: ప్రతి q కు, ఒకే ఒక స్థిరాంకం d_q ఉంటుంది — దాని కింద యాదృచ్ఛిక గ్రాఫ్లు రంగు వేయదగినవి, దాని పైన కావు.
భౌతిక శాస్త్రవేత్తలు ఏమి అంచనా వేశారు
ఏం జరుగుతుందో దాని గురించి సాంఖ్యక భౌతిక శాస్త్రం (statistical physics) దగ్గర ఒక చిత్రం ఉండేది. లంకెలు జోడించే కొద్దీ, సరైన రంగుల అమరికలు గుచ్ఛాలుగా (clusters) గుమిగూడతాయి: ఒక గుచ్ఛంలోని అమరికలు ఒకదానినొకటి పోలి ఉంటాయి, రెండు వేర్వేరు గుచ్ఛాలు మాత్రం చాలా చుక్కలపై భిన్నంగా ఉంటాయి. తర్వాత, సాంద్రీకరణ (condensation) అనే ఒక దశలో, కొన్ని పెద్ద గుచ్ఛాలు మొత్తం రంగుల అమరికల్లో గణనీయమైన వాటాను కలిగి ఉంటాయి — ఆ తర్వాతే రంగుల అమరికల సమితి ఖాళీ అవుతుంది. పరిమితి దగ్గర లెక్కింపు వాదనలు ఎందుకు ఇబ్బంది పడతాయో ఆ వ్యవస్థీకరణ వివరిస్తుంది.
చాలా రంగులకు, మునుపటి పరిశోధనలు ఇప్పటికే పరిమితిని ఒక ఇరుకైన పరిధిలో బంధించాయి: అది సుమారు 2q log q − log q − 2 log 2 కు, 2q log q − log q − 1 కు మధ్య ఉంటుంది; q పెరిగే కొద్దీ ఇది 2 log 2 − 1 వెడల్పు గల అంతరం. కానీ “ఇరుకైనది” అంటే “స్థిరమైనది” కాదు, మూడు వంటి తక్కువ రంగుల సంఖ్యలకు ఆ ప్రశ్న తెరిచే ఉండిపోయింది.
ముందుగా పరిష్కరించిన ఒక కవల సమస్య
రంగులు వేయడానికి ఒక కవల సమస్య ఉంది: సంతృప్తి సాధ్యత (satisfiability) — యాదృచ్ఛిక తార్కిక షరతుల జాబితాలోని అన్నీ నిజమయ్యేలా చరరాశులకు నిజం లేదా అబద్ధం అనే విలువలను ఎంచుకునే సమస్య. అక్కడ కూడా, ఒక ఆకస్మిక పరిమితి ఉందని తెలుసు, కానీ అది స్థిరపడుతుందనే నిరూపణ లేదు. పత్రంలో ఉదహరించిన 2026 నాటి ఒక నివేదికలో, మూడు నుంచి మొదలుకొని ప్రతి షరతు పొడవుకూ (constraint length) అది స్థిరపడుతుందనే నిరూపణను కారెనినీ ప్రకటించారు — పరివర్తన కిటికీ చాలా ఇరుకైనదని చూపడం ద్వారా. కొత్త పత్రం ఆ వాదనను రంగులు వేయడానికి అనుగుణంగా మలుస్తుంది.
కలిసి గడ్డకట్టిన జతలు
నిరూపణ వరుస తగ్గింపుల (reductions) గొలుసు ద్వారా సాగుతుంది. యాదృచ్ఛిక లంకెలను ఒక్కొక్కటిగా జోడిస్తూ, గ్రాఫ్ రంగు వేయదగినది కాకుండా పోయే క్షణాన్ని H అనుకుందాం. ఒక యాదృచ్ఛిక గ్రాఫ్ నుంచి మరొకదానికి H కొద్దిగా మాత్రమే మారితే — సుమారు n/(log n)² లంకెల కిటికీలోపల — అప్పుడు పరిమితి స్థిరపడి తీరాలి. ఒక సాంప్రదాయ అసమానత దాన్ని చివరి రంగు వేయదగిన గ్రాఫ్ గురించిన ప్రశ్నగా మారుస్తుంది: సగటున, అది ఎన్ని కొత్త యాదృచ్ఛిక లంకెలను తట్టుకుంటుంది?
ఇక్కడే కీలక భావన వస్తుంది: గడ్డకట్టిన జతలు (frozen pairs). ప్రతి సరైన రంగుల అమరికా రెండు చుక్కలకు ఒకే రంగు ఇచ్చినప్పుడు, అవి ఒక గడ్డకట్టిన జతను ఏర్పరుస్తాయి. ఒక కొత్త లంకె సరిగ్గా అలాంటి జతను కలిపినప్పుడే ప్రాణాంతకమవుతుంది. ఒంటరి చుక్కలు ఒక నిర్దిష్ట రంగుకు గడ్డకట్టవు, ఎందుకంటే రంగులను పరస్పరం మార్చుకుంటే ఎప్పుడూ మరో సరైన రంగుల అమరిక వస్తుంది; బలవంతంగా నిర్ణయమయ్యేది రెండు చుక్కల మధ్య సంబంధం. లంకెలు జోడించే కొద్దీ ఈ గడ్డకట్టిన తరగతులు ఎలా పెరుగుతాయో కారెనినీ అనుసరిస్తారు — ఒక లంకెను గానీ మొత్తం చుక్కను గానీ తొలగించి, తిరిగి కనిపించే ఎంపికలను పరిశీలించడం ద్వారా. చివరి రంగు వేయదగిన గ్రాఫ్ ఎక్కువకాలం తట్టుకోలేదని అంచనాలు చూపిస్తాయి; ఇది పరికల్పనను నిరూపించడానికి సరిపడేంతగా కిటికీని ఇరుకు చేస్తుంది.
ఇంకా తెలియనిది
ప్రతి q ≥ 3 కు పరిమితి d_q ఉందని సిద్ధాంతం (theorem) చెబుతుంది. అది ఎక్కడ ఉందో అది చెప్పదు: మూడు రంగులకు కూడా, పత్రం దానికి ఏ విలువనూ ఇవ్వదు. ఈ పత్రం ఒకే రచయిత రాసిన ప్రిప్రింట్, ఇంకా సహచర సమీక్షకు గురికాలేదు. దాని గణిత వాదనల్లో ఏదీ ఒక పెద్ద భాషా నమూనా (large language model) ద్వారా రూపొందించబడలేదనే ఒక చిన్న ప్రకటనతో అది ముగుస్తుంది.
