### Top 2 Arxiv Papers Today in Discrete Mathematics

##### #1. On the Relativized Alon Second Eigenvalue Conjecture V: Proof of the Relativized Alon Conjecture for Regular Base Graphs
###### Joel Friedman, David Kohler
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the \emph{algebraic power} (which can also be $+\infty$) and the \emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+\infty$, and in Article~VI we prove this when the base graph is regular and \emph{Ramanujan}. When the algebraic power of the...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #2. Optimal adaptive group testing
###### Max Hahn-Klimroth, Philipp Loick
The group testing problem is concerned with identifying a small number $k \sim n^\theta$ for $\theta \in (0,1)$ of infected individuals in a large population of size $n$. At our disposal is a testing procedure that allows us to test groups of individuals. This paper considers two-stage designs where the test results of the first stage can inform the design of the second stage. We are interested in the minimum number of tests to recover the set of infected individuals w.h.p. Equipped with a novel algorithm for one-stage group testing from [Coja-Oghlan, Gebhard, Hahn-Klimroth \& Loick 2019], we propose a polynomial-time two-stage algorithm that matches the universal information-theoretic lower bound of group testing. This result improves on results from [M\'ezard \& Toninelli 2011] and resolves open problems prominently posed in [Aldridge, Johnson \& Scarlett 2019, Berger \& Levenshtein 2002, Damaschke \& Muhammad 2012].
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

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 223,556 papers.

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