### Top 2 Arxiv Papers Today in Discrete Mathematics

##### #1. A tighter bound on the number of relevant variables in a bounded degree Boolean function
###### Jake Wellens
A classical theorem of Nisan and Szegedy says that a boolean function with degree $d$ as a real polynomial depends on at most $d2^{d-1}$ of its variables. In recent work by Chiarelli, Hatami and Saks, this upper bound was improved to $C \cdot 2^d$, where $C = 6.614$. Here we refine their argument to show that one may take $C = 4.416$.
more | pdf | html
None.
###### Tweets
ComputerPapers: A tighter bound on the number of relevant variables in a bounded degree Boolean function. https://t.co/dKgx2AeZhR
MUKULBHALLA7: https://t.co/LLa17Nv4gE
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3602
Unqiue Words: 1030

##### #2. Any Finite Distributive Lattice is Isomorphic to the Minimizer Set of an ${\rm M}^{\natural}$-Concave Set Function
###### Tomohito Fujii, Shuji Kijima
Submodularity is an important concept in combinatorial optimization, and it is often regarded as a discrete analog of convexity. It is a fundamental fact that the set of minimizers of any submodular function forms a distributive lattice. Conversely, it is also known that any finite distributive lattice is isomorphic to the minimizer set of a submodular function, through the celebrated Birkhoff's representation theorem. ${\rm M}^{\natural}$-concavity is a key concept in discrete convex analysis. It is known for set functions that the class of ${\rm M}^{\natural}$-concave is a proper subclass of submodular. Thus, the minimizer set of an ${\rm M}^{\natural}$-concave function forms a distributive lattice. It is natural to ask if any finite distributive lattice appears as the minimizer set of an ${\rm M}^{\natural}$-concave function. This paper affirmatively answers the question.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7163
Unqiue Words: 1348

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 99,586 papers.

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