ప్రతి చుక్కనూ మిగతా అన్నింటితో కలపండి: అతి తక్కువ ఖండనలు, నిరూపితం

ఒక కాగితంపై ఐదు చుక్కలు పెట్టి, ప్రతి జతనూ ఒక వక్రరేఖతో కలపండి: మొత్తం పది వక్రరేఖలు. అవి మీకు నచ్చినట్లు వంగవచ్చు, కానీ ఏదీ మూడో చుక్క గుండా వెళ్ళకూడదు. ప్రతి ఖండననూ తప్పించడానికి ప్రయత్నించండి, మీరు విఫలమవుతారు. ఐదు చుక్కలతో, కనీసం 1 ఖండన అనివార్యం; ఆరింటితో, కనీసం 3; పదింటితో, కనీసం 60.

గణిత శాస్త్రవేత్తలు అలాంటి చిత్రాన్ని సంపూర్ణ గ్రాఫ్ (complete graph) Kₙ యొక్క చిత్రణ అంటారు — n బిందువులు, ప్రతి జతా కలపబడి ఉంటుంది — ఏ చిత్రణ అయినా చేరగలిగే అతి తక్కువ ఖండనల సంఖ్యను దాని ఖండన సంఖ్య (crossing number) అంటారు. చెక్ రిపబ్లిక్‌లోని చార్లెస్ విశ్వవిద్యాలయానికి చెందిన మార్టిన్ బాల్కో ఈ ప్రశ్నను “టోపోలాజికల్ గ్రాఫ్ సిద్ధాంతంలోని అత్యంత ప్రసిద్ధ సమస్యల్లో ఒకటి” అంటారు.

ఒక కళాకారుడి లెక్క

1950ల చివరలో, బ్రిటిష్ కళాకారుడు ఆంథొనీ హిల్ సరిగ్గా

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

ఖండనలున్న Kₙ చిత్రణలను నిర్మించాడు; ఇక్కడ ⌊ ⌋ అంటే క్రిందికి పూర్ణాంకానికి సవరించడం. ఏ చిత్రణా ఇంతకంటే మెరుగ్గా చేయలేదన్న ఊహను మొదట గై (Guy) ప్రచురించారు, తర్వాత హరారీ, హిల్ చర్చించారు, ఎర్డోష్, గై ప్రాచుర్యంలోకి తెచ్చారు. దీన్ని హరారీ–హిల్ ఊహ (Harary–Hill conjecture) లేదా గై ఊహ అంటారు.

సూత్రం వేగంగా పెరుగుతుంది:

4 లేదా అంతకంటే తక్కువ చుక్కలు: 0 ఖండనలు
5 చుక్కలు: 1
7 చుక్కలు: 9
10 చుక్కలు: 60
14 చుక్కలు: 315

ఆరు దశాబ్దాల పాక్షిక సమాధానాలు

ప్రతి చుక్కల సంఖ్యకూ సరిగ్గా Z(n) ఖండనలున్న చిత్రణలు ఉన్నాయి; కష్టమైన భాగం ఏమిటంటే, ఏ చిత్రణా ఇంతకంటే మెరుగ్గా చేయలేదని చూపడం.

అరవై ఏళ్ళకు పైగా, అది ప్రత్యేక రకాల చిత్రణలకు మాత్రమే నిరూపితమైంది — ఉదాహరణకు, చుక్కలన్నీ ఒకే రేఖపై ఉండి, ప్రతి వక్రరేఖా దానికి ఒకే వైపున ఉండేవి, లేదా చుక్కలు ఒక గోళంపై ఉండి, ప్రతి వక్రరేఖా అతి దగ్గరి మార్గాన్ని తీసుకునేవి. బాల్కో స్వయంగా ఫులెక్, కిన్‌చ్ల్‌లతో కలిసి అలాంటి ఒక తరగతిని పరిష్కరించారు. 2021 నాటికి, కంప్యూటర్లు 14 చుక్కల వరకు సూత్రాన్ని ధృవీకరించాయి. చాలా పెద్ద సంఖ్యలో చుక్కలకు, అత్యుత్తమ సాధారణ ఫలితాలు Z(n) లో కనీసం 98.5%, తర్వాత 98.99% కు హామీ ఇచ్చాయి.

ఒక నిరూపణ, ఆ తర్వాత మరింత స్పష్టమైనది

2026లో, OpenAI ఎన్ని చుక్కలకైనా వర్తించే ఒక నిరూపణను ప్రకటించింది; బాల్కో పత్రం దాన్ని “OpenAI Math Release preprint” గా పేర్కొంటూ, సిద్ధాంతానికి ఘనతను దానికే ఇస్తుంది. ఆ నిరూపణ ఎలా కనుగొనబడిందో పత్రం చెప్పదు. బాల్కో మాటల్లో, మూల నిరూపణ “సాపేక్షంగా చిన్నది”, కానీ “అనుసరించడం చాలా కష్టం”. ఆయన ప్రీప్రింట్ ఒక సరళీకృత రూపాన్ని అందిస్తుంది; అది “రేఖీయ బీజగణితం, గ్రాఫ్ సిద్ధాంతాలపై ప్రాథమిక జ్ఞానాన్ని మాత్రమే కోరుతుంది” అని ఆయన రాశారు. మరో గణిత శాస్త్రవేత్త గెలాసియో సలాజార్ ఒక ప్రత్యేకమైన, వివరణాత్మక విశదీకరణను సిద్ధం చేస్తున్నారు.

ఖండనలకు బదులు గుణకాలను లెక్కించడం

తెలిసిన చిత్రణలు ఇప్పటికే Z(n) ను చేరుకుంటాయి కాబట్టి, దిగువ హద్దుకు మాత్రమే నిరూపణ అవసరం. దానికి నాలుగు అడుగులు పడతాయి.

బేసి సంఖ్యలు సరిపోతాయి. ఒక ఉత్తమ చిత్రణను, ఒక చుక్కను పంచుకునే వక్రరేఖలు ఎప్పుడూ ఖండించుకోకుండా తిరిగి గీయవచ్చు; అప్పుడు ప్రతి ఖండనలోనూ 4 వేర్వేరు చుక్కలు ఉంటాయి. 6 చుక్కల్లో ఒక్కొక్కదాన్ని వంతులవారీగా తొలగించండి: మిగిలిన ప్రతి 5-చుక్కల చిత్రంలోనూ కనీసం 1 ఖండన ఉంటుంది, ప్రతి ఖండనా 6 తొలగింపుల్లో సరిగ్గా 2 తొలగింపుల తర్వాత నిలుస్తుంది (దాని సొంత 4 చుక్కల్లో ఏది తొలగించినా అది మాయమవుతుంది, మిగతా 2 తొలగింపుల తర్వాత నిలుస్తుంది). కాబట్టి ఖండనల సంఖ్యకు రెట్టింపు కనీసం 6: అంటే కనీసం 3, ఇదే Z(6). ఇదే లెక్క ప్రతి సరి సంఖ్యకూ పనిచేస్తుంది.
బహుపదుల కుటుంబం. ప్రతి చుక్కకూ దాని సొంత సంఖ్యను ఇవ్వండి. ఒక ఖండనలో రెండు వక్రరేఖలు, కాబట్టి నాలుగు చుక్కలు, కాబట్టి నాలుగు సంఖ్యలు ఉంటాయి. బాల్కో నాలుగు చరరాశులలో బహుపదులను ఉపయోగిస్తారు; n బేసి అయినప్పుడు ఆ కుటుంబానికి సరిగ్గా Z(n) స్వతంత్ర గుణకాలు ఉండేలా వాటిని ఎంచుకుంటారు — 7 చుక్కలకు, 3 × 3 = 9.
చాలా తక్కువ ఖండనలు చోటు మిగులుస్తాయి. ఒక ఖండన వద్ద బహుపది శూన్యమవ్వాలని కోరడం ఒక సమీకరణం. స్వేచ్ఛా గుణకాల కంటే తక్కువ సమీకరణాలు ఉంటే, రేఖీయ బీజగణితం ఎప్పుడూ ఒక శూన్యేతర పరిష్కారాన్ని మిగులుస్తుంది. కాబట్టి Z(n) కంటే తక్కువ ఖండనలున్న చిత్రణకు, దాని అన్ని ఖండనల వద్దా శూన్యమయ్యే ఒక శూన్యేతర బహుపది లభిస్తుంది; వాటిలో అతి తక్కువ ఘాతం గలదాన్ని తీసుకుందాం.
సమతలం తిప్పికొడుతుంది. జ్యామితి ఒకే ఒక సంప్రదాయ వాస్తవం ద్వారా ప్రవేశిస్తుంది: సమతలంలోని ఒక సంవృత వలయం (closed loop) మరొకదాన్ని కుడి నుంచి ఎడమకు ఎన్నిసార్లు దాటుతుందో, ఎడమ నుంచి కుడికి కూడా సరిగ్గా అన్నిసార్లే దాటుతుంది. బాగా ఎంచుకున్న భారాలతో, ఇది బహుపది విలువల వర్గాల మొత్తాన్ని ఇస్తుంది — కొన్ని ధనాత్మకంగా, కొన్ని ఋణాత్మకంగా లెక్కించబడి — దాని మొత్తం సున్నా. ధనాత్మక పదాలన్నీ ఖండనల వద్దే ఉంటాయి, అక్కడ బహుపది సున్నా, కాబట్టి ఋణాత్మక పదాలు కూడా శూన్యం కావాలి. వలయ వాస్తవాన్ని రెండోసారి ఉపయోగిస్తే, అది ఒక స్థిర కారణాంకంతో భాగించబడేదిగా మారుతుంది; భాగించడం వల్ల అదే లక్షణం ఉన్న, తక్కువ ఘాతం గల శూన్యేతర బహుపది వస్తుంది — ఇది అసాధ్యం, ఎందుకంటే మనం అతి తక్కువ ఘాతం గలదాన్నే తీసుకున్నాం.

ఆ గుర్తు (sign) వాదనే బాల్కో చేసిన ప్రధాన మార్పు: అది “అపభ్రష్టం కాని ద్విరేఖీయ రూపం, లంబ పూరకాలతో కూడిన” (involving a nondegenerate bilinear form and orthogonal complements) మూల వాదనను భర్తీ చేస్తుంది. ఆయన వలయ వాస్తవాన్ని కూడా వేరే విధంగా నిరూపిస్తారు, ప్రతి చుక్కనూ మరింత నేరుగా వేరుపరుస్తారు.

ఒకేసారి పరిష్కారమైన ఇతర నెట్‌వర్క్‌లు

ఖండనలకు బదులు, అసలు ఖండించుకునే వక్రరేఖల జతలను, లేదా బేసి సంఖ్యలో ఖండించుకునే జతలను లెక్కించినా సమాధానం Z(n) గానే ఉంటుంది — ఒక చుక్కను పంచుకునే వక్రరేఖలు మరెక్కడా కలవనంత వరకు. ఇంతకుముందరి తగ్గింపులతో (reductions) కలిపితే, ఈ సిద్ధాంతం కొన్ని లంకెలు తొలగించిన సంపూర్ణ గ్రాఫ్‌లకు, ఒక మార్గం వెంబడి లేదా సరి చక్రం చుట్టూ గొలుసుగా కలిపిన సంపూర్ణ గ్రాఫ్ ప్రతులకు, విస్తరించిన సియర్‌పిన్‌స్కీ గ్రాఫ్‌లు (extended Sierpiński graphs) అనే భిన్నఘనాకార (fractal) తరహా నెట్‌వర్క్‌ల కుటుంబానికి కూడా కచ్చితమైన ఖండన సంఖ్యలను ఇస్తుంది.

6 చుక్కలపై ఉన్న సంపూర్ణ గ్రాఫ్ నుంచి ఒకే ఒక వక్రరేఖను తీసివేయండి, దాని కనిష్ఠం 3 ఖండనల నుంచి 2 కి పడిపోతుంది; 8 చుక్కలపై, 18 నుంచి 15 కి.