SlideShare a Scribd company logo
1 of 21
Download to read offline
Feasible Combinatorial Matrix Theory
Ariel Fernandez & Michael Soltys
August 29, 2013
Comb Matrix - Soltys MFCS’13 IST Austria Title - 1/21
Statistical Archeology: sequence dating (Flinders Petrie, 1899)
900 pre-dynastic Egyptian graves containing 800 representatives of
pottery.
The “graves-versus-varieties” matrix contains vast amount of
information, such as sequential ordering.
[Kendall 1969]
Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 2/21
Paleogenomics: DNA sequence organization of ancient living
organisms using similarities and differences between chromosomes
of extant organisms.
[Chauve et al 2008]
Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 3/21
Consecutive-ones Property: C1P
Consider a slight relaxation, (k, δ)-C1P: each row has at most k
blocks of 1s and the gap between any two blocks is at most δ.
So (1, 0)-C1P is C1P, and deciding if an A has (k, δ)-C1P is:
polytime for (1, 0)
NP-hard for every k ≥ 2, δ ≥ 1 except (2, 1)
What about (2, 1)? [Patterson 2012]
Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 4/21
K¨onig’s Min-Max
0
1 0 1 1
1 0
1
00
0
1
1 0
00
Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 5/21
Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 6/21
Problems
Cover(A, α):
∀i, j ≤ r(A)(A(i, j) = 1 → α(1, i) = 1 ∨ α(2, j) = 1)
MinCover(A, α):
Cover(A, α) ∧ ∀α ≤ c(α)(Cover(A, α ) → Σα ≥ Σα)
KMM(A, α, β):
MinCover(A, α) ∧ MaxSelect(A, β) → Σα = Σβ
a ΣB
1 formula.
But classical proof is ΠB
2 — is there a ΣB
1 proof?
Comb Matrix - Soltys MFCS’13 IST Austria Problem - 7/21
Related Theorems:
Menger’s: size of min cut equals max nr of disjoint s, t-paths
(“Min-Cut Max-Flow”)
Hall’s: ∀k ∈ [n] |Si1 ∪ . . . ∪ Sik
| ≥ k, then there exists a
System of Distinct Representatives.
Dilworth’s: Min nr of chains needed to partition a poset
equals size of max anti-chain of that poset.
Can they all be shown equivalent to KMM with ΣB
0 proofs?
Comb Matrix - Soltys MFCS’13 IST Austria Problem - 8/21
ΣB
1 Proof of KMM
Let lA be the min nr of lines necessary to cover A
Let oA be the max selection of ones in A
Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 9/21
0
1 0 1 1
1 0
1
00
0
1
1 0
00
lA=oA= 3
We want to show with ΣB
1 induction that oA = lA.
Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 10/21
LA uses ΣB
0 induction
LA oA ≤ lA
LA over Z is equivalent to VTC0
And oA ≤ lA follows more or less from the Pigeonhole Principle:
if we can select oA 1s, no two on the same line, then we shall
require at least lA lines to cover those 1s.
Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 11/21
∃LA oA ≥ lA
Showing oA ≥ lA is more difficult; we use ΣB
1 induction.
Lots of cases, but the interesting case is:
0
where we reduce the general case to the case of the blue matrix
whose cover requires as many lines as rows.
Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 12/21
00 00 00 0 0 0 0 0 0
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 13/21
10 00 00 0 0 0 0 0 0
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 14/21
0
0 00 00 0 0 0 0 0 01
0 0 0 1 0 0 0 0 0
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 15/21
1
0 00 00 0 0 0 0 0 01
0 0 0 1 0 0 0 0 0
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 16/21
1
0 00 00 0 0 0 0 0 01
0 0 0 1 0 0 0 0 0
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 17/21
H
1 1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
A
B
C
D
E
FG
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 18/21
J
1 1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
H
1
1
Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 19/21
ΣB
0 Proof of Equivalence
For example, ΣB
0 proof of Menger → KMM
yx
Left graph has a matching of size k ⇐⇒
Right graph has k disjoint {x, y}-paths
Left graph has a cover of size k ⇐⇒
Right graph has an {x, y}-cut of size k
KMM → Meng
complicated,
[Aharoni 1983]
Comb Matrix - Soltys MFCS’13 IST Austria Proof of equivalences - 20/21
Some open problems
Frankl’s Theorem: t a positive integer, and m ≤ n(2t −1)
t ; if A
is m × n, and its rows are distinct, then there exists a column
that when deleted, the resulting matrix has at most 2t−1 − 1
pairs of equal rows. (Bondy’s Theorem when t = 1.)
Complexity of decompositions: A = P1 + P2 + · · · + Pn + X;
n boys and n girls, each boy introduced to exactly k girls and
vice versa. Compute a pairing where each boy & girl has been
previously introduced.
Projective Geometry









1 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 1 1
0 1 0 1 0 1 0
0 1 0 0 1 0 1
0 0 1 1 0 0 1
0 0 1 0 1 1 0









Desargues Thm
Comb Matrix - Soltys MFCS’13 IST Austria Conclusion - 21/21

More Related Content

Viewers also liked

La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004Michael Soltys
 
Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Michael Soltys
 
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Michael Soltys
 
Feasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationFeasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationMichael Soltys
 
The Proof Complexity of Linear Algebra - LICS 2002
The Proof Complexity of Linear Algebra - LICS 2002The Proof Complexity of Linear Algebra - LICS 2002
The Proof Complexity of Linear Algebra - LICS 2002Michael Soltys
 
Games on Posets - CiE 2008
Games on Posets - CiE 2008Games on Posets - CiE 2008
Games on Posets - CiE 2008Michael Soltys
 
Fair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisFair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisMichael Soltys
 
Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Michael Soltys
 
Forced repetitions over alphabet lists
Forced repetitions over alphabet listsForced repetitions over alphabet lists
Forced repetitions over alphabet listsMichael Soltys
 
How Safe is your Data?
How Safe is your Data?How Safe is your Data?
How Safe is your Data?Michael Soltys
 
Circuit Complexity of Shuffle - IWOCA 2013
Circuit Complexity of Shuffle - IWOCA 2013Circuit Complexity of Shuffle - IWOCA 2013
Circuit Complexity of Shuffle - IWOCA 2013Michael Soltys
 
An algorithmic view of Computer Science
An algorithmic view of Computer ScienceAn algorithmic view of Computer Science
An algorithmic view of Computer ScienceMichael Soltys
 
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005Feasible proofs of matrix identities with csanky's algorithm - CSL 2005
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005Michael Soltys
 

Viewers also liked (15)

La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004
 
Algorithms on Strings
Algorithms on StringsAlgorithms on Strings
Algorithms on Strings
 
Intro to Cryptography
Intro to CryptographyIntro to Cryptography
Intro to Cryptography
 
Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009
 
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
 
Feasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationFeasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentation
 
The Proof Complexity of Linear Algebra - LICS 2002
The Proof Complexity of Linear Algebra - LICS 2002The Proof Complexity of Linear Algebra - LICS 2002
The Proof Complexity of Linear Algebra - LICS 2002
 
Games on Posets - CiE 2008
Games on Posets - CiE 2008Games on Posets - CiE 2008
Games on Posets - CiE 2008
 
Fair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisFair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysis
 
Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System -
 
Forced repetitions over alphabet lists
Forced repetitions over alphabet listsForced repetitions over alphabet lists
Forced repetitions over alphabet lists
 
How Safe is your Data?
How Safe is your Data?How Safe is your Data?
How Safe is your Data?
 
Circuit Complexity of Shuffle - IWOCA 2013
Circuit Complexity of Shuffle - IWOCA 2013Circuit Complexity of Shuffle - IWOCA 2013
Circuit Complexity of Shuffle - IWOCA 2013
 
An algorithmic view of Computer Science
An algorithmic view of Computer ScienceAn algorithmic view of Computer Science
An algorithmic view of Computer Science
 
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005Feasible proofs of matrix identities with csanky's algorithm - CSL 2005
Feasible proofs of matrix identities with csanky's algorithm - CSL 2005
 

Similar to Feasible Combinatorial Matrix Theory - MFCS2013

Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Alexander Litvinenko
 
Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Alexander Litvinenko
 
Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Alexander Litvinenko
 
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...Alexander Litvinenko
 
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptx
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptxContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptx
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptxSajjadAnwar25
 
68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez
68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez
68th ICREA Colloquium "Results from the LHC Run II" by Mario MartínezICREA
 
ImagesContent· Corporate American Flag by Adbusters 
· .docx
ImagesContent· Corporate American Flag by Adbusters 
· .docxImagesContent· Corporate American Flag by Adbusters 
· .docx
ImagesContent· Corporate American Flag by Adbusters 
· .docxwilcockiris
 
PRINCIPLES OF COMBINATIONAL LOGIC-2
PRINCIPLES OF COMBINATIONAL LOGIC-2PRINCIPLES OF COMBINATIONAL LOGIC-2
PRINCIPLES OF COMBINATIONAL LOGIC-2Supanna Shirguppe
 
Euler circuits and dna sequencing by hybridization
Euler circuits and dna sequencing by hybridizationEuler circuits and dna sequencing by hybridization
Euler circuits and dna sequencing by hybridizationMountville Mills
 
A Review of Probability and its Applications Shameel Farhan new applied [Comp...
A Review of Probability and its Applications Shameel Farhan new applied [Comp...A Review of Probability and its Applications Shameel Farhan new applied [Comp...
A Review of Probability and its Applications Shameel Farhan new applied [Comp...shameel farhan
 
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...SEENET-MTP
 
Magnetic Materials Assignment Help
Magnetic Materials Assignment HelpMagnetic Materials Assignment Help
Magnetic Materials Assignment HelpEdu Assignment Help
 
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.lccausp
 
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...Varad Meru
 
Neil Lambert - From D-branes to M-branes
Neil Lambert - From D-branes to M-branesNeil Lambert - From D-branes to M-branes
Neil Lambert - From D-branes to M-branesSEENET-MTP
 

Similar to Feasible Combinatorial Matrix Theory - MFCS2013 (20)

Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...
 
Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...
 
Mechanics Materials Homework Help
Mechanics Materials Homework HelpMechanics Materials Homework Help
Mechanics Materials Homework Help
 
Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...Computation of electromagnetic fields scattered from dielectric objects of un...
Computation of electromagnetic fields scattered from dielectric objects of un...
 
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...
Computation of electromagnetic_fields_scattered_from_dielectric_objects_of_un...
 
Ch9
Ch9Ch9
Ch9
 
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptx
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptxContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptx
ContinuumordiscontinuumGSIorJRCimproved45minutesversion.pptx
 
68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez
68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez
68th ICREA Colloquium "Results from the LHC Run II" by Mario Martínez
 
ImagesContent· Corporate American Flag by Adbusters 
· .docx
ImagesContent· Corporate American Flag by Adbusters 
· .docxImagesContent· Corporate American Flag by Adbusters 
· .docx
ImagesContent· Corporate American Flag by Adbusters 
· .docx
 
PRINCIPLES OF COMBINATIONAL LOGIC-2
PRINCIPLES OF COMBINATIONAL LOGIC-2PRINCIPLES OF COMBINATIONAL LOGIC-2
PRINCIPLES OF COMBINATIONAL LOGIC-2
 
Euler circuits and dna sequencing by hybridization
Euler circuits and dna sequencing by hybridizationEuler circuits and dna sequencing by hybridization
Euler circuits and dna sequencing by hybridization
 
A Review of Probability and its Applications Shameel Farhan new applied [Comp...
A Review of Probability and its Applications Shameel Farhan new applied [Comp...A Review of Probability and its Applications Shameel Farhan new applied [Comp...
A Review of Probability and its Applications Shameel Farhan new applied [Comp...
 
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...
Sergey Sibiryakov "Galactic rotation curves vs. ultra-light dark matter: Impl...
 
Magnetic Materials Assignment Help
Magnetic Materials Assignment HelpMagnetic Materials Assignment Help
Magnetic Materials Assignment Help
 
Lecture 6
Lecture 6Lecture 6
Lecture 6
 
Minimum spanning tree
Minimum spanning treeMinimum spanning tree
Minimum spanning tree
 
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.
“Solving QCD: from BG/P to BG/Q”. Prof. Dr. Attilio Cucchieri – IFSC/USP.
 
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passin...
 
Neil Lambert - From D-branes to M-branes
Neil Lambert - From D-branes to M-branesNeil Lambert - From D-branes to M-branes
Neil Lambert - From D-branes to M-branes
 
Mechanics Materials Homework Help
Mechanics Materials Homework HelpMechanics Materials Homework Help
Mechanics Materials Homework Help
 

Recently uploaded

Drug Information Services- DIC and Sources.
Drug Information Services- DIC and Sources.Drug Information Services- DIC and Sources.
Drug Information Services- DIC and Sources.raviapr7
 
How to Show Error_Warning Messages in Odoo 17
How to Show Error_Warning Messages in Odoo 17How to Show Error_Warning Messages in Odoo 17
How to Show Error_Warning Messages in Odoo 17Celine George
 
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdf
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdfP4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdf
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdfYu Kanazawa / Osaka University
 
How to Manage Cross-Selling in Odoo 17 Sales
How to Manage Cross-Selling in Odoo 17 SalesHow to Manage Cross-Selling in Odoo 17 Sales
How to Manage Cross-Selling in Odoo 17 SalesCeline George
 
CapTechU Doctoral Presentation -March 2024 slides.pptx
CapTechU Doctoral Presentation -March 2024 slides.pptxCapTechU Doctoral Presentation -March 2024 slides.pptx
CapTechU Doctoral Presentation -March 2024 slides.pptxCapitolTechU
 
A gentle introduction to Artificial Intelligence
A gentle introduction to Artificial IntelligenceA gentle introduction to Artificial Intelligence
A gentle introduction to Artificial IntelligenceApostolos Syropoulos
 
Work Experience for psp3 portfolio sasha
Work Experience for psp3 portfolio sashaWork Experience for psp3 portfolio sasha
Work Experience for psp3 portfolio sashasashalaycock03
 
Protein Structure - threading Protein modelling pptx
Protein Structure - threading Protein modelling pptxProtein Structure - threading Protein modelling pptx
Protein Structure - threading Protein modelling pptxvidhisharma994099
 
10 Topics For MBA Project Report [HR].pdf
10 Topics For MBA Project Report [HR].pdf10 Topics For MBA Project Report [HR].pdf
10 Topics For MBA Project Report [HR].pdfJayanti Pande
 
KARNAADA.pptx made by - saransh dwivedi ( SD ) - SHALAKYA TANTRA - ENT - 4...
KARNAADA.pptx  made by -  saransh dwivedi ( SD ) -  SHALAKYA TANTRA - ENT - 4...KARNAADA.pptx  made by -  saransh dwivedi ( SD ) -  SHALAKYA TANTRA - ENT - 4...
KARNAADA.pptx made by - saransh dwivedi ( SD ) - SHALAKYA TANTRA - ENT - 4...M56BOOKSTORE PRODUCT/SERVICE
 
The Stolen Bacillus by Herbert George Wells
The Stolen Bacillus by Herbert George WellsThe Stolen Bacillus by Herbert George Wells
The Stolen Bacillus by Herbert George WellsEugene Lysak
 
How to Make a Field read-only in Odoo 17
How to Make a Field read-only in Odoo 17How to Make a Field read-only in Odoo 17
How to Make a Field read-only in Odoo 17Celine George
 
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptxSandy Millin
 
3.21.24 The Origins of Black Power.pptx
3.21.24  The Origins of Black Power.pptx3.21.24  The Origins of Black Power.pptx
3.21.24 The Origins of Black Power.pptxmary850239
 
What is the Future of QuickBooks DeskTop?
What is the Future of QuickBooks DeskTop?What is the Future of QuickBooks DeskTop?
What is the Future of QuickBooks DeskTop?TechSoup
 
In - Vivo and In - Vitro Correlation.pptx
In - Vivo and In - Vitro Correlation.pptxIn - Vivo and In - Vitro Correlation.pptx
In - Vivo and In - Vitro Correlation.pptxAditiChauhan701637
 
HED Office Sohayok Exam Question Solution 2023.pdf
HED Office Sohayok Exam Question Solution 2023.pdfHED Office Sohayok Exam Question Solution 2023.pdf
HED Office Sohayok Exam Question Solution 2023.pdfMohonDas
 
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRA
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRADUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRA
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRATanmoy Mishra
 
How to Solve Singleton Error in the Odoo 17
How to Solve Singleton Error in the  Odoo 17How to Solve Singleton Error in the  Odoo 17
How to Solve Singleton Error in the Odoo 17Celine George
 

Recently uploaded (20)

Drug Information Services- DIC and Sources.
Drug Information Services- DIC and Sources.Drug Information Services- DIC and Sources.
Drug Information Services- DIC and Sources.
 
How to Show Error_Warning Messages in Odoo 17
How to Show Error_Warning Messages in Odoo 17How to Show Error_Warning Messages in Odoo 17
How to Show Error_Warning Messages in Odoo 17
 
March 2024 Directors Meeting, Division of Student Affairs and Academic Support
March 2024 Directors Meeting, Division of Student Affairs and Academic SupportMarch 2024 Directors Meeting, Division of Student Affairs and Academic Support
March 2024 Directors Meeting, Division of Student Affairs and Academic Support
 
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdf
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdfP4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdf
P4C x ELT = P4ELT: Its Theoretical Background (Kanazawa, 2024 March).pdf
 
How to Manage Cross-Selling in Odoo 17 Sales
How to Manage Cross-Selling in Odoo 17 SalesHow to Manage Cross-Selling in Odoo 17 Sales
How to Manage Cross-Selling in Odoo 17 Sales
 
CapTechU Doctoral Presentation -March 2024 slides.pptx
CapTechU Doctoral Presentation -March 2024 slides.pptxCapTechU Doctoral Presentation -March 2024 slides.pptx
CapTechU Doctoral Presentation -March 2024 slides.pptx
 
A gentle introduction to Artificial Intelligence
A gentle introduction to Artificial IntelligenceA gentle introduction to Artificial Intelligence
A gentle introduction to Artificial Intelligence
 
Work Experience for psp3 portfolio sasha
Work Experience for psp3 portfolio sashaWork Experience for psp3 portfolio sasha
Work Experience for psp3 portfolio sasha
 
Protein Structure - threading Protein modelling pptx
Protein Structure - threading Protein modelling pptxProtein Structure - threading Protein modelling pptx
Protein Structure - threading Protein modelling pptx
 
10 Topics For MBA Project Report [HR].pdf
10 Topics For MBA Project Report [HR].pdf10 Topics For MBA Project Report [HR].pdf
10 Topics For MBA Project Report [HR].pdf
 
KARNAADA.pptx made by - saransh dwivedi ( SD ) - SHALAKYA TANTRA - ENT - 4...
KARNAADA.pptx  made by -  saransh dwivedi ( SD ) -  SHALAKYA TANTRA - ENT - 4...KARNAADA.pptx  made by -  saransh dwivedi ( SD ) -  SHALAKYA TANTRA - ENT - 4...
KARNAADA.pptx made by - saransh dwivedi ( SD ) - SHALAKYA TANTRA - ENT - 4...
 
The Stolen Bacillus by Herbert George Wells
The Stolen Bacillus by Herbert George WellsThe Stolen Bacillus by Herbert George Wells
The Stolen Bacillus by Herbert George Wells
 
How to Make a Field read-only in Odoo 17
How to Make a Field read-only in Odoo 17How to Make a Field read-only in Odoo 17
How to Make a Field read-only in Odoo 17
 
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx
2024.03.23 What do successful readers do - Sandy Millin for PARK.pptx
 
3.21.24 The Origins of Black Power.pptx
3.21.24  The Origins of Black Power.pptx3.21.24  The Origins of Black Power.pptx
3.21.24 The Origins of Black Power.pptx
 
What is the Future of QuickBooks DeskTop?
What is the Future of QuickBooks DeskTop?What is the Future of QuickBooks DeskTop?
What is the Future of QuickBooks DeskTop?
 
In - Vivo and In - Vitro Correlation.pptx
In - Vivo and In - Vitro Correlation.pptxIn - Vivo and In - Vitro Correlation.pptx
In - Vivo and In - Vitro Correlation.pptx
 
HED Office Sohayok Exam Question Solution 2023.pdf
HED Office Sohayok Exam Question Solution 2023.pdfHED Office Sohayok Exam Question Solution 2023.pdf
HED Office Sohayok Exam Question Solution 2023.pdf
 
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRA
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRADUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRA
DUST OF SNOW_BY ROBERT FROST_EDITED BY_ TANMOY MISHRA
 
How to Solve Singleton Error in the Odoo 17
How to Solve Singleton Error in the  Odoo 17How to Solve Singleton Error in the  Odoo 17
How to Solve Singleton Error in the Odoo 17
 

Feasible Combinatorial Matrix Theory - MFCS2013

  • 1. Feasible Combinatorial Matrix Theory Ariel Fernandez & Michael Soltys August 29, 2013 Comb Matrix - Soltys MFCS’13 IST Austria Title - 1/21
  • 2. Statistical Archeology: sequence dating (Flinders Petrie, 1899) 900 pre-dynastic Egyptian graves containing 800 representatives of pottery. The “graves-versus-varieties” matrix contains vast amount of information, such as sequential ordering. [Kendall 1969] Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 2/21
  • 3. Paleogenomics: DNA sequence organization of ancient living organisms using similarities and differences between chromosomes of extant organisms. [Chauve et al 2008] Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 3/21
  • 4. Consecutive-ones Property: C1P Consider a slight relaxation, (k, δ)-C1P: each row has at most k blocks of 1s and the gap between any two blocks is at most δ. So (1, 0)-C1P is C1P, and deciding if an A has (k, δ)-C1P is: polytime for (1, 0) NP-hard for every k ≥ 2, δ ≥ 1 except (2, 1) What about (2, 1)? [Patterson 2012] Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 4/21
  • 5. K¨onig’s Min-Max 0 1 0 1 1 1 0 1 00 0 1 1 0 00 Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 5/21
  • 6. Comb Matrix - Soltys MFCS’13 IST Austria Introduction - 6/21
  • 7. Problems Cover(A, α): ∀i, j ≤ r(A)(A(i, j) = 1 → α(1, i) = 1 ∨ α(2, j) = 1) MinCover(A, α): Cover(A, α) ∧ ∀α ≤ c(α)(Cover(A, α ) → Σα ≥ Σα) KMM(A, α, β): MinCover(A, α) ∧ MaxSelect(A, β) → Σα = Σβ a ΣB 1 formula. But classical proof is ΠB 2 — is there a ΣB 1 proof? Comb Matrix - Soltys MFCS’13 IST Austria Problem - 7/21
  • 8. Related Theorems: Menger’s: size of min cut equals max nr of disjoint s, t-paths (“Min-Cut Max-Flow”) Hall’s: ∀k ∈ [n] |Si1 ∪ . . . ∪ Sik | ≥ k, then there exists a System of Distinct Representatives. Dilworth’s: Min nr of chains needed to partition a poset equals size of max anti-chain of that poset. Can they all be shown equivalent to KMM with ΣB 0 proofs? Comb Matrix - Soltys MFCS’13 IST Austria Problem - 8/21
  • 9. ΣB 1 Proof of KMM Let lA be the min nr of lines necessary to cover A Let oA be the max selection of ones in A Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 9/21
  • 10. 0 1 0 1 1 1 0 1 00 0 1 1 0 00 lA=oA= 3 We want to show with ΣB 1 induction that oA = lA. Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 10/21
  • 11. LA uses ΣB 0 induction LA oA ≤ lA LA over Z is equivalent to VTC0 And oA ≤ lA follows more or less from the Pigeonhole Principle: if we can select oA 1s, no two on the same line, then we shall require at least lA lines to cover those 1s. Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 11/21
  • 12. ∃LA oA ≥ lA Showing oA ≥ lA is more difficult; we use ΣB 1 induction. Lots of cases, but the interesting case is: 0 where we reduce the general case to the case of the blue matrix whose cover requires as many lines as rows. Comb Matrix - Soltys MFCS’13 IST Austria Main Proof - 12/21
  • 13. 00 00 00 0 0 0 0 0 0 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 13/21
  • 14. 10 00 00 0 0 0 0 0 0 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 14/21
  • 15. 0 0 00 00 0 0 0 0 0 01 0 0 0 1 0 0 0 0 0 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 15/21
  • 16. 1 0 00 00 0 0 0 0 0 01 0 0 0 1 0 0 0 0 0 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 16/21
  • 17. 1 0 00 00 0 0 0 0 0 01 0 0 0 1 0 0 0 0 0 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 17/21
  • 18. H 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A B C D E FG Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 18/21
  • 19. J 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 H 1 1 Comb Matrix - Soltys MFCS’13 IST Austria Interesting Case - 19/21
  • 20. ΣB 0 Proof of Equivalence For example, ΣB 0 proof of Menger → KMM yx Left graph has a matching of size k ⇐⇒ Right graph has k disjoint {x, y}-paths Left graph has a cover of size k ⇐⇒ Right graph has an {x, y}-cut of size k KMM → Meng complicated, [Aharoni 1983] Comb Matrix - Soltys MFCS’13 IST Austria Proof of equivalences - 20/21
  • 21. Some open problems Frankl’s Theorem: t a positive integer, and m ≤ n(2t −1) t ; if A is m × n, and its rows are distinct, then there exists a column that when deleted, the resulting matrix has at most 2t−1 − 1 pairs of equal rows. (Bondy’s Theorem when t = 1.) Complexity of decompositions: A = P1 + P2 + · · · + Pn + X; n boys and n girls, each boy introduced to exactly k girls and vice versa. Compute a pairing where each boy & girl has been previously introduced. Projective Geometry          1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0          Desargues Thm Comb Matrix - Soltys MFCS’13 IST Austria Conclusion - 21/21