Solving systems of equations on antichains for the computation of the ninth Dedekind Number
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910650207305728 |
|---|---|
| author | De Causmaecker, Patrick Van Hirtum, Lennart |
| author_facet | De Causmaecker, Patrick Van Hirtum, Lennart |
| contents | We study systems of equations on antichains, together with a way to count the number of solutions. We start with a simple example, generalise and show more applications. One of the results was used in the recent computation of D(9), the others have potential to speed up existing techniques in the future.
In fact, the result of two independent computations of D(9) were published nearly at the same time, in one of them the authors of the present paper were involved. D(n) counts the monotone Boolean functions or antichains on subsets of a set of n elements. The number rises doubly exponentially in the number of elements n, and until now no algorithm of a lower combinatorial complexity is known to compute D(n). In our computation, we use coefficients representing the number of solutions of a specific set of equations on antichains over a finite set. We refer to these coefficients as P-coefficients. These can be computed efficiently. In this paper, we generalise this coefficient and apply it to four different systems of equations. Finally we show how the coefficient was used in our computation of D(9), and how its generalisations can be used to compute D(n). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20904 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving systems of equations on antichains for the computation of the ninth Dedekind Number De Causmaecker, Patrick Van Hirtum, Lennart Combinatorics Discrete Mathematics We study systems of equations on antichains, together with a way to count the number of solutions. We start with a simple example, generalise and show more applications. One of the results was used in the recent computation of D(9), the others have potential to speed up existing techniques in the future. In fact, the result of two independent computations of D(9) were published nearly at the same time, in one of them the authors of the present paper were involved. D(n) counts the monotone Boolean functions or antichains on subsets of a set of n elements. The number rises doubly exponentially in the number of elements n, and until now no algorithm of a lower combinatorial complexity is known to compute D(n). In our computation, we use coefficients representing the number of solutions of a specific set of equations on antichains over a finite set. We refer to these coefficients as P-coefficients. These can be computed efficiently. In this paper, we generalise this coefficient and apply it to four different systems of equations. Finally we show how the coefficient was used in our computation of D(9), and how its generalisations can be used to compute D(n). |
| title | Solving systems of equations on antichains for the computation of the ninth Dedekind Number |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.20904 |