-
Notifications
You must be signed in to change notification settings - Fork 0
/
morseResolutionsPackage.m2
1409 lines (1220 loc) · 40.8 KB
/
morseResolutionsPackage.m2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
newPackage(
"MorseResolutions",
Version => "1.0.1",
Date => "March 1, 2023",
Headline => "morse resolutions",
Authors => {
{
Name => "Trung Chau",
Email => "trung.chau@utah.edu",
HomePage => "https://www.math.utah.edu/~chau/"
},
{
Name => "Selvi Kara",
Email => "selvikara@gmail.com",
HomePage => "www.selvikara.com"
},
{
Name => "Augustine O'Keefe",
Email => "aokeefe@conncoll.edu ",
HomePage => "https://www.conncoll.edu/directories/faculty-profiles/augustine-okeefe/"
},
}
AuxiliaryFiles => false,
DebuggingMode => false
)
export {
-- Methods
"taylorCell",
"allTaylorCells",
"bridge",
"smallestBridge",
"possibleEdgesWithPositions",
"possibleEdges",
"bMMatching",
"bridgeFriendly",
"criticalBMCells",
"bMRanks",
"lyubeznikBridge",
"lyubeznikMatching",
"criticalLyubeznikCells",
"lyubeznikRanks",
"possibleTrimmedEdges",
"trimmedMatching",
"criticalTrimmedCells",
"trimmedRanks",
}
-------------------
-- Exported Code
-------------------
---------------------------------------------------------------
---------------------------------------------------------------
-- Auxiliary functions: subsets of minimal generating set of a
-- monomial ideal
---------------------------------------------------------------
---------------------------------------------------------------
-----------------------------------------
--Taylor Cells of Cardinality k-
-----------------------------------------
taylorCell = method(TypicalValue => List)
taylorCell(Ideal,ZZ) := List => (I,k)->(
select(subsets flatten entries gens I, i-> #i==k)
);
-----------------------------------------
--Taylor Cells-
-----------------------------------------
allTaylorCells = method(TypicalValue => List)
allTaylorCells(Ideal):= List => I->(
M= flatten entries gens I;
L=for k from 0 to #M-1 list taylorCell(I,#M-k);
L
);
-----------------------------------------------------------
-----------------------------------------------------------
-- Main Barile-Macchia resolution functions
-----------------------------------------------------------
-----------------------------------------------------------
-----------------------------------------
--Bridge-
-----------------------------------------
bridge = method(TypicalValue => List)
bridge(List) := List => L ->(
if #L<3 then {} else select(L, i -> lcm L == lcm delete(i,L))
);
-----------------------------------------
--Smallest Bridge-
-----------------------------------------
smallestBridge = method(TypicalValue => RingElement)
smallestBridge(List, Sequence) := RingElement => (L, S) ->(
if bridge L=!={} then (
sortB = select(S, i-> member(i,bridge L)); --select returns a list in the same order as the input list
sortB_0
)
else print "no bridges exist"
);
-----------------------------------------------
--Possible Edges of a Barile-Macchia Matching-
-----------------------------------------------
---Part 1: Possible Edges of a Barile-Macchia Matching with Positions of the Smallest Bridges--
possibleEdgesWithPosition = method(Dispatch => Thing)
possibleEdgesWithPosition(Sequence) := List => S -> (
I = ideal S;
Sigma = drop(allTaylorCells I, -2); --drops the Taylor Cells of length 1 and 2
Omega = flatten drop(allTaylorCells I, -2);
A={};
i = 0;
j = 0;
while #Omega >0 do(
sigma = Sigma_i_j;
if isSubset({sigma}, Omega) then(
if bridge sigma =!= {} then(
sb = smallestBridge(sigma, S);
sigmaMinusSb = delete(sb, sigma);
A = append(A, (position(S, k-> sb==k), sigma, sigmaMinusSb));
Omega = delete(sigma, Omega);
Omega = delete(sigmaMinusSb, Omega);
)
else Omega = delete(sigma, Omega);
);
if #(Sigma_i)> j+1 then j = j+1 else(i = i+1; j = 0);
);
A
);
-- Part 2: Possible Edges of a Barile-Macchia Matching --
possibleEdges = method(Dispatch => Thing)
possibleEdges(Sequence) := List => S -> (
A=possibleEdgesWithPosition S;
B={};
for i from 0 to #A-1 do(
B=append(B,delete (A_i_0, A_i));
);
return B;
)
-----------------------------------------
--Barile-Macchia Matching-
-----------------------------------------
bMMatching = method(Dispatch => Thing)
bMMatching(Sequence) := List => S -> (
A = possibleEdgesWithPosition S;
groupedA = hashTable apply(A, i->(i_2, select(A,j->j_2==i_2)));
minA = applyValues(groupedA, i-> min i);
Bridge = apply(values minA, i->drop(i,1));
Bridge
);
-----------------------------------------
--isBridge Friendly-
-----------------------------------------
isBridgeFriendly = method(Dispatch => Thing)
isBridgeFriendly(Sequence) := List => S -> (
A = possibleEdges S;
B = bMMatching S;
A==B
);
-----------------------------------------
--Friendly Step-
-----------------------------------------
friendlyStep = method(Dispatch => Thing)
friendlyStep(Sequence) := List => S -> (
A = possibleEdges S;
B = bMMatching S;
{B, A==B}
);
-----------------------------------------
--Bridge Friendly List-
-----------------------------------------
bridgeFriendlyList = method(TypicalValue => List)
bridgeFriendlyList(Ideal) := List => I -> (
-- take all permutations of S, find bMMatching, check if second component is true for any of them
orderings = permutations flatten entries gens I;
Bridges = apply(orderings, i-> {i}|friendlyStep(toSequence i)); --output is {S, M}
friendlies = select(Bridges, i -> i_2); --i_2 is Boolean so this will only select true guys
apply(friendlies, i->drop(i,-1))
);
-----------------------------------------
--Critical Barile-Macchia Cells -
-----------------------------------------
criticalBMCells = method(Dispatch => Thing)
criticalBMCells(Sequence) := List => S -> (
I = ideal S;
crit = allTaylorCells I;
n = #crit;
nonCrit = bMMatching(S);
for i from 0 to #nonCrit-1 do(
k = #nonCrit_i_0;
sigma1 = nonCrit_i_0;
sigma2 = nonCrit_i_1;
crit1 = crit_(n-k);
crit2 = crit_(n-k+1);
crit1 = delete(sigma1, crit1);
crit2 = delete(sigma2, crit2);
crit = replace(n-k, crit1, crit);
crit = replace(n-k+1, crit2, crit);
);
crit
);
-----------------------------------------
--Barile-Macchia Rank -
-----------------------------------------
bMRanks = method(Dispatch => Thing)
bMRanks(Sequence) := List => S -> (
crit = criticalBMCells(S);
n = #crit;
rankList = {1};
for i from 0 to (n-1) do (
rankList = append(rankList, #crit_(n-i-1) );
);
rankList
);
-----------------------------------------------------------
-----------------------------------------------------------
-- Main Lyubeznik resolution functions
-----------------------------------------------------------
-----------------------------------------------------------
-----------------------------------------
--Lyubeznik Bridge -
-----------------------------------------
lyubeznikBridge = method(TypicalValue => List)
lyubeznikBridge(List,Sequence) := RingElement => (L,S) ->(
if #L<2 then print "The Taylor cell does not contain a Lyubeznik
bridge"
else A={};
for i from 0 to #S-1 do(
B=S_i;
L=delete(B,L);
if ( #L>0 and lcm L // B !=0) then (
A=B;
break
);
);
A
);
-----------------------------------------
--Lyubeznik Matching -
-----------------------------------------
lyubeznikMatching = method(Dispatch => Thing)
lyubeznikMatching(Sequence) := List => S -> (
I = ideal S;
Omega = flatten drop(allTaylorCells I, -2);
LMatching={};
while #Omega >0 do(
sigma = Omega_0;
if lyubeznikBridge(sigma,S) =!= {} then(
sb = lyubeznikBridge(sigma, S);
sigmaMinusSb = delete(sb, sigma);
LMatching = append(LMatching, (sigma, sigmaMinusSb));
Omega = delete(sigma, Omega);
Omega = delete(sigmaMinusSb, Omega);
)
else Omega = delete(sigma, Omega);
);
LMatching
);
-----------------------------------------
--Critical Lyubeznik Cells -
-----------------------------------------
criticalLyubeznikCells = method(Dispatch => Thing)
criticalLyubeznikCells(Sequence) := List => S -> (
I = ideal S;
crit = allTaylorCells I;
n = #crit;
L = lyubeznikMatching(S);
for i from 0 to #L-1 do(
k = #L_i_0;
sigma1 = L_i_0;
sigma2 = L_i_1;
crit1 = crit_(n-k);
crit2 = crit_(n-k+1);
crit1 = delete(sigma1, crit1);
crit2 = delete(sigma2, crit2);
crit = replace(n-k, crit1, crit);
crit = replace(n-k+1, crit2, crit);
);
crit
);
-----------------------------------------
--Lyubeznik Rank -
-----------------------------------------
lyubeznikRanks = method(Dispatch => Thing)
lyubeznikRanks(Sequence) := List => S -> (
crit = criticalLyubeznikCells(S);
n = #crit;
rankList = {1};
for i from 0 to (n-1) do (
rankList = append(rankList, #crit_(n-i-1) );
);
rankList
);
----------------------------------------
--Trimmed Lyubeznik resolution via Barile-Macchia algorithm
----------------------------------------
-----------------------------------------------
--Possible Edges of a Barile-Macchia Matching of the Lyubeznik Complex-
-----------------------------------------------
possibleTrimmedEdges = method(TypicalValue => List)
possibleTrimmedEdges(Sequence, Sequence) := List => (S1,S2) -> (
B= criticalLyubeznikCells S1;
T= select(B,j->j=!={});
Sigma = drop(T, -2);
Omega = flatten drop(T, -2);
A={};
i = 0;
j = 0;
while #Omega >0 do(
sigma = Sigma_i_j;
if isSubset({sigma}, Omega) then(
if bridge sigma =!= {} then(
sb = smallestBridge(sigma, S2);
sigmaMinusSb = delete(sb, sigma);
A = append(A, (position(S2, k-> sb==k), sigma, sigmaMinusSb));
Omega = delete(sigma, Omega);
Omega = delete(sigmaMinusSb, Omega);
)
else Omega = delete(sigma, Omega);
);
if #(Sigma_i)> j+1 then j = j+1 else(i = i+1; j = 0);
);
A
);
-----------------------------------------------
--Trimmed Barile-Macchia Matching of the Lyubeznik Complex
-----------------------------------------------
trimmedMatching = method(TypicalValue => List)
trimmedMatching(Sequence, Sequence) := List => (S1,S2) -> (
A = possibleTrimmedEdges(S1,S2);
groupedA = hashTable apply(A, i->(i_2, select(A,j->j_2==i_2)));
minA = applyValues(groupedA, i-> min i);
Bridge = apply(values minA, i->drop(i,1));
Bridge
);
-----------------------------------------------
--Critical Cells of the Trimmed Lyubeznik Complex
-----------------------------------------------
criticalTrimmedCells = method(TypicalValue => List)
criticalTrimmedCells(Sequence, Sequence) := List => (S1,S2) -> (
crit = criticalLyubeznikCells S1;
n = #crit;
nonCrit = trimmedMatching(S1,S2);
for i from 0 to #nonCrit-1 do(
k = #nonCrit_i_0;
sigma1 = nonCrit_i_0;
sigma2 = nonCrit_i_1;
crit1 = crit_(n-k);
crit2 = crit_(n-k+1);
crit1 = delete(sigma1, crit1);
crit2 = delete(sigma2, crit2);
crit = replace(n-k, crit1, crit);
crit = replace(n-k+1, crit2, crit);
);
crit
);
-----------------------------------------------
--Trimmed Rank of the Lyubeznik Complex
-----------------------------------------------
trimmedRanks = method(TypicalValue => List)
trimmedRanks(Sequence, Sequence) := List => (S1,S2) -> (
crit = criticalTrimmedCells(S1,S2);
n = #crit;
rankList = {1};
for i from 0 to (n-1) do (
rankList = append(rankList, #crit_(n-i-1) );
);
rankList
);
----------------------------------------
--Documentation
----------------------------------------
beginDocumentation()
doc///
Node
Key
MorseResolutions
Headline
A package for working with Morse resolutions of monomial ideals
Description
Text
{\em MorseResolutions} package enables computations for Morse resolutions of monomial ideals.
In particular, this package allows computations for the two major classes of Morse resolutions:
Barile-Macchia resolutions from [CK] and Lyubeznik resolutions from [BW]. Morse resolutions are
introduced in [BW] and induced by homogeneous acyclic matchings using discrete Morse theory.
This package constructs two classes of homogeneous acyclic matchings (Barile-Macchia matchings and Lyubeznik matchings)
of a monomial ideal $I$ with respect to a total order on its minimal generators. These matchings induce Barile-Macchia
resolutions and Lyubeznik resolutions. We use Algorithm 3.6 [CK] to construct the Barile-Macchia matching function.
Similarly, we use the matching from Theorem 3.2 [BW] to construct the Lyubeznik matching function. The package
also contains functions for computing the ranks of Barile-Macchia resolutions and Lyubeznik resolutions induced
by the Barile-Macchia matchings and Lyubeznik matchings, respectively.
This package also contains procedures to check bridge-friendliness of monomial ideals as described
in Definition 2.24 [CK].
In [CK], Barile-Macchia algorithm are applied to the Taylor complex of a monomial ideal. Instead of the Taylor complex,
one can apply the Barile-Macchia algorithm to a simplicial complex that supports a free resolution of $I$ by [BW].
This package contains a function that computes the Barile-Macchia matching of a Lyubeznik complex, a simplicial complex
that supports a free resolution of $I$ with respect to a fixed total order $<$ on the minimal generating set of $I$.
The goal of this work was primarily to help compute examples in the paper [CK]. This is a work in progress and the
authors are working to improve the functionality of this package. All suggestions and contributions are welcome.
Here is a typical use of this package. We create an ideal in 4 variables with the total order described
in the sequence $S$.
Acknowledgement
We thank Jeremy Dewar for helpful discussions.
References
[CK] T. Chau and S. Kara, Barile-Macchia Resolutions. Preprint, @arXiv "2211.04640"@ (2022).
[BW] E. Batzies and V. Welker, Discrete Morse theory for cellular resolutions, J. Reine Angew. Math. 543 (2002).
Subnodes
taylorCell
allTaylorCells
bridge
smallestBridge
possibleEdgesWithPositions
possibleEdges
bMMatching
bridgeFriendly
criticalBMCells
bMRanks
lyubeznikBridge
lyubeznikMatching
criticalLyubeznikCells
lyubeznikRanks
possibleTrimmedEdges
trimmedMatching
criticalTrimmedCells
trimmedRanks
///
doc///
Node
Key
taylorCell
(taylorCell, Ideal, ZZ)
Headline
prints all subsets of a fixed cardinality $n$ of a minimal generating set of the given monomial ideal $I$
Usage
taylorCell(I,n)
Inputs
I: Ideal
n: ZZ
Outputs
:List
a list that consists of all subsets of a minimal monomial generating set of $I$ with cardinality $n$
Description
Text
Given a monomial ideal $I$ and an integer $n$, returns cardinality $n$ subsets of minimal generators of $I$. In other words,
it returns all $(n-1)$-faces of the Taylor complex of $I$.
Example
R=QQ[a,b,c,d];
S = (c*d, b*c, a*b, a^2*d);
I=ideal(S);
taylorCell(I,2)
SeeAlso
allTaylorCells
///
doc ///
Node
Key
allTaylorCells
(allTaylorCells, Ideal)
Headline
prints all subsets of a minimal generating set of the given monomial ideal $I$
Usage
allTaylorCells(I)
Inputs
I: Ideal
Outputs
:List
a list of all subsets of a minimal generating set of I
Description
Text
Given an ideal $I$, returns all subsets of a minimal generating set of $I$. In other words, it returns all faces of
the Taylor complex of $I$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a^2*d);
I=ideal(S);
allTaylorCells(I)
SeeAlso
taylorCell
///
-----------------------------
-- Barile-Macchia Documentation
-----------------------------
doc ///
Node
Key
bridge
(bridge, List)
Headline
prints all bridges of a list of monomials
Usage
bridge(L)
Inputs
L: List
a list of monomials
Outputs
:List
if no bridge exists, returns the empty list {}, otherwise returns a list containing all bridges of $L$
Description
Text
Given a list of monomials $L$, returns all bridges of $L$.
A monomial $m$ in $L$ is called a bridge of $L$ if the lcm of L does not change after removing $m$.
Example
R=QQ[a,b,c,d,e];
L={a*b,a*d,a*e};
bridge(L)
SeeAlso
smallestBridge
///
doc ///
Node
Key
smallestBridge
(smallestBridge, List, Sequence)
Headline
prints the smallest bridge of a list of monomials with respect to a total order
Usage
smallestBridge(L,S)
Inputs
L: List
a list of monomials
S: Sequence
a sequence of monomials that contain monomials in L
a total order on a set of monomials that contain monomials in L
Outputs
:RingElement
Description
Text
Given a list of monomials $L$, returns the smallest bridge of $L$ with respect to the total order $S$.
Example
R=QQ[a,b,c,d,e];
L={a*b,b*c,c*d,d*e};
S=(d*e,c*d,b*c,a*b);
smallestBridge(L,S)
SeeAlso
bridge
///
doc ///
Node
Key
possibleEdgesWithPositions
(possibleEdgesWithPositions, Sequence)
Headline
prints triples that contain positions of the corresponding smallest bridges associated to possible edges and possible edges
of the Taylor complex of a monomial ideal with respect to a given total order monomial ideal with respect to a given total
order before Step 3 of Algorithm 2.6 in [CK].
Usage
possibleEdgesWithPositions(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Given a monomial ideal $I$, let $<$ be a total order on its minimal generating set $G(I) = \{m_1,\ldots,m_n\}$.
The total order $<$ is recorded as a sequence $S$ of $\{m_1,\ldots,m_n\}$.
Let $G$ be the directed graph obtained from the Taylor complex of $I$. Directed edges of $G$ are of the
form $(\sigma,\tau)$ where $\tau\subset \sigma \subset G(I)$ and $|\tau|=|\sigma|-1$.
Consider a collection of directed edges $A$ in $G$. We call $A$ an acyclic matching in $G$ if
a) $A$ is a matching in $G$, i.e. none of the two edges in $A$ share vertices, and
b) there is no directed cycle in the graph obtained from $G$ by reversing the edges in $A$.
An acyclic matching $A$ is called homogeneous if $\lcm(\sigma)=\lcm(\tau)$ for each directed edge $(\sigma,\tau) \in A$.
A collection of directed edges of $G$ produced by Algorithm 2.6 in [CK] is a homogeneous acyclic matching in $G$ by
Theorem 2.8 from [CK]. A matching that is produced by Algorithm 2.6 in [CK] is called a Barile-Macchia matching of $I$ or, more
precisely, a Barile-Macchia matching of the Taylor complex of $I$. The output of this algorithm depends on a choice of total
order on $G(I)$. In other words, each total order produces a Barile-Macchia matching of $I$, and it is worth noting that
these Barile-Macchia matchings are not necessarily the same.
The edges in a Barile-Macchia matching are obtained by considering directed edges $(\sigma,\tau)$ where $\tau$ is obtained from
$\sigma$ by removing the smallest bridge of $\sigma$ with respect to $S$. Steps 1) and 2) of the algorithm puts together
such direct edges while making sure the source vertices of the considered edges are all distinct. These two steps can
create two directed edges $(\sigma,\tau)$ and $(\sigma',\tau')$ such that $\tau=\tau'$. In other words, after removing
the smallest bridges of $\sigma$ and $\sigma'$, it is possible to obtain the same target vertex. Step 3) of the algorithm
picks only one directed edge $(\sigma,\tau)$ among those in a way that the smallest bridge of $\sigma$ is smaller than
the smallest bridges of all other source vertices whose targets overlap.
The edges that are obtained from Steps 1) and 2) of the algorithm are called possible edges of the Barile-Macchia matching of the
Taylor complex of $I$ with respect to $S$. Given a total order $S$, this function returns to the list of triples
$(i, \sigma, \sigma \setminus \sbridge(\sigma))$, where $i$ is the position of the smallest bridge of $\sigma \subseteq \G(I)$
with respect to a total order $S$ on $\G(I)$ and collection of all $(\sigma \setminus \sbridge(\sigma))$ is the possible edges of $I$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
possibleEdgesWithPositions(S)
SeeAlso
bMMatching
possibleTrimmedEdges
possibleEdges
///
doc ///
Node
Key
possibleEdges
(possibleEdges, Sequence)
Headline
prints all edges of a Barile-Macchia matching of the Taylor complex of a monomial ideal with respect to a given total order
before Step 3 of Algorithm 2.6 in [CK]
Usage
possibleEdges(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Given a monomial ideal $I$ and a given a total order $S$, this function returns to the list of potential edges
of the Barile-Macchia matching of the Taylor complex of $I$ with respect to $S$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
possibleEdges(S)
SeeAlso
bMMatching
possibleEdgesWithPositions
possibleTrimmedEdges
///
doc ///
Node
Key
bMMatching
(bMMatching, Sequence)
Headline
prints all edges of a Barile-Macchia matching of the Taylor complex of a monomial ideal with respect to a given total order
Usage
bMMatching(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Given a total order $S$ on $G(I)$ for a monomial ideal $I$, this function returns the Barile-Macchia matching with respect
to $S$ of the Taylor complex of $I$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
bMMatching(S)
SeeAlso
possibleEdges
lyubeznikMatching
trimmedMatching
///
doc ///
Key
isBridgeFriendly
(isBridgeFriendly, Sequence)
Headline
checks whether a monomial ideal $I$ with respect to a total order $S$ on $G(I)$ is bridge-friendly with respect to $S$
Usage
isBridgeFriendly(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:Boolean
Description
Text
A monomial ideal $I$ is called bridge-friendly with respect to a total order $S$ on $G(I)$ if Step 3
of Algorithm 2.6 [CK] is redundant with respect to $S$, i.e., possibleEdges(S)=bMMatching(S).
This function tests whether $I$ is bridge-friendly with respect to the given total order $S$ on $G(I)$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
isBridgeFriendly(S)
SeeAlso
possibleEdges
bMMatching
///
doc ///
Node
Key
friendlyStep
(friendlyStep, Sequence)
Headline
prints a list such that the first entry in the list is the Barile-Macchia matching of a monomial ideal $I$ with
respect to a given total order $S$ on $G(I)$ and the second entry is a Boolean to check if $I$ is
bridge-friendly with respect to $S$
Usage
friendlyStep(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Let $I$ be a monomial ideal with the given total order $S$ on $G(I)$. This function returns to a pair where
the first element is the Barile-Macchia matching of $I$ with respect to $S$ and the second element in the list is
true or false depending on whether Barile-Macchia matching coincides with possible edges of $I$ with respect to $S$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
friendlyStep(S)
SeeAlso
possibleEdges
bMMatching
isBridgeFriendly
///
doc ///
Node
Key
bridgeFriendlyList
(bridgeFriendlyList, Ideal)
Headline
prints a list of all Barile-Macchia matchings of the Taylor complex of a given monomial ideal with respect to total orders
for which $I$ is bridge-friendly with respect to each of those total orders.
Usage
bridgeFriendlyList(I)
Inputs
I: Ideal
a monomial ideal
Outputs
:List
if no order exists, returns {}, otherwise returns a list containing all total orders on $G(I)$ which work
Description
Text
Given a monomial ideal $I$, this method computes all possible total orders $S$ on $G(I)$ with respect to which the ideal
$I$ is bridge-friendly. In particular, the output of this function is a list of pairs ${S, bMMatching(S)}$ where
$I$ is bridge-friendly with respect to $S$.
Example
R=QQ[a,b,c,d];
I=ideal(a*b,b*c,c*a);
bridgeFriendlyList(I)
Text
The ideal in the following example is not bridge-friendly with respect to any total order. So, the output is {}.
Example
R=QQ[a,b,c,d];
I=ideal(c*d, b*c, a*b, a*d);
bridgeFriendlyList(I)
Caveat
For a monomial ideal $I$ with $G(I)= \{m_1,\ldots,m_n\}$, there are $n!$ possible total orders on $G(I)$, so this
function can be computationally expensive.
SeeAlso
possibleEdge
bMMatching
isBridgeFriendly
friendlyStep
///
doc ///
Node
Key
criticalBMCells
(criticalBMCells, Sequence)
Headline
prints all $A$-critical cells of the Taylor complex of a monomial ideal where $A$ is the Barile-Macchia matching of a monomial
ideal $I$ with respect to a given total order on $G(I)$.
Usage
criticalBMCells(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Let $I$ be the monomial ideal and $S$ be a total order on $G(I)$. Let $A$ be a homogeneous acyclic matching of $G$,
the directed graph obtained from the Taylor complex of $I$. A subset of $G(I)$ is called an $A$-critical cell of the
Taylor complex of $I$ if it does not appear in $A$.
Given a total order $S$ on $G(I)$, this function returns to a list of all $A$-critical cells where $A$ is the Barile-Macchia
matching of the Taylor complex of $I$ with respect to $S$.
Example
R=QQ[a,b,c,d];
S = (c*d, b*c, a*b, a*d);
criticalBMCells(S)
SeeAlso
bMMatching
criticalLyubeznikCells
criticalTrimmedCells
///
doc ///
Node
Key
bMRanks
(bMRanks, Sequence)
Headline
prints the ranks of the free modules in the Barile-Macchia resolution of $R/I$ with respect to a total
order on $G(I)$ where $I$ is a monomial ideal
Usage
bMRanks(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Let $G$ be the directed graph obtained from the Taylor complex of $I$. Each homogeneous acyclic matching on $G_X$ induces
a free resolution of $R/I$ by [BW]. More precisely, if $A$ is a homogeneous acyclic matching on $G_X$, then there exists a
CW-complex $X_A$ which supports a free resolution of $I$. The $i$-cells of $X_A$ are in one-to-one correspondence with
the $A$-critical cells of $X$ of cardinality $i+1$. The cellular resolution supported on $X_A$ is $\mathcal{F}_A$ where
$(\mathcal{F}_A)_i$ is the free $R$-module with a basis indexed by all critical subsets of cardinality $i$.
Given a total order $S$ on $G(I)$ for a monomial ideal $I$, this function returns to ranks of the free modules of the
Barile-Macchia resolution of $I$ with respect to $S$. The output is a list of numbers where the $i^{th}$ number in the
list is the rank of $(\mathcal{F}_A)_i$.
Example
R=QQ[a,b,c,d];
S = (c*d, b*c, a*b, a*d);
bMRanks(S)
References
[BW] E. Batzies and V. Welker, Discrete Morse theory for cellular resolutions, J. Reine Angew. Math. 543 (2002).
SeeAlso
bMMatching
criticalBMCells
criticalLyubeznikCells
criticalTrimmedCells
///
-----------------------------
-- Lyubeznik Documentation
-----------------------------
doc ///
Node
Key
lyubeznikBridge
(lyubeznikBridge, List, Sequence)
Headline
prints the Lyubeznik bridge of a list of monomials with respect to a total order
Usage
lyubeznikBridge(L,S)
Inputs
L: List
a list of monomials
S: Sequence
a sequence of all monomials in L
a total order on a set of monomials in L
Outputs
:RingElement
Description
Text
Given a list of monomials $L$, returns the Lyubeznik bridge of $L$ with respect to the total
order $S$.
Example
R=QQ[x_1..x_8];
S=(x_7*x_8,x_2*x_3*x_8,x_1*x_2*x_7,x_1*x_2*x_5,x_2*x_3*x_5*x_6,x_1*x_2*x_3*x_4);
L= {x_1*x_2*x_5,x_2*x_3*x_5*x_6,x_1*x_2*x_3*x_4};
lyubeznikBridge(L,S)
SeeAlso
smallestBridge
///
doc ///
Node
Key
lyubeznikMatching
(lyubeznikMatching, Sequence)
Headline
prints all edges of a Lyubeznik matching of a monomial ideal generated by $S$
Usage
lyubeznikMatching(S)
Inputs
S: Sequence
a sequence of monomials
a total order on a set of monomials
Outputs
:List
Description
Text
Let $I$ be a monomial ideal with a total order $S$ on $G(I)$ and $G$ be the directed graph obtained from
the Taylor complex of $I$. We call the homogeneous acyclic matching $A$ from Theorem 3.2 [BW] a Lyubeznik
matching of $I$ with respect to a total order $S$.
Given a total order $S$ on $G(I)$, this function returns to the Lyubeznik matching of the Taylor complex of
$I$ with respect to $S$.
Example
R=QQ[a,b,c,d]
S = (c*d, b*c, a*b, a*d);
lyubeznikMatching(S)
References
[BW] E. Batzies and V. Welker, Discrete Morse theory for cellular resolutions, J. Reine Angew. Math. 543 (2002).
SeeAlso
bMMatching
trimmedMatching
///