A family of permutations in $S_n$ is called even-intersecting if every two distinct members agree in an even number of positions. Let $M(n)$ denote the maximum size of such a family. For even $n$, we prove that $$n!!\leq M(n)\leq e^{\frac{n}{2}+o(n)}n!!,$$ improving the bound obtained from a theorem of Cameron, Deza and Frankl (1987) by an exponential factor. This problem may be viewed as a permutation analogue of the classical Eventown problem for set systems. For odd $n$, we give a construction yielding $M(n)\geq n^2/4$. We further extend this construction to obtain $$ M(n)\geq\bigl(n-\sqrt{n-1}\bigr)^2 ,$$ whenever $n=(q+1)^2+1$ and $q$ is an odd prime power. The latter bound asymptotically matches the upper bound $M(n)\leq(n-1)^2+1$ obtained by Cameron, Deza and Frankl.
For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We...
For a positive integer $n$, let $S(n)=\{\sigma(d): d\mid n\}$ be ordered by divisibility, and let $a(n)$ be its width. We study how much of the divisor lattice of $n$ survives under the map $d\mapsto \sigma(d)$. For every fixed prime-exponent pattern, the largest possible value of $a(n)$ is the width of a corresponding...
A family of subsets of $[n]$ is $r$-fork-free if none of its members is strictly contained in $r$ other distinct members. For each fixed integer $r\ge2$, we prove that the maximum size of such a family is \[ \binom{n}{\lfloor n/2\rfloor} \left(1+\frac{2(r-1)}{n}+o(n^{-1})\right). \] This determines the second-order ter...
A cyclic number is a positive integer $n$ such that $\gcd(n, \varphi(n)) = 1$. Erd\H{o}s showed that the number of cyclic numbers up to $x$, $C(x)$, has $C(x) \sim e^{-\gamma}x/\log_3(x)$ asymptotically as $x$ tends to infinity. We define Wieferich numbers to be odd, positive integers $n$ such that $(n, (2^{\ell(n)}-1)...
Let $C(n)$ denote the maximum number of directed Hamiltonian cycles in a tournament on $n$ vertices. We prove that, as $n\to\infty$, $$ C(n) = \left(\frac{\cosh 1}{\cos 1}\pm o(1)\right)\frac{(n-1)!}{2^n}. $$ The bound is asymptotically attained by the regular tournament with vertices $\mathbb Z/n\mathbb Z$ where $(i,j...
Let $d$ be the divisor function, and let $K(n)$ be the least positive integer $K$ for which $d((n + K)!) \ge 2d(n!)$. Erd\H{o}s, Graham, Ivi\'c and Pomerance proved that, for infinitely many $n$, \begin{equation*} K(n)>(1/9)(\log n)(\log_{2} n)(\log_{4} n)/(\log_{3} n)^3. \end{equation*} We improve upon this by a facto...
Tristan Freiberg· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
