### Top 3 Arxiv Papers Today in Discrete Mathematics

##### #1. Bipartite Perfect Matching as a Real Polynomial
###### Gal Beniamini, Noam Nisan
We obtain a description of the Bipartite Perfect Matching decision problem as a multi-linear polynomial over the Reals. We show that it has full degree and has $(1-o(1))\cdot 2^{n^2}$ monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) there are only $2^{\theta(n \log n)}$ monomials with non-zero coefficients. Our proof relies heavily on the fact that the lattice of graphs which are matching-covered'' is Eulerian.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #2. Complexity of limit-cycle problems in Boolean networks
###### Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, Sylvain Sené
Boolean networks are a general model of interacting entities, with applications to biological phenomena such as gene regulation. Attractors play a central role, and the schedule of entities update is a priori unknown. This article presents results on the computational complexity of problems related to the existence of update schedules such that some limit-cycle lengths are possible or not. We first prove that given a Boolean network updated in parallel, knowing whether it has at least one limit-cycle of length $k$ is $\text{NP}$-complete. Adding an existential quantification on the block-sequential update schedule does not change the complexity class of the problem, but the following alternation brings us one level above in the polynomial hierarchy: given a Boolean network, knowing whether there exists a block-sequential update schedule such that it has no limit-cycle of length $k$ is $\Sigma_2^\text{P}$-complete.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

##### #3. Bisimilar Conversion of Multi-valued Networks to Boolean Networks
###### Franck Delaplace, Sergiu Ivanov
Discrete modelling frameworks of Biological networks can be divided in two distinct categories: Boolean and Multi-valued. Although Multi-valued networks are more expressive for qualifying the regulatory behaviours modelled by more than two values, the ability to automatically convert them to Boolean network with an equivalent behaviour breaks down the fundamental borders between the two approaches. Theoretically investigating the conversion process provides relevant insights into bridging the gap between them. Basically, the conversion aims at finding a Boolean network bisimulating a Multi-valued one. In this article, we investigate the bisimilar conversion where the Boolean integer coding is a parameter that can be freely modified. Based on this analysis, we define a computational method automatically inferring a bisimilar Boolean network from a given Multi-valued one.
more | pdf | html
None.
###### Tweets
BioPapers: Bisimilar Conversion of Multi-valued Networks to Boolean Networks. https://t.co/0pEcy1PCh5
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 12267
Unqiue Words: 2145

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 257,103 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 257,103 papers.