Resolutions and associated primes of powers of ideals

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Loiskekoski, Lauri
dc.date.accessioned 2015-07-01T08:13:17Z
dc.date.available 2015-07-01T08:13:17Z
dc.date.issued 2014
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/17042
dc.description.abstract Independent sets are subsets of a graph where none of the nodes have links between them. Finding the largest independent subsets and covering a graph by independent subsets are problems commonly encountered in combinatorial optimization. In this thesis we study the independent sets of a graph and more general independence systems with the tools of commutative algebra. We build a poset from the independent sets of a graph and associate an ideal in a commutative ring to it. We calculate the associated primes and the free resolution of this ideal and its powers. We show that the free resolution can be found geometrically as a cell resolution by embedding the poset to a space with as many dimensions as the graph has vertices. Similarly the associated primes can be found by looking for the critical subgraphs which are subgraphs of the graph whose chromatic number is reduced by one when any of the vertices of the graph is removed. en
dc.description.abstract Itsenäiset joukot ovat verkkojen osajoukkoja, joissa solmujen välillä ei ole yhtään linkkiä. Mahdollisimman suurten itsenäisten joukkojen löytäminen ja verkon peittäminen itsenäisillä joukoilla ovat kombinatorisessa optimoinnissa vastaan tulevia ongelmia. Tässä työssä tutkitaan verkkojen itsenäisiä joukkoja ja yleisempiä itsenäisyysrakenteita kommutatiivisen algebran keinoin. Rakennamme verkon itsenäisistä joukoista osittain järjestetyn joukon, johon liitämme kommutatiivisen renkaan ideaalin. Laskemme tälle ideaalille ja sen potensseille assosioidut alkuideaalit sekä vapaan resoluution. Osoitamme, että tämän ideaalin vapaan resoluution pystyy luomaan soluresoluutiona upottamalla osittain järjestetty joukko avaruuteen, jonka ulottuvuuksien määrä on sama kuin verkon solmujen määrä. Vastaavasti assosioitu alkuideaali löytyy analysoimalla verkon kriittisiä aliverkkoja, eli verkkoja joiden kromaattinen luku laskee yhdellä, mikäli mikä tahansa verkon solmuista poistetaan. fi
dc.format.extent v + 24 s.
dc.language.iso en en
dc.title Resolutions and associated primes of powers of ideals en
dc.title Ideaalien potenssien resoluutiot ja assosioidut alkuideaalit fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.department Matematiikan ja systeemianalyysin laitos fi
dc.subject.keyword kommutatiivinen algebra fi
dc.subject.keyword verkkoteoria fi
dc.subject.keyword itsenäinen joukko fi
dc.subject.keyword soluresoluutio fi
dc.subject.keyword kriittinen aliverkko fi
dc.subject.keyword kromaattinen luku fi
dc.subject.keyword commutative algebra en
dc.subject.keyword independent set en
dc.subject.keyword graph theory en
dc.subject.keyword independence structure en
dc.subject.keyword simplex en
dc.subject.keyword critical subgraph en
dc.subject.keyword chromatic number en
dc.identifier.urn URN:NBN:fi:aalto-201507013684
dc.type.dcmitype text en
dc.programme.major Matematiikka fi
dc.programme.mcode Mat-1
dc.type.ontasot Diplomityö fi
dc.type.ontasot Master's thesis en
dc.contributor.supervisor Engström, Alexander


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account