1960ల నాటి గ్రాఫ్ పజిల్‌కు ఎట్టకేలకు ముగింపు

కొన్ని బిందువులు తీసుకుని, వాటిలో కొన్ని జంటలను గీతలతో కలపండి: గణిత శాస్త్రవేత్తలు దీన్ని గ్రాఫ్ అంటారు, బిందువులను దాని శీర్షాలు (vertices), గీతలను దాని అంచులు (edges) అంటారు. చక్రం (cycle) అంటే వేర్వేరు శీర్షాలను సందర్శించి మొదలైన చోటికే తిరిగి వచ్చే మూసిన వలయం. సహజంగా వచ్చే ప్రశ్న: ఒక గ్రాఫ్ అంచులను — ప్రతి అంచునూ సరిగ్గా ఒక్కసారి వాడుతూ — చక్రాలుగా విభజించగలమా?

పత్రం గుర్తుచేసినట్టు, దీనికి జవాబు చాలాకాలంగా తెలుసు: ప్రతి శీర్షాన్నీ సరి సంఖ్యలో అంచులు తాకినప్పుడు, అప్పుడు మాత్రమే అది సాధ్యం. అలాంటి గ్రాఫ్‌లను ఆయిలర్ గ్రాఫ్‌లు (Eulerian) అంటారు. తర్వాతి ప్రశ్న, ఎన్ని చక్రాలు అవసరం అన్నది. చక్రాలు మాత్రమే సరిపోని గ్రాఫ్‌లకు, ఒంటరి అంచులను కూడా ముక్కలుగా అనుమతిస్తారు.

ఊహ

1960లలో ఎర్డోష్, గల్లాయ్ (Erdős, Gallai), n శీర్షాలున్న ప్రతి గ్రాఫ్ అంచులనూ, గరిష్ఠంగా nకు అనులోమానుపాతంలో — O(n) అని రాస్తారు — ఉన్న చక్రాలు, ఒంటరి అంచులుగా విభజించవచ్చని ఊహించారు. ఎర్డోష్ దీన్ని తన అపరిష్కృత సమస్యల సంకలనాల్లో చాలావాటిలో చేర్చారు. హాయోష్ (Hajós) చేసిన సంబంధిత ఊహ, ప్రతి ఆయిలర్ గ్రాఫ్‌కూ గరిష్ఠంగా (n − 1)/2 చక్రాలు సరిపోతాయా అని అడుగుతుంది.

ఆశించగలిగిన అత్యుత్తమం రేఖీయమే (linear): కొన్ని గ్రాఫ్‌లకు సుమారు 1.5 n ముక్కలు అవసరమని ఎర్డోష్ చూపారు. nను ఏదో ఒక స్థిరాంకంతో గుణిస్తే ఎల్లప్పుడూ సరిపోతుందా అన్నదే ప్రశ్న.

నెమ్మదిగా జరిగిన హద్దుల యాభై ఏళ్లు

ఎర్డోష్, గల్లాయ్ స్వయంగా ఒక సరళమైన పద్ధతిని గమనించారు: అత్యంత పొడవైన చక్రాన్ని పదేపదే తొలగించడం. అది సుమారు n log n ముక్కలను ఇస్తుంది — పత్రం ప్రకారం, దాదాపు యాభై ఏళ్లు అదే అత్యుత్తమ సాధారణ హద్దుగా నిలిచింది. ఇటీవల కాన్లన్, ఫాక్స్, సుడకోవ్ (Conlon, Fox, Sudakov) దాన్ని n log log nకు తగ్గించారు, తర్వాత బుచిచ్, మాంట్‌గోమరీ (Bucić, Montgomery) n log* nకు తగ్గించారు; ఇక్కడ log* n — ఒకటి కంటే కిందికి రావడానికి ఎన్నిసార్లు సంవర్గమానం తీసుకోవాలో ఆ సంఖ్య — ఊహించలేనంత నెమ్మదిగా పెరుగుతుంది. ఈ విధానాలు దశలవారీగా పనిచేశాయి, ప్రతి దశకు సుమారు n చక్రాలు ఖర్చయ్యాయి, కాబట్టి దశల సంఖ్య ఎప్పుడూ తుది లెక్కలోకి చొరబడేది. యాదృచ్ఛిక గ్రాఫ్‌ల (random graphs) వంటి ప్రత్యేక కుటుంబాలకు కూడా ఈ ఊహ ఇప్పటికే నిరూపితమైంది.

వలయాల ఖర్చు చెల్లించే బరువులు

దక్షిణ కొరియాలోని KAISTకు చెందిన జేహూన్ కిమ్ (Jaehoon Kim) ఇప్పుడు ఈ ఊహను నిరూపిస్తున్నారు: n శీర్షాలున్న ప్రతి గ్రాఫ్‌నూ గరిష్ఠంగా Cn చక్రాలు, అంచులుగా విభజించగలిగే ఒక స్థిర స్థిరాంకం C ఉంది. ఉపసిద్ధాంతంగా, హాయోష్ ఊహ ఒక స్థిర గుణకం వరకు నిజమవుతుంది.

ఈ నిరూపణ దశల పద్ధతిని వదిలేస్తుంది. ఒకే విధానం చక్రాలనూ అంచులనూ ఒక్కొక్కటిగా తొలగిస్తుంది, మొత్తం సంఖ్యను రెండు రాశులు అదుపులో ఉంచుతాయి, ఒక్కొక్కటీ n యొక్క స్థిరాంక గుణిజం కంటే తక్కువగానే ఉంటుంది.

• డిగ్రీలపై ఆధారపడిన పొటెన్షియల్. ప్రతి శీర్షానికీ దాని అంచుల సంఖ్యతో పాటు తగ్గే ఒక బరువు ఇస్తారు, సుమారు 1 / (డిగ్రీ × log² డిగ్రీ). శీర్షాల బరువుల మొత్తం కనీసం 1 ఉన్న చక్రం బరువైనది. బరువైన చక్రాన్ని తొలగిస్తే మొత్తం “పొటెన్షియల్” కనీసం 1 తగ్గుతుంది, ఆ పొటెన్షియల్ మొదట్లో n యొక్క స్థిరాంక గుణిజం కంటే ఎక్కువ ఉండదు. కాబట్టి బరువైన చక్రాలను O(n) సార్లు మాత్రమే తొలగించగలం.
• శీర్షాల సంఖ్య. బరువైన చక్రం ఒక్కటీ మిగలనప్పుడు గ్రాఫ్ “తేలికైనది” — పెద్ద డిగ్రీలున్న తేలికైన గ్రాఫ్‌లో ఒక దట్టమైన, దాదాపు మూసుకుపోయిన ప్రాంతం తప్పనిసరిగా ఉంటుందని ప్రధాన కొత్త సిద్ధాంతం చూపుతుంది. ఆ ప్రాంతాన్ని దాని పరిమాణానికి అనులోమానుపాతంలో ఉన్న చక్రాలు, అంచులుగా విభజిస్తారు, ఆ తర్వాత దాని శీర్షాల్లో కనీసం యాభైవ వంతుకు గరిష్ఠంగా రెండు అంచులే మిగిలి, అవి శాశ్వతంగా తప్పుకుంటాయి. ప్రతి శీర్షం ఒక్కసారి మాత్రమే తప్పుకోగలదు కాబట్టి, ఈ భాగం ఖర్చు కూడా O(n).

గ్రాఫ్‌లోని దట్టమైన భాగాల్లో, “ఎక్స్‌పాండర్ల” గుండా వెళ్లే జోడింపు మార్గాలతో మార్గాల ముక్కలను ఒకే చక్రంగా మూస్తారు; యాదృచ్ఛిక రంగుల కేటాయింపు ఒకే చక్రానికి చెందిన జోడింపు మార్గాలను దూరంగా ఉంచుతుంది. — చిత్రం 3, Kim (2026), arXiv:2610.07840.

ఆ దట్టమైన ప్రాంతాలను విభజించడానికి, నిరూపణ బుచిచ్, మాంట్‌గోమరీల దృఢమైన “ఎక్స్‌పాండర్ల” (expanders) — శీర్షాల ప్రతి సమితికీ చాలా పొరుగు శీర్షాలుండే గ్రాఫ్‌లు — సాధనాలను విస్తరిస్తుంది, ఒకే చక్రాన్ని కలిపే మార్గాలు ఎప్పుడూ ఢీకొనకుండా శీర్షాలకు యాదృచ్ఛికంగా రంగులు వేస్తుంది.

ఇంకా తేలనివి

స్థిరాంకం C అపారమైనది, రచయిత దాన్ని ఉత్తమీకరించడానికి ప్రయత్నించలేదు. అత్యుత్తమ స్థిరాంకాన్ని — కనీసం 1.5 — కనుగొనడం ఇంకా తేలలేదు, అలాగే హాయోష్ ఊహ కచ్చిత రూపం, గ్రాఫ్‌లను మార్గాలుగా విభజించడంపై గల్లాయ్ సంబంధిత ఊహ కూడా. బరువుల ఉపాయానికి కావాల్సింది మొత్తం అభిసరించే (converge) బరువులు మాత్రమే, ఇది ఇతర విభజన సమస్యల్లోనూ ఉపయోగపడవచ్చని రచయిత సూచిస్తున్నారు.

ఇది ఒకే రచయిత ప్రీప్రింట్, ఇంకా సహచర సమీక్ష (peer review) ద్వారా తనిఖీ కాలేదు.

ప్రయోజనాల సంఘర్షణ. వాదనలను అభివృద్ధి చేయడంలో, పాఠ్యం, చిత్రాలు సిద్ధం చేయడంలో ChatGPT (OpenAI), Claude (Anthropic)లను విస్తృతంగా వాడినట్టు, అన్ని ఫలితాలనూ తామే సరిచూసి పత్రానికి పూర్తి బాధ్యత వహిస్తున్నట్టు రచయిత పేర్కొన్నారు. మీరు చదువుతున్న ఈ పాఠ్యాన్ని కూడా Claude రాసింది.