Search

We study the probability that the random graph $G(n,p)$ is triangle-free. When $p =o(n^{-1/2})$ or $p = \omega(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and via regularity or hypergraph container methods in the latter case. We prove for the first time an asymptotic formula for the logarithm of this probability when $p = c n^{-1/2}$ for $c$ a sufficiently small constant. More generally, we study lower-tail large deviations for triangles in random graphs: the probability that $G(n,p)$ has at most $\eta$ times its expected number of triangles, when $p = c n^{-1/2}$ for $c$ and $\eta \in [0,1)$ constant. Our results apply for all $c$ if $\eta \ge .4993$ and for $c$ small enough otherwise. For $\eta$ small (including the case of triangle-freeness), we prove that a phase transition occurs as $c$ varies, in the sense of a non-analyticity of the rate function, while for $\eta \ge .4993$ we prove that no phase transition occurs. On the other hand for the random graph $G(n,m)$, with $m = b n^{3/2}$, we show that a phase transition occurs in the lower-tail problem for triangles as $b$ varies for \emph{every} $\eta \in [0,1)$. Our method involves ingredients from algorithms and statistical physics including the cluster expansion and concentration inequalities for contractive Markov chains.

We present an audit mechanism for language models, with a focus on models deployed in the healthcare setting. Our proposed mechanism takes inspiration from clinical trial design where we posit the language model audit as a single blind equivalence trial, with the comparison of interest being the subject matter experts. We show that using our proposed method, we can follow principled sample size and power calculations, leading to the requirement of sampling minimum number of records while maintaining the audit integrity and statistical soundness. Finally, we provide a real-world example of the audit used in a production environment in a large-scale public health network.

We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ conditioned on triangle-freeness? Can we efficiently approximate the probability that $G(n,p)$ is triangle-free? These are prototypical instances of forbidden substructure problems ubiquitous in combinatorics. The algorithmic questions are instances of approximate counting and sampling for a hypergraph hard-core model. Estimating the probability that $G(n,p)$ has no triangles is a fundamental question in probabilistic combinatorics and one that has led to the development of many important tools in the field. Through the work of several authors, the asymptotics of the logarithm of this probability are known if $p =o( n^{-1/2})$ or if $p =\omega( n^{-1/2})$. The regime $p = \Theta(n^{-1/2})$ is more mysterious, as this range witnesses a dramatic change in the the typical structural properties of $G(n,p)$ conditioned on triangle-freeness. As we show, this change in structure has a profound impact on the performance of sampling algorithms. We give two different efficient sampling algorithms for triangle-free graphs (and complementary algorithms to approximate the triangle-freeness large deviation probability), one that is efficient when $p < c/\sqrt{n}$ and one that is efficient when $p > C/\sqrt{n}$ for constants $c, C>0$. The latter algorithm involves a new approach for dealing with large defects in the setting of sampling from low-temperature spin models.

Degeneracy plays an important role in understanding Tur\'an- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a $k$-uniform hypergraph as the degeneracy of its $1$-skeleton (i.e., the graph formed by replacing every $k$-edge by a $k$-clique). We prove that skeletal degeneracy controls hypergraph Tur\'an and Ramsey numbers in a similar manner to (graphical) degeneracy. Specifically, we show that $k$-uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erd\H{o}s conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Tur\'an number of a $k$-uniform $k$-partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the `random greedy process' introduced by Lee in his resolution of the Burr-Erd\H{o}s conjecture., Comment: 33 pages

Social navigation and pedestrian behavior research has shifted towards machine learning-based methods and converged on the topic of modeling inter-pedestrian interactions and pedestrian-robot interactions. For this, large-scale datasets that contain rich information are needed. We describe a portable data collection system, coupled with a semi-autonomous labeling pipeline. As part of the pipeline, we designed a label correction web app that facilitates human verification of automated pedestrian tracking outcomes. Our system enables large-scale data collection in diverse environments and fast trajectory label production. Compared with existing pedestrian data collection methods, our system contains three components: a combination of top-down and ego-centric views, natural human behavior in the presence of a socially appropriate "robot", and human-verified labels grounded in the metric space. To the best of our knowledge, no prior data collection system has a combination of all three components. We further introduce our ever-expanding dataset from the ongoing data collection effort -- the TBD Pedestrian Dataset and show that our collected data is larger in scale, contains richer information when compared to prior datasets with human-verified labels, and supports new research opportunities., Comment: This work has been accepted by IEEE ICRA 2024. arXiv admin note: substantial text overlap with arXiv:2203.01974

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}\left(n + \log(1/\delta)\log\log(1/\delta)\right)$ space and $\mathcal{O}\left(\log(\log(n)/\delta)\right)$-wise independent hash functions. As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest. We apply our new IBLTs to the encrypted compression problem, recently studied by Fleischhacker, Larsen, Simkin (Eurocrypt 2023). We extend their approach to work for a more general class of encryption schemes and using our new IBLT we achieve an asymptotically better compression rate.

Consider a host hypergraph $G$ which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of $G$ are sampled at the appropriate rate then the spanning structure still appears with high probability in the sampled hypergraph. We prove such results for perfect matchings in hypergraphs above Dirac thresholds, for $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition, and for bounded-degree spanning trees. In each case our proof is based on constructing a spread measure and then applying recent results on the (fractional) Kahn--Kalai conjecture connecting the existence of such measures with probabilistic thresholds. For our second result we give a shorter and more general proof of a recent theorem of Allen, B\"ottcher, Corsten, Davies, Jenssen, Morris, Roberts, and Skokan which handles the $r=3$ case with different techniques. In particular, we answer a question of theirs with regards to the number of $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition., Comment: 41 pages. Corrected an error in the proof of Theorem 1.5 and improved exposition

We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{6}$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park., Comment: Improved exposition. Results unchanged. 23 pages, 1 figure

We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order-$n$ Latin squares with no intercalate (i.e., no $2\times2$ Latin subsquare) is at least $(e^{-9/4}n-o(n))^{n^{2}}$. Equivalently, $\mathbb{P}\left[\mathbf{N}=0\right]\ge e^{-n^{2}/4-o(n^{2})}=e^{-(1+o(1))\mathbb{E}\mathbf{N}}$, where $\mathbf{N}$ is the number of intercalates in a uniformly random order-$n$ Latin square. In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant $0<\delta\le1$ we have $\mathbb{P}[\mathbf{N}\le(1-\delta)\mathbb{E}\mathbf{N}]=\exp(-\Theta(n^{2}))$ and for any constant $\delta>0$ we have $\mathbb{P}[\mathbf{N}\ge(1+\delta)\mathbb{E}\mathbf{N}]=\exp(-\Theta(n^{4/3}\log n))$. Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order-$n$ Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate $2\times2$ submatrices with the same arrangement of symbols) is of order $n^{4}$, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is., Comment: 32 pages, 1 figure. Corrected typos and improved terminology

We prove a 1973 conjecture due to Erd\H{o}s on the existence of Steiner triple systems with arbitrarily high girth., Comment: Added details to some proofs. Final version, to appear in Annals of Mathematics

A knowledge graph (KG) is a data structure which represents entities and relations as the vertices and edges of a directed graph with edge types. KGs are an important primitive in modern machine learning and artificial intelligence. Embedding-based models, such as the seminal TransE [Bordes et al., 2013] and the recent PairRE [Chao et al., 2020] are among the most popular and successful approaches for representing KGs and inferring missing edges (link completion). Their relative success is often credited in the literature to their ability to learn logical rules between the relations. In this work, we investigate whether learning rules between relations is indeed what drives the performance of embedding-based methods. We define motif learning and two alternative mechanisms, network learning (based only on the connectivity of the KG, ignoring the relation types), and unstructured statistical learning (ignoring the connectivity of the graph). Using experiments on synthetic KGs, we show that KG models can learn motifs and how this ability is degraded by non-motif (noise) edges. We propose tests to distinguish the contributions of the three mechanisms to performance, and apply them to popular KG benchmarks. We also discuss an issue with the standard performance testing protocol and suggest an improvement. To appear in the proceedings of Complex Networks 2021., Comment: 16 pages

Many serial killers commit tens of murders. At the same time inter-murder intervals can be decades long. This suggests that some serial killers can die of an accident or a disease, having been never caught. We use the distribution of the killers by the number of murders, the distribution of the length of inter-murder intervals and USA life tables to estimate the number of the uncaught killers. The result is that in 20th century there were about seven of such killers. The most prolific of them likely committed over sixty murders.

Computing such correlation coefficient would be straightforward had we had available the rankings given by the prize committee to all scientists in the pool. In reality we only have citation rankings for all scientists. This means, however, that we have the ordinal rankings of the prize winners with regard to citation metrics. I use maximum likelihood method to infer the most probable correlation coefficient to produce the observed pattern of ordinal ranks of the prize winners. I get the correlation coefficients of 0.47 and 0.59 between the composite citation indicator and getting Abel Prize and Fields Medal, respectively. The correlation coefficient between getting a Nobel Prize and the Q-factor is 0.65. These coefficients are of the same magnitude as the correlation coefficient between Elo ratings of the chess players and their popularity measured as numbers of webpages mentioning the players.

The $n$-queens problem is to determine $\mathcal{Q}(n)$, the number of ways to place $n$ mutually non-threatening queens on an $n \times n$ board. We show that there exists a constant $\alpha = 1.942 \pm 3 \times 10^{-3}$ such that $\mathcal{Q}(n) = ((1 \pm o(1))ne^{-\alpha})^n$. The constant $\alpha$ is characterized as the solution to a convex optimization problem in $\mathcal{P}([-1/2,1/2]^2)$, the space of Borel probability measures on the square. The chief innovation is the introduction of limit objects for $n$-queens configurations, which we call queenons. These form a convex set in $\mathcal{P}([-1/2,1/2]^2)$. We define an entropy function that counts the number of $n$-queens configurations that approximate a given queenon. The upper bound uses the entropy method of Radhakrishnan and Linial--Luria. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of $n$-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons. Along the way we prove a large deviations principle for $n$-queens configurations that can be used to study their typical structure., Comment: 60 pages, 4 figures. Filled in a gap by adding Lemma 3.5. Corrected various minor errors

Recent research has found that select scientists have a disproportional share of highly cited papers. Researchers reasoned that this could not have happened if success in science was random and introduced a hidden parameter Q, or talent, to explain this finding. So, the talented high-Q scientists have many high impact papers. Here I show that an upgrade of an old random citation copying model could also explain this finding. In the new model the probability of citation copying is not the same for all papers but is proportional to the logarithm of the total number of citations to all papers of its author. Numerical simulations of the model give results similar to the empirical findings of the Q-factor article., Comment: Accepted for publication by Europhysics Letters

Property-preserving hash functions allow for compressing long inputs $x_0$ and $x_1$ into short hashes $h(x_0)$ and $h(x_1)$ in a manner that allows for computing a predicate $P(x_0, x_1)$ given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick $x_0$ and $x_1$ after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result. In this work we construct robust property-preserving hash functions for the hamming-distance predicate which distinguishes inputs with a hamming distance at least some threshold $t$ from those with distance less than $t$. The security of the construction is based on standard lattice hardness assumptions. Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin. Our construction relies on a single well-studied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions. In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas previously several exponentiations per bit as well as the interpolation and evaluation of high-degree polynomials over large fields were required. An additional benefit of our construction is that the description of the hash function can be compressed to $\lambda$ bits assuming a random oracle. Previous work has descriptions of length $\mathcal{O}(\ell \lambda)$ bits for input bit-length $\ell$, which has a secret structure and thus cannot be compressed. We prove a lower bound on the output size of any property-preserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.

The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an $n \times n$ chessboard. We present a simple two stage randomized algorithm to construct such configurations. In the first stage, a random greedy algorithm constructs an approximate \textit{toroidal} $n$-queens configuration. In this well-known variant the diagonals wrap around the board from left to right and from top to bottom. We show that with high probability this algorithm succeeds in placing $(1-o(1))n$ queens on the board. In the second stage, the method of absorbers is used to obtain a complete solution to the non-toroidal problem. By counting the number of choices available at each step of the random greedy algorithm we conclude that there are more than $\left( \left( 1 - o(1) \right) n e^{-3} \right)^n$ solutions to the $n$-queens problem. This proves a conjecture of Rivin, Vardi, and Zimmerman in a strong form., Comment: 16 pages, 2 figures, corrected typos and improved exposition

Primordial black holes created in the early Universe can constitute a substantial fraction of dark matter and serve as seeds for early galaxy formation. Binary primordial black holes with masses of the order of a few dozen solar masses can explain the observed LIGO/Virgo gravitational-wave events. In this Letter, we show that primordial black holes with log-normal mass spectrum centered at $M_0\simeq 15-17 M_\odot$ simultaneously explain both the chirp mass distribution of the detected LIGO/Virgo binary black holes and the differential chirp mass distribution of merging binaries as inferred from the LIGO/Virgo observations. The obtained parameters of log-normal mass spectrum of primordial black holes also give the fraction of seeds with $M\gtrsim 10^4 M_\odot$ required to explain the observed population of supermassive black holes at $z=6-7$., Comment: 4 pages, 2 figures, to be submitted

Possible models for the generation of electromagnetic (EM) radiation during the coalescence of neutron star-black hole binaries are considered. The mass of the remnant disk around the black hole during the coalescence of neutron stars and black holes is calculated by taking into account the equation of state for neutron stars and the rotation of the binary components before the coalescence. The parameters of binary systems before the coalescence (the mass ratio, the component rotation, the neutron star magnetic field) are calculated by the population synthesis method. The derived mass of the remnant disk around the black hole after the coalescence is used to estimate the kinetic energy of the relativistic jet launched by the Blandford-Znajek mechanism. A disk mass of more than $\sim 0.05 M_\odot$ required for the formation of short gamma-ray bursts is shown to be obtained in no more than 1-10\% of the coalescences (depending on the equation of state). Less efficient common envelopes (a large parameter $\alpha_{CE}$) lead to a noticeably larger percentage of events with astrophysically interesting EM energy release. For binaries with a large mass ratio, in which a magnetized neutron star is not subjected to tidal disruption before the coalescence, the possibility of the formation of an electrically charged rotating black hole (Wald charge) is considered and estimates of the maximum EM power released by such a black hole after the coalescence are made. The conversion of the emitted gravitational waves into electromagnetic ones in the relativistic lepton plasma generated in coalescing pulsar-black hole binaries at the pre-coalescence stage is discussed., Comment: 19 pages, 8 figures

In the recent article Janosov, Battiston, & Sinatra report that they separated the inputs of talent and luck in creative careers. They build on the previous work of Sinatra et al which introduced the Q-model. Under the model the popularity of different elements of culture is a product of two factors: a random factor and a Qfactor, or talent. The latter is fixed for an individual but randomly distributed among different people. This way they explain how some individuals can consistently produce high-impact work. They extract the Q-factors for different scientists, writers, and movie makers from statistical data on popularity of their work. However, in their article they reluctantly state that there is little correlation between popularity and quality ratings of of books and movies (correlation coefficients 0.022 and 0.15). I analyzed the data of the original Q-factor article and obtained a correlation between the citation-based Q-factor and Nobel Prize winning of merely 0.19. I also briefly review few other experiments that found a meager, sometimes even negative, correlation between popularity and quality of cultural products. I conclude that, if there is an ability associated with a high Q-factor it should be more of a marketing ability than an ability to produce a higher quality product. Janosov

Available data on the chirp mass distribution of the coalescing black hole binaries in O1-O3 LIGO/Virgo runs are analyzed and compared statistically with the distribution calculated under the assumption that these black holes are primordial with a log-normal mass spectrum. The theoretically calculated chirp mass distribution with the inferred best acceptable mass spectrum parameters, $M_0=17 M_\odot$ and $\gamma=0.9$, perfectly describes the data. The value of $M_0$ very well agrees with the theoretically expected one. On the opposite, the chirp mass distribution of black hole binaries originated from massive binary star evolution requires additional model adjustments to reproduce the observed chirp mass distribution, Comment: 17 pages, 8 figures, one figure and reference added, revised version submitted to JCAP

We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\geq 3$ and $c \in (0,1)$ be fixed. Let $n \in \mathbb{N}$ be even and set $g = c \log_{k-1} (n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $\delta (G)

We study the distribution of 2,837 inter-murder intervals (cooling off periods) for 1,012 American serial killers. The distribution is smooth, following a power law in the region of 10-10,000 days. The power law cuts off where inter-murder intervals become comparable with the length of human life. Otherwise there is no other characteristic scale in the distribution. In particular, we do not see any characteristic spree-killer interval or serial-killer interval, but only a monotonous smooth distribution lacking any features. This suggests that there is only a quantitative difference between serial killers and spree-killers, representing different samples generated by the same underlying phenomenon. The over decade long inter-murder intervals are not anomalies, but rare events described by the same power-law distribution and therefore should not necessarily be looked upon with suspicion, as has been done in a recent case involving a serial killer dubbed as the "Grim Sleeper." This large-scale study supports the conclusions of a previous study, involving three prolific serial killers, and the associated neural net model, which can explain the observed power law distribution., Comment: An adopted for criminology readership version of this article was published by the Journal of Criminal Justice

Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2n}$ or the complete bipartite graph $K_{n,n}$, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary $k$-regular bipartite graphs $G$ on $2n$ vertices for all $k = \omega \left( \frac{n}{\log^{1/3} n} \right)$. Surprisingly, this is not the case for smaller values of $k$. Using a construction due to Goel, Kapralov and Khanna, we show that there exist bipartite $k$-regular graphs in which the last isolated vertex disappears long before a perfect matching appears., Comment: Corrected typo

Let $m \leq n \leq k$. An $m \times n \times k$ 0-1 array is a Latin box if it contains exactly $mn$ ones, and has at most one $1$ in each line. As a special case, Latin boxes in which $m = n = k$ are equivalent to Latin squares. Let $\mathcal{M}(m,n,k;p)$ be the distribution on $m \times n \times k$ 0-1 arrays where each entry is $1$ with probability $p$, independently of the other entries. The threshold question for Latin squares asks when $\mathcal{M}(n,n,n;p)$ contains a Latin square with high probability. More generally, when does $\mathcal{M}(m,n,k;p)$ support a Latin box with high probability? Let $\varepsilon>0$. We give an asymptotically tight answer to this question in the special cases where $n=k$ and $m \leq \left(1-\varepsilon \right) n$, and where $n=m$ and $k \geq \left(1+\varepsilon \right) n$. In both cases, the threshold probability is $\Theta \left( \log \left( n \right) / n \right)$. This implies threshold results for Latin rectangles and proper edge-colorings of $K_{n,n}$., Comment: Corrected typos; Added acknowledgment

Let $H$ be a random $k$-uniform $n$-vertex hypergraph where every $k$-tuple belongs to $H$ independently with probability $p$. We show that for some $\varepsilon_k > 0$, if $p \geq n^{-\varepsilon_k}$, then asymptotically almost surely $H$ contains an $\left( n , k , k - 1 \right)$-Steiner System. Our main tool is Keevash's method of Randomized Algebraic Constructions., Comment: 22 pages

This report is a follow-up to a 2012-2013 study (see ED611342), which found that 77 of 100 large U.S. cities were coordinating the work of out-of-school-time providers, government agencies, private funders, and others to provide high-quality afterschool programs to the children who stand to benefit most. The report provides a look at the state of afterschool coordination just prior to the unexpected and devastating closure of schools and afterschool programs in the spring of 2020 owing to the global pandemic. It focuses on three key components described in the research on afterschool coordination: (1) a designated coordinating entity; (2) a common data system; (3) and a framework or set of standards for program quality. ??The authors were able to gather information about the status of afterschool systems in 67 of 75 cities (two of the original 77 cities were left out of the current study for methodological reasons). They found that a large majority--57 cities--were still coordinating afterschool efforts in 2020. Moreover, the proportion of cities that had adopted all three key components increased from 29 percent in 2013 to 40 percent in 2020. While the percentage of cities with a common data system and the percentage with quality standards or a quality framework both increased, a quarter of cities that had coordinating entities in 2013 no longer had them in 2020. Statewide and regional networks, state-level afterschool coordination initiatives and private philanthropy appeared to be playing a larger role in supporting coordination than in 2013. The research also found a statistically significant relationship between increased funding for afterschool coordination and the use of quality standards or a quality framework in 2020 and a statistically significant relationship between having a high or moderate level of support from the mayor or county executive and having a common data system. ??The authors also looked at 50 cities where, in 2013, there was no afterschool coordination or they were unable to find a knowledgeable contact afterschool coordination. Of the 34 cities where a knowledgeable contact could be found in 2020, 14 were now doing some coordination.

This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the Erd\H{o}s-Szekeres theorem: For every $k\ge1$, every order-$n$ $k$-dimensional permutation contains a monotone subsequence of length $\Omega_{k}\left(\sqrt{n}\right)$, and this is tight. On the other hand, and unlike the classical case, the longest monotone subsequence in a random $k$-dimensional permutation of order $n$ is asymptotically almost surely $\Theta_{k}\left(n^{\frac{k}{k+1}}\right)$., Comment: 12 pages, 1 figure

We investigate a pool of international chess title holders born between 1901 and 1943. Using Elo ratings we compute for every player his expected score in a game with a randomly selected player from the pool. We use this figure as player's merit. We measure players' fame as the number of Google hits. The correlation between fame and merit is 0.38. At the same time the correlation between the logarithm of fame and merit is 0.61. This suggests that fame grows exponentially with merit., Comment: To appear in Applied Economics Letters

MnSi has been extensively studied for five decades, nonetheless detailed information on the Fermi surface (FS) symmetry is still lacking. This missed information prevented from a comprehensive understanding the nature of the magnetic interaction in this material. Here, by performing angle-resolved photoemission spectroscopy on high-quality MnSi films epitaxially grown on Si(111), we unveil the FS symmetry and the evolution of the electronic structure across the paramagnetic-helimagnetic transition at T$_C$ $\sim$ 40 K, along with the appearance of sharp quasiparticle emission below T$_C$. The shape of the resulting FS is found to fulfill robust nesting effects. These effects can be at the origin of strong magnetic fluctuations not accounted for by state-of-art quasiparticle self-consistent GW approximation. From this perspective, the unforeseen quasiparticle damping detected in the paramagnetic phase and relaxing only below T$_C$, along with the persistence of the d-bands splitting well above T$_C$, at odds with a simple Stoner model for itinerant magnetism, open the search for exotic magnetic interactions favored by FS nesting and affecting the quasiparticles lifetime.