Poset(Under Construction!)

Poset

數列推廣成偏序集。

Matroid(Under Construction!)

Antimatroid

反擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,聯集也要被包含
向下 規則1.
給兩三個大集合,可以有交集
每個大集合都要窮舉各種子集合,生一堆子子孫孫出來
終點(匯)顯然是空集合

向上 規則2.
給兩三個大集合,可以有交集
兩兩大集合都要窮舉各種聯集,生一堆父父祖祖出來
起點(源)顯然是宇集合

Matroid

擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,隨便從差集找到某個元素,然後小集合添上元素,也要被包含
   隨便抓兩個集合,交集+差集子集也要被包含
1. 子集合通通不可被包含  除了空集合
2. 聯集-交集也要被包含

Greene-Kleitman Theorem

Dilworth's Theorem推廣版本,跟數論的Partition有關。我沒有研究。

https://www.math.ku.edu/~jmartin/courses/math796-S08/notes0402.pdf

Domination(Under Construction!)

Domination

LIS/凸包/maximal layer/interval coverage/
dominating point -> dominating inteval -> segment tree

(x1,y1) dominates (x2,y2) iff x1 >= x2 and y1 >= y2

variable change: let a = -x, b = y
(a1,b1) covers    (a2,b2) iff a1 <= a2 and b1 >= b2

variable change: let idx1 = a1, idx2 = b1, v1 = a2, v2 = b2
(idx1,idx2) (v1,v2) are inversion pairs iff idx1 < idx2 and v1 > v2
整除是被dominate
Gröbner Basis

UVa 11020 Timus 1078

Submodular Function(Under Construction!)

Submodular Function

marginal effect
https://www.zhihu.com/question/34720027

area cover
https://zhuanlan.zhihu.com/p/106576120

optimization
https://people.seas.harvard.edu/~yaron/AM221-S16/schedule.html