Polyhedral combinatorics
પોલિહેડ્રલ કોમ્બિનેટોરિક્સ એ ગણિતની એક શાખા છે, જે કોમ્બિનેટોરિક્સ અને અલગ ભૂમિતિમાં છે, જે બહિર્મુખ પોલિહેડ્રા અને ઉચ્ચ-પરિમાણીય બહિર્મુખ પોલિટોપનાં ચહેરાની ગણતરી અને વર્ણન કરવાની સમસ્યાઓનો અભ્યાસ કરે છે. પોલિહેડ્રલ કોમ્બિનેટોરિક્સમાં સંશોધન બે અલગ અલગ ક્ષેત્રોમાં આવે છે. આ ક્ષેત્રના ગણિતશાસ્ત્રીઓ પોલીટોપ્સના સંયોજનશાસ્ત્રનો અભ્યાસ કરે છે; દાખલા તરીકે, તેઓ એવી અસમાનતાઓ શોધે છે જે મનસ્વી પોલીટોપ્સમાં અથવા પોલીટોપ્સના અમુક મહત્વપૂર્ણ પેટા વર્ગોમાં ઉચ્ચ પરિમાણોના શિરોબિંદુઓ, ધાર અને ચહેરાઓની સંખ્યા વચ્ચેના સંબંધોનું વર્ણન કરે છે, અને પોલીટોપ્સના અન્ય સંયોજન ગુણધર્મોનો અભ્યાસ કરે છે જેમ કે તેમની કનેક્ટિવિટી અને વ્યાસ (અન્ય કોઈપણ શિરોબિંદુથી કોઈપણ શિરોબિંદુ સુધી પહોંચવા માટે જરૂરી પગલાંની સંખ્યા). વધુમાં, ઘણા કોમ્પ્યુટર વૈજ્ઞાનિકો પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાઓથી ઉદ્ભવતા ચોક્કસ ચોક્કસ પોલીટોપ્સ (ખાસ કરીને 0-1 પોલીટોપ્સ, જેમના શિરોબિંદુઓ હાયપરક્યુબના સબસેટ છે) ના ચહેરાના ચોક્કસ વર્ણનમાં સંશોધનનું વર્ણન કરવા માટે "પોલીહેડ્રલ કોમ્બિનેટોરિક્સ" શબ્દસમૂહનો ઉપયોગ કરે છે. મુખ અને મુખ-ગણતરી વેક્ટર બહિર્મુખ પોલીટોપ P ના મુખને P અને બંધ અર્ધ-અવકાશ H ના આંતરછેદ તરીકે વ્યાખ્યાયિત કરી શકાય છે, જેમ કે H ની સીમામાં P નો કોઈ આંતરિક બિંદુ ન હોય. 0-પરિમાણીય ચહેરાઓ પોતે શિરોબિંદુઓ છે, અને 1-પરિમાણીય ચહેરાઓ (ધાર તરીકે ઓળખાતા) શિરોબિંદુઓની જોડીને જોડતા રેખા વિભાગો છે. નોંધ લો કે આ વ્યાખ્યામાં ખાલી સમૂહ અને સંપૂર્ણ બહુપદી P નો પણ સમાવેશ થાય છે. જો P પોતે પરિમાણ d ધરાવે છે, તો પરિમાણ d−1 ધરાવતા P ના મુખને P ના મુખ કહેવામાં આવે છે અને પરિમાણ d−2 ધરાવતા મુખને પર્વતમાળા કહેવામાં આવે છે. પી ના ચહેરાને આંશિક રીતે સમાવેશ દ્વારા ક્રમબદ્ધ કરી શકાય છે, જે ચહેરાની જાળી બનાવે છે જે તેના ટોચના તત્વ પી તરીકે અને તેના તળિયાના તત્વ તરીકે ખાલી સમૂહ ધરાવે છે. પોલિહેડ્રલ સંયોજનશાસ્ત્રમાં મુખ્ય સાધન એ પોલિટોપનું f-વેક્ટર છે, જે વેક્ટર (f0, f1,., fd−1) છે જ્યાં phi એ પોલિટોપનાં i-પરિમાણીય લક્ષણોની સંખ્યા છે. દાખલા તરીકે, ક્યુબમાં આઠ શિરોબિંદુઓ, બાર ધાર અને છ પાસાં હોય છે, તેથી તેનો f-વેક્ટર (8,12,6) છે. બેવડા પોલીટોપમાં વિપરીત ક્રમમાં સમાન સંખ્યાઓ સાથે એફ-વેક્ટર હોય છે; આમ, દાખલા તરીકે, નિયમિત ઓક્ટાહેડ્રોન, જે સમઘન માટે બેવડા હોય છે, તેમાં એફ-વેક્ટર (6,12,8) હોય છે. રૂપરેખાંકન મેટ્રિસીસમાં ત્રાંસા ઘટકો તરીકે નિયમિત પોલીટોપ્સના એફ-વેક્ટરનો સમાવેશ થાય છે. વિસ્તૃત f-વેક્ટરની રચના f-વેક્ટરના દરેક છેડે એક નંબરને જોડીને કરવામાં આવે છે, જેમાં ચહેરાના જાળીના તમામ સ્તરે પદાર્થોની સંખ્યાની ગણતરી કરવામાં આવે છે; વેક્ટરની ડાબી બાજુએ, f−1 = 1 ખાલી સમૂહને ચહેરો તરીકે ગણાવે છે, જ્યારે જમણી બાજુએ, fd = 1 એ P ને જ ગણાવે છે. સમઘન માટે વિસ્તૃત f-વેક્ટર (1,8,12,6,1) છે અને ઓક્ટાહેડ્રોન માટે તે (1,6,12,8,1) છે. જો કે આ ઉદાહરણ માટે પોલિહેડ્રા વેક્ટર એકરૂપ છે (ગુણાંક, ડાબેથી જમણે ક્રમમાં લેવામાં આવે છે, મહત્તમ સુધી વધે છે અને પછી ઘટે છે), ત્યાં ઉચ્ચ-પરિમાણીય પોલીટોપ છે જેના માટે આ સાચું નથી. સરળ પોલીટોપ માટે (પોલીટોપ જેમાં દરેક પાસું સિમ્પ્લેક્સ હોય છે), આ વેક્ટરને રૂપાંતરિત કરવું ઘણીવાર અનુકૂળ હોય છે, જે એચ-વેક્ટર તરીકે ઓળખાતા અલગ વેક્ટરનું ઉત્પાદન કરે છે. જો આપણે f-વેક્ટર (અંતિમ 1 ને બાદ કરતાં) ની શરતોને બહુપદીના ગુણાંક તરીકે અર્થઘટન કરીએ (ઉદાહરણ તરીકે, ઓક્ટાહેડ્રોન માટે આ બહુપદી આપે છે f (x) = x3 + 6x2 + 12x + 8), તો પછી h-વેક્ટર બહુપદીના ગુણાંકની યાદી આપે છે h (x) = f (x−1) (ફરીથી, ઓક્ટાહેડ્રોન માટે, h (x) = x3 + 3x2 + 3x + 1). ઝિગલર લખે છે તેમ, "સરળ પોલીટોપ્સ વિશેની વિવિધ સમસ્યાઓ માટે, એચ-વેક્ટર એ એફ-વેક્ટર્સ કરતાં ફેસ નંબરો વિશેની માહિતીને એન્કોડ કરવાની વધુ અનુકૂળ અને સંક્ષિપ્ત રીત છે". સમાનતાઓ અને અસમાનતાઓ પોલીટોપના એફ-વેક્ટરના ગુણાંક વચ્ચેનો સૌથી મહત્વપૂર્ણ સંબંધ યુલરનું સૂત્ર β (−1) ઇફી = 0 છે, જ્યાં વિસ્તૃત એફ-વેક્ટરના ગુણાંક પર સરવાળાની શરતો હોય છે. ત્રણ પરિમાણોમાં, વિસ્તૃત f-વેક્ટર (1, v, e, f, 1) ની ડાબી અને જમણી બાજુએ બે 1 ને સમીકરણની જમણી બાજુએ ખસેડવાથી આ ઓળખ વધુ પરિચિત સ્વરૂપ v − e + f = 2 માં પરિવર્તિત થાય છે. ત્રિ-પરિમાણીય પોલિહેડ્રોનના દરેક પાસામાં ઓછામાં ઓછી ત્રણ ધાર હોય છે તે હકીકત પરથી, તે 2e ≤ 3f ની બમણી ગણતરી દ્વારા અનુસરે છે, અને યુલરના સૂત્રમાંથી e અને f ને દૂર કરવા માટે આ અસમાનતાનો ઉપયોગ કરવાથી વધુ અસમાનતાઓ e ≤ 3v−6 અને f ≤ 2v−4 તરફ દોરી જાય છે. દ્વૈત દ્વારા, e ≤ 3f−6 અને v ≤ 2f−4. તે સ્ટેનિટ્ઝના પ્રમેયને અનુસરે છે કે આ સમાનતાઓ અને અસમાનતાને સંતોષે છે તે કોઈપણ 3-પરિમાણીય પૂર્ણાંક વેક્ટર બહિર્મુખ પોલિહેડ્રોનનું f-વેક્ટર છે. ઉચ્ચ પરિમાણોમાં, પોલીટોપનાં ચહેરાની સંખ્યાઓ વચ્ચેના અન્ય સંબંધો પણ મહત્વપૂર્ણ બની જાય છે, જેમાં ડેહ્ન-સોમરવિલે સમીકરણો સામેલ છે, જે સરળ પોલીટોપ્સના એચ-વેક્ટરની દ્રષ્ટિએ વ્યક્ત કરવામાં આવે છે, જે તમામ k માટે સરળ સ્વરૂપ hk = hd − k લે છે. k = 0 સાથેના આ સમીકરણોનું ઉદાહરણ યુલરના સૂત્રની સમકક્ષ છે પરંતુ d> 3 માટે આ સમીકરણોના અન્ય ઉદાહરણો એકબીજાથી રેખીય રીતે સ્વતંત્ર છે અને એચ-વેક્ટર (અને તેથી પણ f-વેક્ટર) ને વધારાની રીતે અવરોધે છે. પોલીટોપ ફેસ કાઉન્ટ પરની અન્ય મહત્વપૂર્ણ અસમાનતા અપર બાઉન્ડ થીયરમ દ્વારા આપવામાં આવે છે, જે સૌપ્રથમ આના દ્વારા સાબિત થાય છે, જે જણાવે છે કે n શિરોબિંદુઓ સાથે d-પરિમાણીય પોલીટોપમાં અન્ય કોઈપણ પરિમાણના ઘણા ચહેરાઓ સમાન સંખ્યામાં શિરોબિંદુઓ સાથે પડોશી પોલીટોપ જેટલા હોઈ શકે છેઃ જ્યાં ફૂદડીનો અર્થ એ છે કે જ્યારે d સમ હોય ત્યારે સરવાળાની અંતિમ મુદત અડધી થવી જોઈએ. લક્ષણવિહીન રીતે, આ સૂચવે છે કે તમામ પરિમાણોના મોટાભાગના ચહેરાઓ છે. ચાર પરિમાણોમાં પણ, બહિર્મુખ પોલીટોપ્સના સંભવિત f-વેક્ટરોનો સમૂહ ચાર-પરિમાણીય પૂર્ણાંક જાળીનો બહિર્મુખ સબસેટ બનાવતો નથી, અને આ વેક્ટરના સંભવિત મૂલ્યો વિશે ઘણું બધું અજ્ઞાત રહે છે. આલેખ-સૈદ્ધાંતિક ગુણધર્મો પોલીટોપ્સના ચહેરાની સંખ્યાની તપાસ સાથે, સંશોધકોએ તેમના અન્ય સંયુક્ત ગુણધર્મોનો અભ્યાસ કર્યો છે, જેમ કે પોલીટોપ્સના શિરોબિંદુઓ અને ધાર (તેમના 1-કંકાલ) માંથી મેળવેલા આલેખનનું વર્ણન. બાલિન્સ્કીનો પ્રમેય જણાવે છે કે કોઈપણ ડી-પરિમાણીય બહિર્મુખ પોલીટોપમાંથી આ રીતે મેળવેલ આલેખ ડી-વર્ટેક્સ-જોડાયેલ છે. ત્રિ-પરિમાણીય પોલિહેડ્રાના કિસ્સામાં, આ ગુણધર્મ અને સમતોલતાનો ઉપયોગ પોલિહેડ્રાના આલેખની ચોક્કસ લાક્ષણિકતા દર્શાવવા માટે થઈ શકે છેઃ સ્ટેનિટ્ઝનો પ્રમેય જણાવે છે કે G એ ત્રિ-પરિમાણીય પોલિહેડ્રોનનું હાડપિંજર છે જો અને માત્ર ત્યારે જ જો G એ 3-વર્ટેક્સ-જોડાયેલ સમતોલ આલેખ હોય. (અગાઉ માઈકા પર્લ્સ દ્વારા અનુમાન કરાયેલ) એક પ્રમેય જણાવે છે કે કોઈ વ્યક્તિ તેના આલેખમાંથી સરળ પોલીટોપનાં ચહેરાનાં માળખાનું પુનઃનિર્માણ કરી શકે છે. એટલે કે, જો આપેલ દિશાહીન આલેખ એક સરળ પોલીટોપનું હાડપિંજર હોય, તો ત્યાં માત્ર એક જ પોલીટોપ (સંયોજન સમકક્ષતા સુધી) હોય છે, જેના માટે આ સાચું છે. આ (બિન-સરળ) પડોશી પોલીટોપથી એકદમ વિપરીત છે, જેનો આલેખ સંપૂર્ણ આલેખ છે; સમાન આલેખ માટે ઘણા જુદા જુદા પડોશી પોલીટોપ હોઈ શકે છે. અનન્ય સિંક ઓરિએન્ટેશન પર આધારિત આ પ્રમેયનો બીજો પુરાવો તેમના દ્વારા આપવામાં આવ્યો હતો, અને દર્શાવ્યું હતું કે આ પ્રમેયનો ઉપયોગ તેમના આલેખમાંથી સરળ પોલીટોપ્સના ફેસ લેટીસની પુનઃરચના માટે બહુપદી સમય અલ્ગોરિધમ મેળવવા માટે કેવી રીતે કરવો. જો કે, આપેલ આલેખ અથવા જાળીને સરળ પોલીટોપનાં ચહેરાનાં જાળી તરીકે અનુભવી શકાય છે કે કેમ તે ચકાસવું એ (ધ્રુવીયતા દ્વારા) સરળ પોલીટોપ્સની અનુભૂતિને સમકક્ષ છે, જે વાસ્તવિક અસ્તિત્વના સિદ્ધાંત માટે સંપૂર્ણ હોવાનું દર્શાવવામાં આવ્યું હતું. રેખીય પ્રોગ્રામિંગ માટે સિમ્પ્લેક્સ પદ્ધતિના સંદર્ભમાં, પોલીટોપનો વ્યાસ સમજવો મહત્વપૂર્ણ છે, જે અન્ય કોઈપણ શિરોબિંદુથી માર્ગ દ્વારા કોઈપણ શિરોબિંદુ સુધી પહોંચવા માટે જરૂરી ઓછામાં ઓછી ધારની સંખ્યા છે. રેખીય પ્રોગ્રામની રેખીય અસમાનતાઓની પ્રણાલી પ્રોગ્રામના તમામ શક્ય ઉકેલોનું પ્રતિનિધિત્વ કરતા પોલીટોપનાં પાસાઓને વ્યાખ્યાયિત કરે છે, અને સિમ્પ્લેક્સ પદ્ધતિ આ પોલીટોપમાં પાથને અનુસરીને શ્રેષ્ઠ ઉકેલ શોધે છે. આમ, વ્યાસ આ પદ્ધતિ માટે જરૂરી પગલાંની સંખ્યા પર નીચી સીમા પૂરી પાડે છે. હિર્શ અનુમાન, જે હવે નકારી કાઢવામાં આવ્યું છે, તેણે નિશ્ચિત પરિમાણ અને પાસાઓની સંખ્યા સાથે પોલીટોપનો વ્યાસ કેટલો મોટો હોઈ શકે તેના પર એક મજબૂત (રેખીય) બંધન સૂચવ્યું હતું. તેમના વ્યાસ પર નબળા (અર્ધ-બહુપદી અને) ઉપલા સીમાઓ જાણીતા છે, તેમજ પોલીટોપ્સના વિશેષ વર્ગો માટે હિર્શ અનુમાનના પુરાવા પણ જાણીતા છે. કોમ્પ્યુટેશનલ ગુણધર્મો આપેલ પોલીટોપનાં શિરોબિંદુઓની સંખ્યા અમુક કુદરતી સંખ્યા k દ્વારા બંધાયેલી છે કે કેમ તે નક્કી કરવું એ કોમ્પ્યુટેશનલ રીતે મુશ્કેલ સમસ્યા છે અને જટિલતા વર્ગ PP માટે સંપૂર્ણ છે. 0-1 પોલીટોપ્સના પાસાઓ પૂર્ણાંક પ્રોગ્રામિંગ માટે કટીંગ-પ્લેન પદ્ધતિઓના સંદર્ભમાં મહત્વપૂર્ણ છે કે જે સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓના ઉકેલોને અનુરૂપ શિરોબિંદુઓ ધરાવતા પોલીટોપ્સના પાસાઓનું સચોટ વર્ણન કરવામાં સક્ષમ હોય. મોટેભાગે, આ સમસ્યાઓના ઉકેલો દ્વિસંગી વાહક દ્વારા વર્ણવી શકાય છે, અને અનુરૂપ બહુપદીઓમાં શિરોબિંદુઓ હોય છે જે બધા શૂન્ય અથવા એક હોય છે. ઉદાહરણ તરીકે, બિરખોફ પોલીટોપને ધ્યાનમાં લો, જે n × n મેટ્રિસીસનો સમૂહ છે જે ક્રમચય મેટ્રિસીસના બહિર્મુખ સંયોજનોમાંથી રચાઈ શકે છે. સમાનરૂપે, તેના શિરોબિંદુઓને સંપૂર્ણ દ્વિપક્ષી આલેખમાં તમામ સંપૂર્ણ મેળનું વર્ણન કરવા તરીકે વિચારી શકાય છે, અને આ પોલીટોપ પરની રેખીય ઓપ્ટિમાઇઝેશન સમસ્યાને દ્વિપક્ષી લઘુત્તમ વજન સંપૂર્ણ મેળ ખાતી સમસ્યા તરીકે અર્થઘટન કરી શકાય છે. બિરખોફ-વોન ન્યુમેન પ્રમેય જણાવે છે કે આ બહુપદીને બે પ્રકારની રેખીય અસમાનતા અથવા સમાનતા દ્વારા વર્ણવી શકાય છે. પ્રથમ, દરેક મેટ્રિક્સ કોષ માટે, એક અવરોધ છે કે આ કોષ બિન-નકારાત્મક મૂલ્ય ધરાવે છે. અને બીજું, મેટ્રિક્સની દરેક પંક્તિ અથવા સ્તંભ માટે, એક અવરોધ છે કે તે પંક્તિ અથવા સ્તંભમાં કોષોનો સરવાળો એક સમાન છે. પંક્તિ અને સ્તંભની મર્યાદાઓ n2 − 2n + 1 પરિમાણની રેખીય પેટા જગ્યાને વ્યાખ્યાયિત કરે છે જેમાં બિરખોફ પોલીટોપ આવેલું છે, અને બિન-નકારાત્મકતા મર્યાદાઓ તે પેટા જગ્યામાં બિરખોફ પોલીટોપનાં પાસાઓને વ્યાખ્યાયિત કરે છે. જો કે, બિરખોફ પોલીટોપ અસામાન્ય છે કારણ કે તેના પાસાંઓનું સંપૂર્ણ વર્ણન ઉપલબ્ધ છે. અન્ય ઘણા 0-1 પોલીટોપ માટે, ઘાતાંકીય રીતે ઘણા અથવા સુપરએક્સપોનેન્શિયલી ઘણા પાસાઓ છે, અને તેમના પાસાઓનું માત્ર આંશિક વર્ણન ઉપલબ્ધ છે. એબ્સ્ટ્રેક્ટ પોલીટોપ કોમ્બિનેટરિયલ કોમ્યુટેટિવ બીજગણિત મેટ્રોઇડ પોલીટોપ ઓર્ડર પોલીટોપ સિમ્પલ સ્ફીયર સ્ટેબલ મેચિંગ પોલીટોપ નોટ્સ રેફરન્સ પણ જુઓ. . . . . . . . . . . . . . . બાહ્ય કડીઓ.