Singmaster’s conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal’s triangle; that is, for any natural number $t \geq 2$, the number of solutions to the equation $\binom{n}{m} = t$ for natural numbers $1 \leq m \lt n$ is bounded. In this paper we establish this result in the interior region $\exp(\log^{2/3+\varepsilon} n) \leq m \leq n - \exp(\log^{2/3+\varepsilon} n)$ for any fixed ɛ > 0. Indeed, when t is sufficiently large depending on ɛ, we show that there are at most four solutions (or at most two in either half of Pascal’s triangle) in this region. We also establish analogous results for the equation $(n)_m = t$, where $(n)_m := n(n-1) \dots (n-m+1)$ denotes the falling factorial.
This content will become publicly available on March 1, 2025
Turán graphs with bounded matching number
We determine the maximum possible number of edges of a graph with n vertices, matching number at most s and clique number at most k for all admissible values of the parameters.
more »
« less
- Award ID(s):
- 2154082
- NSF-PAR ID:
- 10498656
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Journal of Combinatorial Theory, Series B
- Volume:
- 165
- Issue:
- C
- ISSN:
- 0095-8956
- Page Range / eLocation ID:
- 223 to 229
- Subject(s) / Keyword(s):
- Combinatorics Discrete Mathematics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
Inspired by results of Eskin and Mirzakhani (J Mod Dyn 5(1):71–105, 2011) counting closed geodesics of length at most L in the moduli space of a fixed closed surface, we consider a similar question in the Out(Fr) setting. The Eskin-Mirzakhani result can be equivalently stated in terms of counting the number of conjugacy classes (within the mapping class group) of pseudo-Anosovs whose dilatations have natural logarithm at most L. Let N(L) denote the number of Out(Fr)-conjugacy classes of fully irreducibles satisfying that the natural logarithm of their dilatation is at most L. We prove for r>2 that as L goes to infinity, the number N(L) has double exponential (in L) lower and upper bounds. These bounds reveal behavior not present in the surface setting or in classical hyperbolic dynamical systems.more » « less
-
more » « less
Abstract We prove that the number of edges of a multigraph with vertices is at most , provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, if has edges, in any drawing of with the above property, the number of crossings is . This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.
-
We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.more » « less
-
S. Koyejo ; S. Mohamed ; A. Agarwal ; D. Belgrave ; K. Cho ; A. Oh (Ed.)A deep neural network using rectified linear units represents a continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing a CPWL function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number of pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies a lower neural complexity because the number of distinct linear components is always not greater than the minimum number of pieces in a CPWL function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexities of any CPWL function are at most polynomial growth for low-dimensional inputs and factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.more » « less
