تحقیق در مورد ایده آل های خطی به ترتیب کوهن - مکوالی

بخشی از مقاله

ايده آل هاي خطي به ترتيب كوهن-مكوالي

چكيده- G را يك نمودار غيرمستقيم ساده n راسي در نظر بگيريد و بگذاريد برايده آل خطي مرتبطش دلالت كند. مانشان مي دهيم كه تمام نمودارهاي و تري G ، به ترتيب كوهن- مكوالي هستند ، دليل ما بر پايه نشان دادن اين است كه دوگانه الكساندر I(G) ،خطي و ازمولفه است.

نتيجه ما فرضيه فريدي را كه مي گويد ايده آل درخت ساده شده به ترتيب كوهن- مكوالي، هرزوگ، هيبي، مي باشد، وفرضيه ژنگ كه مي گويد يك نمودار وتري كوهن-مكوالي است اگر و تنها اگر ايده آل خطي اش در هم ريخته نباشد، را تكميل مي كند. ما همچنين ويژگي هاي دايره هاي مرتب كوهن- مكوالي را بيان مي كنيم و نمونه‌هايي از گراف هاي مرتب غيروتري كوهن- مكوالي را هم ارائه مي كنيم.

1-مقدمه
G را يك گراف ساده n راسي در نظر بگيريد پس G هيچ حلقه يا خطوط چندگانه اي پهن دو راس ندارد.) رئوس ومجموعه هاي خطي G توسط EG,VG را به ترتيب نشان دهيد. ما ايده آل تك جمله اي غير مربع چهارگانه با K كه يك ميزان است و جايي كه را به G ارتباط مي دهيم.ايده ال ايده آل خطي Gناميده مي شود.
توجه اوليه اين مقاله ايده آل هاي خطي گراف هاي وتري است. يك گراف G وتري است اگر هر دايره طول يك وتر داشته باشد. اينجا اگر ،خطوط يك دايره طول n باشند، ما مي گوييم كه دايره وري يك وتر دارد اگر دو راس xj,xi در دايره به نحوي وجود داشته باشند كه يك خط براي G باشند اما خطي در دايره نباشد.

ما مي گوييم كه يگ گراف G كوهن –مكوالي است اگر كوهن-مكوالي باشد. چنانكه هرزوگ، هيبي و ژنگ اشاره مي كنند، طبقه بندي تمام گراف هاي كوهن-مكوالي شايد اكنون قابل كشيدن نباشند، اين مسئله به سختي طبقه بندي كردن تمام مجموعه هاي ساده شده كوهن-مكوالي است.]9[.البته هرزوگ، هيبي و ژنگ در ]9[ ثابت كردند كه وقتي G يك گراف وتري باشد،پس G در هر ميداني كوهن-مكوالي است اگر وفقط اگر به هم نريخته باشد.
ويژگي كوهن –مكوالي به ترتيب بودن، كه شرايطي است ضعيف تر از كوهن-مكوالي بودن، توسط استنلي ]14[ در ارتباط با تئوري قابليت جدا شدن غيرخالص معرفي شد.

تعريف 1-1- را در نظر بگيريد. يك M معيار B درجه دار كوهن –مكوالي به ترتيب ناميده مي شود اگر يك تصفيه معين از معيارهاي R درجه بندي وجود داشته باشد.

به نحوي كه كوهن –مكوالي باشد، و ابعاد كرول خارج قسمت در حال افزايش باشند:

ما ميگوييم يك گراف G كوهن-مكوالي به ترتيب است و در K اگر كوهن-مكوالي به ترتيب باشد. ما مي توانيم به نتيجه هرزوگ، هيبي و ژنگ بر سيم البته با استفاده از اين تضعيف شرايط كوهن-مكوالي. نتيجه اصلي ما فرضيه زير است (كه مستقل از خاصيت (K) است.
فرضيه 2-1 فرضيه 2-3.تمام گراف هاي وتري كوهن-مكوالي به ترتيب هستند.

بنابراين حتي گراف هاي وتري كه ايده آل هاي خطي نشان در هم نريخته نيستند نيز هنوز يك ويژگي جبري را دارا هستند.فرضيه 2-3 همچنين حالت يك بعدي كار فردي در توده هاي ساده شده ]3[ را نيز عموميت مي بخشد.
مقاله ما به صورت زير سازمان مي يابد. در قسمت بعدي ، ما نتايجي از اين ادبيات درباره دوگانگي الكساندر ودرباره گراف هاي وتري جمع مي كنيم. در بخش 3،فرضيه 2.3 را ثابت مي كنيم.

ما برخي از گراف هاي غيروتري در قسمت 4 را كه دايره هاي كوهن-مكوالي را به ترتيب طبقه بندي مي كنند بررسي مي كنيم و در مورد برخي ازويژگي هاي گراف‌هاي شامل دايره هاي –n براي n>3 تحقيق مي كنيم.
همچنين شرايط كافي را براي گرافي كه نمي تواند كوهن-مكوالي به ترتيب باشد ،ارائه مي كنيم.
2-اجزا مورد نياز
درطول اين مقاله، G بر يك گراف ساده روي رئوس n با مجموعه نقطه اي VG ومجموعه خطي EG دلالت مي كند. ايده آل خطي ،جايي كه را به G مربوط مي سازيم.

گراف كامل در رئوس n كه بر Kn دلالت شده است،گرافي است با مجموعه خطي ، يعني گراف اين ويژگي را دارد كه خطي بين هر جفت رئوس وجود دارد. اگر x نقطه اي در G باشد بايد بنويسيم N(x) كه بر همسايه‌هاي x دلالت كند،يعني آن رئوسي كه خطي را با x شريكند. ما ابتدا بايد به حالتي توجه كنيم كه G يك گرافي وتري است.گراف هاي وتري ويژگي زير را دارند:

لم 21- G,[6,7,12,15] را يك گراف وتري در نظر بگيريد، x را يك زير نمودار كامل از G در نظر بگيريد.اگر ،پس نقطه اي به نام وجود داردكه زيرگراف به وجود آمده توسط مجموعه همسايه مربوط به x، يك گراف كامل باشد. اين امر همچنين زير نمودار به وجود آمده در را وادار مي كند كه يك زير گراف كامل باشد.
يك پوشش راس گراف G يك زير مجموعه از VG است به نحوي كه هر خط G حداقل به يك راس A برخوردار داشته باشد. توجه كنيدكه ما هيچ وقت به داشتن يك راس مجزا در پوشش راس نياز نداريم.

مثلا ، اگر ما گرافي در سه راس داشته باشيم و تنها خط موجود باشد، پس هر دو پوشش هاي راس هستند. پوشش هاي راس يك گراف G به دو گانه الكساندر مربوطند.
تعريف 2-2- I را يك ايده آل تك جمله اي غيرمربع در نظر بگيريد. دوگانه الكساندر غيرمربع ايده آل
است.

پس نتيجه ساده اي گرفته مي شود:
لم 3-2- G را يك گراف ساده با ايده آل خطي در نظر بگيريد.پس

يك پوشش راس براي G است.

يك تجزيه درجه بندي شده آزاد حداقل به هر ايده آل همگون I از R مرتبط است.

كه در آن R(j) بر معيار R به دست آمده از تغيير درجات R توسط j دلالت مي كند. عدد ij,Bi,j(I) امين عدد درجه بندي شده «بتي» مربوط به Iاست و برابر تعداد حداقل مولد هاي درجه j در I امين معيار يك جفتي است.

تعريف 4-2-فرض كنيد كه I ايده آل همگون R است كه تمام مولدهايشان در جه d دارند. پس I يك تجزيه خطي دارد اگر تما براي تمام براي يك ايده آل همگون I ، ما (Id) را مي نويسيم كه بر ايده آل تبديل شده توسط تمام عناصر كه درجه d دارند،دلالت مي كند. توجه كنيد كه (Id) با Id فرق مي كند، كه فضاي برداري تمام عناصر I با درجه d است.هرزوگ وهيبي تعريف زير را در ]7[ معرفي كردند.

تعريف 5-2-يك ايده آل همگون I خطي و از مولفه است اگر (Id) يك تجزيه خطي براي تمام d4 داشته باشد.
اگر I توسط تك جمله اي هاي غيرمربع تبديل شود،بگذاريد I(d) بر ايده‌آل تبديل شده توسط تك جمله هاي غير مربع درجه d براي I دلالت كند. هرزوگ وهيبي ] 7،قضيه 5-1[ نشان دادند كه :
فرضيه 6-2-فرض كنيد I يك ايده آل تك جمله اي تبديل شده توسط تك جمله هاي غيرمربع باشد.
پس I خطي و از مولفه است اگر وتنها اگر I[d] يك تجزيه خطي براي تمامي d ها داشته باشد.
يك فرد مي تواند از خارج قسمت هاي خطي براي تعيين اينكه ايده آل يك تجزيه خطي دارد استفاده كند.
تعريف 7-2- I را ايده آل تك جمله اي R در نظر بگيريد. مي گوييم كه I خارج قسمت هاي خطي دارد اگر براي برخي ترتيب هاي مولد هاي حداقل I با
درجه
توسط يك زير مجموعه تبديل شود.
سپس ما به ]لم [3,5-2 نيازمنديم:
لم 8-2-اگر يك ايده آل تك جمله باشد كه خارج قسمت هاي خطي داشته باشد، و تمامي uiها درجه يكساني داشته باشند.در نتيجه I يك تجزيه خطي دارد.
ما اين سمت را با استفاده از اين نظرها براي ايده آل هاي خطي به پايان مي بريم.
لم 9-2-اگر ايده آل خطي گراف G باشد در نتيجه

يك پوشش راس براي G در اندازه d است.
اثبات. چون توسط پوشش هاي راس حداقل تبديل شده است،هر حداقل غيرمربعي از درجه d در به مجموعه اي از رئوس d مرتبط است كه شامل يك پوشش راس حداقل باشد و در نتيجه رئوس d نيز يك پوشش راس بر G را تشكيل مي دهند.

لم را يك گراف كامل در رئوس n در نظر بگيريد. براي هر d، خارج قسمت هاي خطي دارد، در نتيجه خطي وهم جهت مولفه است.
اثبات: ما نشان ميدهيم كه براي هر d ، خارج قسمت هاي خطي دارد وبنابراين يك تجزيه خطي دارد كه يعني خطي هم جهت مولفه توسط فرضيه 6-2- است.
پوشش هاي رئوس حداقل kn همگي زير مجموعه هاي با اندازه n-1 هستند. بنابارين توسط لم 9-2 ، وقتي كه d=n ، يك ايده آل اصلي است. اين حالات به ميزان ناچيزي خارج قسمت هاي خطي دارند. بنابراين براي نشان دادن اينكه كه خارج قسمت هاي خطي دارد. كافي است.

توجه كنيد كه به ميزان حداقل توسط تمامي تك جمله اي هاي درجه n-1 تبديل شده اند و بنابراين .حالا يك ايده آل تك جمله‌اي غيرمربع ثابت قوي است (همچنين يك ايده آل و رنس غيرمربع در حالت ]8[ است.بنابراين خارج قسمت هاي خطي دارد اگر كسي تك جمله ها را به ترتيب واژه نويسي پايين آمدني مرتب كند.

نكته 11-2-يك اظهارنامه عمومي تر از لم 10-2 صحيح است. J را كوچكتر يا مساوي n بگيريد و بگيريد. ما ميتوانيم ايده آل هايي را در نظر بگريم كه مولفه هايشان تمامي ايده آل ممكن توليد شده توسط j مربوط به متغيرهاي n باشند:

ما ميتوانيم اين ايده آل را به صورت دو گانه اي استنلي –رسند يك مجموعه ساده شده با تمامي صورت هاي ممكن (j-1) اما نه صورت هاي j يا به بصورت ايده آل سطح يك مجموعه ساده شده با تمامي صورت هاي ممكن j به مانند سطح هايش مشاده كنيم. I به صورت حداقل توسط تمامي تك جمله اي هاي غيرمربع درجه n-j+1 تبديل مي شود ودر نتيجه يك ايده آل غيرمربع و رسن است. بنابراين I يك تجزيه خطي دارد و درنتيجه خطي و درجهت مولفه است.
براي آخرين لم،نشان مي دهيم كه براي تعيين اينكه خطي و درجهت مولفه است، بايد شرايط را به صورتي كاهش دهيم كه در آن گراف G هيچ راس جدايي نداشته باشد.

لم 12-2-G را يك گراف ساده روي رئوس n با ايده آل خطي در نظر بگيريد. H را گراف G كه به رئوس مجزاي x+1,…,xn به آن اضافه شده در نظر بگيريد.
فرض كنيد كه خطي و هم جهت مولفه باشد. پس خطي وهم جهت مولفه است.
اثبات. توجه كنيدكه ايده آل هاي خطي H,G مولدهاي حداقل يكساني دارند، گرچه در حلقه هاي مختلفي موجودند. بنابراين مولدهاي حداقل يكساني دارند. توسط لم 9-2-6 چون خطي وهم جهت مولفه است ، نيز خطي و درجهت مولفه است.

3-فرضيه اصلي
در اين بخش ما نتيجه اصلي اين مقاله را ثابت مي كنيم. اثبات ما به نتيجه بعدي هرزوگ و هيبي ]7[ وهرزوگ، رنيز و واكد ] 10[ كه نكات خطي بودن درجهت مولفه و كوهن-ماكوالي به ترتيب بودن را به هم متصل مي كند، ارتباط دارد.
فرضيه 1-3-I را يك ايده آل تك جمله اي غيرمربع از Rدر نظر بگيريد.پس R/I به ترتيب كوهن-ماكوالي است اگر وتنها اگر خطي و در جهت مولفه باشد.
ما به نتيجه اصلي مان رسيده ايم.

فرضيه 2-3-تمامي گراف هاي وتري به ترتيب كوهن-مكوالي هستند.
اثبات .G را يك گراف وتري در نظر بگيريد. فرضيه 1-3 براي نشان دادن اينكه خطي ودر جهت مولفه است كافي است. براي نشان دادن اينكه خطي و در جهت مولفه است، ما دليلمان را بر پايه اثبات فريدي (فرضيه 4-5) قرار داده ايم كه مي گويد بخش غيرمربع ايده آل سطح يك انبوه ساده شده خارج قسمت هاي خطي در هر درجه اي دارد. در فرضيه 6-2- ما نياز داريم نشان دهيم كه يك تجزيه خطي براي هر d دارد. لم 8-2 كافي است نشان دهد خارج قسمت هاي خطي براي هر d دارد.

ما روي تعداد رئوس در گراف وتري توجه مي كنيم. با توجه به لم 12-2 ،ميتوانيم فرض كنيم كه G هيچ راس جدايي ندارد. بنابراين اولين حالت براي بررسي هنگامي است كه ما گراف G در 2 راس متصل به خط داشته باشيم. در اين حالت G=k2 ،پس خارج قسمت هاي خطي براي هر d (با توجه به لم 10-2) دارد.
حال فرض كنيد كه G يك گراف وتري در رئوس باشد كه هيچ نقطه راس مجزايي نداشته باشد پس G حداقل دو خط دارد.اگر G=kn در نتيجه ما طبق لم 10-2 عمل كرده ايم.پس ما ميتوانيم فرض مي كنيم كه G كامل نيست. (مثلا ،k را هر خطي از G بگيريد، وسپس x نقطه راسي خواهد بود كه بر آن خط مماس نيست.)

بنويسيد ملاحظه كنيدكه بايد وتري باشد. توجه كنيدكه ممكن است يك راس جدا( يا رئوس جدا) باشد؛ در اين حالت، ايده آل خط،ايده آل صفر است.
حالا با توجه به لم 9-2 ، به تك جمله هاي غيرمربعي تبديل مي شود كه به پوشش هاي رئوس G به اندازه هاي d مربوطند. توجه كنيد كه هر پوشش راس از G بايد زيرگراف كامل kt+1 تشكيل شده توسط را بپوشاند.پس هر پوشش راسي بايد حداقل شامل رئوس باشد.

اگر يك پوشش راس G باشد كه شامل x است ،پس بايد يك پوشش راس باشد.اگر يك پوشش راس شامل نباشد پس بايد شامل باشد.اما سپس \ بايد يك پوشش راس باشد. (در اين حالت وقتي كه اين زيرگراف يك راس جدا باشد، در نتيجه . هيچ خطي موجودنيست، مجموعه خالي يك پوشش راس است. همانطور كه در هر زير مجموعه از از رئوس است.

را در نظر بگيريد را ايده آل خطي به ترتيب آنها در نظر بگيريد. از بحث بالا نتيجه مي گيريم كه
را به عنوان ايده‌آل هاي R با مولد هاي يكسان مانند ملاحضه مي كنيم.
چون H2,H1 هر دو وتري و با رئوس كمتري از G هستند، با استنباط، خارج قسمت هاي خطي دارند. فرض مي كنيم كه Bis , Ais در ترتيب درست براي خارج قسمت هاي خطي نوشته شده اند. ما اكنون نشان مي دهيم كه
خارج قسمت هاي خطي با درنظر گرفتن اين ترتيب مولدهاي دارد.

چون واضح است كه خارج قسمت هاي خطي دارد، ما بايد چك كنيم كه ايده آل زير به خارج قسمت هاي خطي داشته باشد:

نخست توجه كنيد كه چون B1 به يك پوشش راس G\{x} مرتبط است ،‌B1 حداقل با t-1 از قابل تعبيه است. پس حداكثر يك y به صورت y(B) وجود دارد.
حال فرض كنيم كه pyAj , mxB1 غيرمربع هستند. دو حالت براي توجه كردن وجود دارد.
حالت 1- اگر y\B1 ،پس چون B1 به يك پوشش راس G\{x} مرتبط است، به يك پوشش راس به اندازه d-t-1 از مرتبط است. پس . توجه كنيدكه اگر يك متغير z\m ،‌پس z بايد متغيري ز حلقه باشد. از طرف ديگر نبايد غيرمربع باشد. پس،براي هر متغير z كه z\m ، ، و بنابراين بنابراين (براي هر z كه بر m را تقسيم شود).