Share to: share facebook share twitter share wa share telegram print page

Independence system

In combinatorial mathematics, an independence system ⁠⁠ is a pair , where ⁠⁠ is a finite set and ⁠⁠ is a collection of subsets of ⁠⁠ (called the independent sets or feasible sets) with the following properties:

  1. The empty set is independent, i.e., . (Alternatively, at least one subset of ⁠⁠ is independent, i.e., .)
  2. Every subset of an independent set is independent, i.e., for each , we have . This is sometimes called the hereditary property, or downward-closedness.

Another term for an independence system is an abstract simplicial complex.

Relation to other concepts

  • A pair , where ⁠⁠ is a finite set and ⁠⁠ is a collection of subsets of ⁠⁠, is also called a hypergraph. When using this terminology, the elements in the set ⁠⁠ are called vertices and elements in the family ⁠⁠ are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph.
  • An independence system with an additional property called the augmentation property or the independent set exchange property yields a matroid. The following expression summarizes the relations between the terms:

    HYPERGRAPHS ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.

References

  • Bondy, Adrian; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699.


Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Read other articles:

City of Clinton (steam ferry)

History NameCity of Clinton OwnerKing County OperatorKitsap County Transportation Co. In service1922 Out of service1929 FateDestroyed by fire General characteristics TypeSteam ferry Tonnage57 Length58 ft (17.68 m) Beam20 ft (6.10 m) Installed powerSteam engine, 100 hp (75 kW) PropulsionPropeller City of Clinton was a small steam ferry built in 1922 which served on Puget Sound until March 23, 1929, when the vessel caught fire and sank near the city of Mukilteo, Wa...

 

Semiring

Algebraic ring that need not have additive negative elements Algebraic structure → Ring theoryRing theory Basic conceptsRings • Subrings • Ideal • Quotient ring • Fractional ideal • Total ring of fractions • Product of rings • Free product of associative algebras • Tensor product of algebras Ring homomorphisms • Kernel • Inner automorphism • Frobenius endomorphism Algebraic structures • Module • Associative algebra • Graded ring • Involutive ring • Categ...

 

Marina Orlova (pemeran)

Artikel ini bukan mengenai Marina Orlova (YouTuber). Marina OrlovaLahirMarina Viktorovna Orlova25 Maret 1986 (umur 37)Pyatigorsk, Stavropol Krai, RSFSR, USSRKebangsaanRussiaPekerjaanAktri, penyanyi, komposer dan pujangga, presenterTahun aktif1995–sekarangSitus webmarinaorlova.film Marina Orlova (bahasa Rusia: Марина Викторовна Орлова; lahir 25 Maret 1986) adalah seorang pemeran perempuan asal Rusia. Ia telah berperan dalam 40 film dan acara televisi di Mo...

Пюльвер'єр

Пюльвер'єрPulvérières Країна  Франція Регіон Овернь-Рона-Альпи  Департамент Пюї-де-Дом  Округ Ріом Кантон Понжибо Код INSEE 63290 Поштові індекси 63230 Координати 45°53′11″ пн. ш. 2°54′36″ сх. д.H G O Висота 775 - 994 м.н.р.м. Площа 14,75 км² Населення 402 (01-2020[1]) Густота 25,9 ос./км

 

Roads in Fraser's Hill

Federal Route 422Route informationLength13.5 km (8.4 mi)Existed1920s–2018[1]Major junctionsMajor intersections FT 56 Jalan Bukit Fraser FT 148 Jalan Bukit Fraser 2 LocationCountryMalaysia Highway system Highways in Malaysia Expressways Federal State Roads in Fraser's Hill, Federal Route 422, were a series of federal roads in Fraser's Hill, Pahang, Malaysia from 1920s to 2018 before being downgraded to state roads.[1] The roads are maintained by the Malaysian P...

 

バルデス (スペイン)

Valdés    州  アストゥリアス州 県  アストゥリアス県 面積 353.52 km² 人口 12,635 人 （2014年） 人口密度 35.74 人/km² 住民呼称 valdesano/a Valdés スペイン内バルデス (スペイン)の位置 Valdés アストゥリアス県内バルデス (スペイン)の位置 北緯43度33分0秒 西経6度32分0秒 / 北緯43.55000度 西経6.53333度 / 43.55000; -6.53333座標: 北緯43度33分0秒 西経6度32分0秒...

Super Ape

1976 studio album by The UpsettersSuper ApeStudio album by The UpsettersReleasedAugust 1976 (1976-08)RecordedBlack Ark, Kingston, JamaicaGenreDubLength37:37LabelIsland, UpsetterProducerLee PerryThe Upsetters chronology Revolution Dub(1975) Super Ape(1976) Return of the Super Ape(1978) Lee Scratch Perry chronology Revolution Dub(1975) Super Ape(1976) Roast Fish Collie Weed & Corn Bread(1978) Alternative coverJamaican album cover Professional ratingsReview scoresSourceRati...

 

Tập tin:Logo Vụ Pháp chế BQP.png

Phiên bản trước đó của tập tin này không tự do và không còn được sử dụng trong các bài viết nữa. Do đó, chúng không đạt tiêu chuẩn cho nội dung không tự do và sẽ bị xóa. Phiên bản hiện tại sẽ không bị xóa, chỉ có các bản sửa đổi trước đó bị xóa.Bảo quản viên, Điều phối viên: Nếu thấy không có vấn đề gì với phiên bản hiện tại và nó đáp ứng đúng tiêu chuẩn cho nội d...

 

لاري ر. مارشال

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2019) لاري ر. مارشال معلومات شخصية الميلاد القرن 20  سيدني  مواطنة أستراليا  الحياة العملية المدرسة الأم جامعة ماكواري  المهنة فيزيائي  اللغات الإنجلي�...

The Beatrice Letters

2006 book by Lemony Snicket This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Beatrice Letters – news · newspapers · books · scholar · JSTOR (December 2010) (Learn how and when to remove this template message) The Beatrice Letters AuthorLemony Snicket (pen name of Daniel Handler)IllustratorBrett HelquistCo...

 

Plica semilunaris dari konjungtiva

Plica semilunaris dari konjungtivaTampak depan mata kiri dengan kelopak mata yang dijauhkan untuk menunjukkan medial canthus. (Plica semilunaris dilabeli pada kiri tengah).RincianPengidentifikasiBahasa Latinplica semilunaris conjunctivaeTA98A15.2.07.048TA26841FMA59045Daftar istilah anatomi[sunting di Wikidata] Plica semilunaris adalah lipatan kecil pada bulbar konjungtiva pada canthus tengah pada mata. Organ ini longgar, sehingga gerakan mata tidak terbatasi. Ini adalah sisa-sisa vestigia...

 

Дорогоцінна перлина

Дорогоцінна Перлина — одна з чотирьох книг, що складають Стандартні твори Церкви Ісуса Христа Святих Останніх Днів. Дорогоцінна Перлина є частиною священних писань Церкви Ісуса Христа Святих Останніх Днів (англ. The Church of Jesus Christ of Latter-day Saints) та деяких інших конфесій свя...

Diego Mariño

Diego Mariño Informasi pribadiNama lengkap Diego Mariño VillarTanggal lahir 9 Mei 1990 (umur 33)Tempat lahir Vigo, SpanyolTinggi 185 m (606 ft 11 in)Posisi bermain KiperInformasi klubKlub saat ini LevanteNomor 13Karier junior Santa Mariña1998–2000 Rápido Bouzas2000–2003 Sárdoma2003–2004 Areosa2004–2008 VillarrealKarier senior*Tahun Tim Tampil (Gol)2008–2010 Villarreal C 48 (0)2010–2012 Villarreal B 72 (0)2012–2013 Villarreal 9 (0)2013–2014 Valladolid 2...

 

Ikigami (film)

2008 Japanese filmIkigamiTheatrical release posterDirected byTomoyuki TakimotoWritten byMotoro MaseAkimitsu SasakiTomoyuki TakimotoHiroyuki YatsuBased onIkigami: The Ultimate Limitby Motoro MaseProduced byAkimitsu SasakiStarringShota MatsudaTakashi TsukamotoRiko NarumiTakayuki YamadaAkira EmotoCinematographyTakahide ShibanushiEdited byNobuyuki TakahashiMusic byHibiki InamotoDistributed byToho CompanyRelease date September 27, 2008 (2008-09-27) Running time133 minutesCountryJapa...

 

2009 Commonwealth Bank Tournament of Champions

Tennis tournament2009 Commonwealth Bank Tournament of ChampionsDateNovember 4–8Edition1stChampionsSingles Aravane Rezaï Commonwealth Bank Tournament of Champions · 2010 → The 2009 Commonwealth Bank Tournament of Champions was a singles-only tennis tournament that was played on indoor hard courts. It was the first edition of the Commonwealth Bank Tournament of Champions and was part of the 2009 WTA Tour. It was held at the Bali International Convention Centre in Bali, Indon...

Керлінг на зимових Олімпійських іграх 2022 — змішані пари

Турнір з керлінгу серед змішаних парна XXIV Зимових Олімпійських іграх Місце проведенняПекінський національний плавальний комплексДати2–8 лютогоУчасників20 з 10 країнПризери  Стефанія Константіні Амос Мозанер  Італія Крістін Скаслієн Магнус Недреготт...

 

Breakage (accounting)

For the general concept, see Break (disambiguation). For the musician, see Breakage (musician). For the Breaking Bad episode, see Breakage (Breaking Bad). This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (September 2013) This article needs additional cita...

 

I (2015 film)

2015 film directed by S. Shankar ITheatrical release posterDirected byShankarWritten byShankar Subha (Dialogues) Produced byV Ravichandran D. Ramesh Babu StarringVikramAmy JacksonSuresh GopiCinematographyP. C. SreeramEdited byAnthonyMusic byA. R. RahmanProductioncompanyAascar Films Pvt. Ltd.Distributed byAascar Films Pvt. Ltd. Global United Media (Kerala) AA Films (Hindi) Release date 14 January 2015 (2015-01-14) Running time188 minutes[1]CountryIndiaLanguageTamilBudget...

Nazionale di calcio femminile dell'Austria

Austria Uniformi di gara Casa Trasferta Sport Calcio Federazione ÖFB Confederazione UEFA Codice FIFA AUT Soprannome Das Team Selezionatore Irene Fuhrmann Record presenze Sarah Puntigam (120) Capocannoniere Nina Burger (48) Ranking FIFA 16º Esordio internazionale Svizzera 5-1 Austria Richterswil, Svizzera, 25 agosto 1990 Migliore vittoria Austria 11-0 Armenia Waidhofen an der Ybbs, Austria, 10 maggio 2003 Armenia 0-11 Austria Waidhofen an der Ybbs, Austria, 13 maggio 2003 Peggiore sconfitta ...

 

Deny Marcel

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Deny Marcel – berita · surat kabar · buku · cendekiawan · JSTOR Deny MarcelInformasi pribadiNama lengkap Deny MarcelTanggal lahir 24 Februari 1983 (umur 40)Tempat lahir Balikpapan, Kalimantan TimurT...

 
Kembali kehalaman sebelumnya