355 results on '"Ferber, Asaf"'
Search Results
2. Sunflowers in set systems with small VC-dimension
- Author
-
Balogh, József, Bernshteyn, Anton, Delcourt, Michelle, Ferber, Asaf, and Pham, Huy Tuan
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,Mathematics - Probability - Abstract
A family of $r$ distinct sets $\{A_1,\ldots, A_r\}$ is an $r$-sunflower if for all $1 \leqslant i < j \leqslant r$ and $1 \leqslant i' < j' \leqslant r$, we have $A_i \cap A_j = A_{i'} \cap A_{j'}$. Erd\H{o}s and Rado conjectured in 1960 that every family $\mathcal{H}$ of $\ell$-element sets of size at least $K(r)^\ell$ contains an $r$-sunflower, where $K(r)$ is some function that depends only on $r$. We prove that if $\mathcal{H}$ is a family of $\ell$-element sets of VC-dimension at most $d$ and $|\mathcal{H}| > (C r (\log d+\log^\ast \ell))^\ell$ for some absolute constant $C > 0$, then $\mathcal{H}$ contains an $r$-sunflower. This improves a recent result of Fox, Pach, and Suk. When $d=1$, we obtain a sharp bound, namely that $|\mathcal{H}| > (r-1)^\ell$ is sufficient. Along the way, we establish a strengthening of the Kahn-Kalai conjecture for set families of bounded VC-dimension, which is of independent interest., Comment: 14 pages
- Published
- 2024
3. A quantum algorithm for learning a graph of bounded degree
- Author
-
Ferber, Asaf and Hardiman, Liam
- Subjects
Quantum Physics ,Mathematics - Combinatorics - Abstract
We are presented with a graph, $G$, on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $\Omega(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors., Comment: 15 pages
- Published
- 2024
4. Hamiltonicity of Sparse Pseudorandom Graphs
- Author
-
Ferber, Asaf, Han, Jie, Mao, Dingjia, and Vershynin, Roman
- Subjects
Mathematics - Combinatorics - Abstract
We show that every $(n,d,\lambda)$-graph contains a Hamilton cycle for sufficiently large $n$, assuming that $d\geq \log^{10}n$ and $\lambda\leq cd$, where $c=\frac{1}{9000}$. This significantly improves a recent result of Glock, Correia and Sudakov, who obtain a similar result for $d$ that grows polynomially with $n$. The proof is based on the absorption technique combined with a new result regarding the second largest eigenvalue of the adjacency matrix of a subgraph induced by a random subset of vertices. We believe that the latter result is of an independent interest and will have further applications.
- Published
- 2024
5. Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs
- Author
-
Ferber, Asaf, Han, Jie, and Mao, Dingjia
- Subjects
Mathematics - Combinatorics - Abstract
Given a family of graphs $G_1,\dots,G_{n}$ on the same vertex set $[n]$, a rainbow Hamilton cycle is a Hamilton cycle on $[n]$ such that each $G_i$ contributes exactly one edge. We prove that if $G_1,\dots,G_{n}$ are independent samples of $G(n,p)$ on the same vertex set $[n]$, then for each $\varepsilon>0$, whp, every collection of spanning subgraphs $H_i\subseteq G_i$, with $\delta(H_i)\geq(\frac{1}{2}+\varepsilon)np$, admits a rainbow Hamilton cycle. A similar result is proved for rainbow perfect matchings in a family of $n/2$ graphs on the same vertex set $[n]$. Our method is likely to be applicable to further problems in the rainbow setting, in particular, we illustrate how it works for finding a rainbow perfect matching in the $k$-partite $k$-uniform hypergraph setting., Comment: 13 pages
- Published
- 2022
6. Sparse recovery properties of discrete random matrices
- Author
-
Ferber, Asaf, Sah, Ashwin, Sawhney, Mehtaab, and Zhu, Yizhe
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Motivated by problems from compressed sensing, we determine the threshold behavior of a random $n\times d$ $\pm 1$ matrix $M_{n,d}$ with respect to the property "every $s$ columns are linearly independent". In particular, we show that for every $0<\delta <1$ and $s=(1-\delta)n$, if $d\leq n^{1+1/2(1-\delta)-o(1)}$ then with high probability every $s$ columns of $M_{n,d}$ are linearly independent, and if $d\geq n^{1+1/2(1-\delta)+o(1)}$ then with high probability there are some $s$ linearly dependent columns.
- Published
- 2022
- Full Text
- View/download PDF
7. Counting Hamilton Cycles in Dirac Hypergraphs
- Author
-
Ferber, Asaf, Hardiman, Liam, and Mond, Adva
- Published
- 2023
- Full Text
- View/download PDF
8. Counting Hamiltonian Cycles in Dirac Hypergraphs
- Author
-
Ferber, Asaf, Hardiman, Liam, and Mond, Adva
- Subjects
Mathematics - Combinatorics ,05C65, 05C38, 05C45, 05C80, 05C07 - Abstract
For $0\leq \ell
1/2$ has (asymptotically and up to a subexponential factor) at least as many Hamiltonian $\ell$-cycles as in a typical random $k$-graph with edge-probability $\delta$. This significantly improves a recent result of Glock, Gould, Joos, K\"uhn, and Osthus, and verifies a conjecture of Ferber, Krivelevich and Sudakov for all values $0\leq \ell - Published
- 2021
9. On subgraphs with degrees of prescribed residues in the random graph
- Author
-
Ferber, Asaf, Hardiman, Liam, and Krivelevich, Michael
- Subjects
Mathematics - Combinatorics - Abstract
We show that with high probability the random graph $G_{n, 1/2}$ has an induced subgraph of linear size, all of whose degrees are congruent to $r\pmod q$ for any fixed $r$ and $q\geq 2$. More generally, the same is true for any fixed distribution of degrees modulo $q$. Finally, we show that with high probability we can partition the vertices of $G_{n, 1/2}$ into $q+1$ parts of nearly equal size, each of which induces a subgraph all of whose degrees are congruent to $r\pmod q$. Our results resolve affirmatively a conjecture of Scott, who addressed the case $q=2$.
- Published
- 2021
10. Singularity of the k-core of a random graph
- Author
-
Ferber, Asaf, Kwan, Matthew, Sah, Ashwin, and Sawhney, Mehtaab
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies'' such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $k\ge 3$ and $\lambda > 0$, an Erd\H{o}s--R\'enyi random graph $G\sim\mathbb{G}(n,\lambda/n)$ with $n$ vertices and edge probability $\lambda/n$ typically has the property that its $k$-core (its largest subgraph with minimum degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 International Congress of Mathematicians, and adds to a short list of known nonsingularity theorems for "extremely sparse'' random matrices with density $O(1/n)$. A key aspect of our proof is a technique to extract high-degree vertices and use them to "boost'' the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge and Salez., Comment: 25 pages
- Published
- 2021
11. Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial
- Author
-
Ferber, Asaf, Jain, Vishesh, Sah, Ashwin, and Sawhney, Mehtaab
- Subjects
Mathematics - Probability ,Mathematics - Number Theory - Abstract
Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric $\{\pm 1\}$-matrix is irreducible. This addresses a question raised by Eberhard in recent work. The main innovation in our work is establishing sharp estimates regarding the rank distribution of symmetric random $\{\pm 1\}$-matrices over $\mathbb{F}_p$ for primes $2 < p \leq \exp(O(n^{1/4}))$. Previously, such estimates were available only for $p = o(n^{1/8})$. At the heart of our proof is a way to combine multiple inverse Littlewood--Offord-type results to control the contribution to singularity-type events of vectors in $\mathbb{F}_p^{n}$ with anticoncentration at least $1/p + \Omega(1/p^2)$. Previously, inverse Littlewood--Offord-type results only allowed control over vectors with anticoncentration at least $C/p$ for some large constant $C > 1$., Comment: 12 pages; comments welcome!
- Published
- 2021
12. Friendly bisections of random graphs
- Author
-
Ferber, Asaf, Kwan, Matthew, Narayanan, Bhargav, Sah, Ashwin, and Sawhney, Mehtaab
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability ,05C80 (primary), 60C05 (secondary) - Abstract
Resolving a conjecture of F\"uredi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which $n-o(n)$ vertices have at least as many neighbours in their own part as across. The engine of our proof is a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument., Comment: 21 pages, 3 appendices
- Published
- 2021
13. List-decodability with large radius for Reed-Solomon codes
- Author
-
Ferber, Asaf, Kwan, Matthew, and Sauermann, Lisa
- Subjects
Computer Science - Information Theory ,Mathematics - Combinatorics - Abstract
List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form $r=1-\varepsilon$ for $\varepsilon$ tending to zero. Our main result states that there exist Reed-Solomon codes with rate $\Omega(\varepsilon)$ which are $(1-\varepsilon, O(1/\varepsilon))$-list-decodable, meaning that any Hamming ball of radius $1-\varepsilon$ contains at most $O(1/\varepsilon)$ codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.
- Published
- 2020
14. Singularity of sparse random matrices: simple proofs
- Author
-
Ferber, Asaf, Kwan, Matthew, and Sauermann, Lisa
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Consider a random $n\times n$ zero-one matrix with "density" $p$, sampled according to one of the following two models: either every entry is independently taken to be one with probability $p$ (the "Bernoulli" model), or each row is independently uniformly sampled from the set of all length-$n$ zero-one vectors with exactly $pn$ ones (the "combinatorial" model). We give simple proofs of the (essentially best-possible) fact that in both models, if $\min(p,1-p)\geq (1+\varepsilon)\log n/n$ for any constant $\varepsilon>0$, then our random matrix is nonsingular with probability $1-o(1)$. In the Bernoulli model this fact was already well-known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person.
- Published
- 2020
15. Lower bounds for multicolor Ramsey numbers
- Author
-
Conlon, David and Ferber, Asaf
- Subjects
Mathematics - Combinatorics - Abstract
We give an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two., Comment: 4 pages
- Published
- 2020
16. Every graph contains a linearly sized induced subgraph with all degrees odd
- Author
-
Ferber, Asaf and Krivelevich, Michael
- Subjects
Mathematics - Combinatorics - Abstract
We prove that every graph $G$ on $n$ vertices with no isolated vertices contains an induced subgraph of size at least $n/10000$ with all degrees odd. This solves an old and well-known conjecture in graph theory.
- Published
- 2020
17. Singularity of random symmetric matrices -- simple proof
- Author
-
Ferber, Asaf
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
In this paper we give a simple, short, and self-contained proof for a non-trivial upper bound on the probability that a random $\pm 1$ symmetric matrix is singular., Comment: Comments are welcome!
- Published
- 2020
18. Dirac-type theorems in random hypergraphs
- Author
-
Ferber, Asaf and Kwan, Matthew
- Subjects
Mathematics - Combinatorics - Abstract
For positive integers $d
0$ and any "not too small" $p$, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and edge probability $p$ typically has the property that every spanning subgraph of $G$ with minimum degree at least $(1+\varepsilon)m_{d}(k,n)p$ has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of $m_{d}(k,n)$ without actually knowing its value. - Published
- 2020
19. The probability of selecting $k$ edge-disjoint Hamilton cycles in the complete graph
- Author
-
Ferber, Asaf, Haenni, Kaarel, and Jain, Vishesh
- Subjects
Mathematics - Combinatorics - Abstract
Let $H_1,\dots,H_k$ be Hamilton cycles in $K_n$, chosen independently and uniformly at random. We show, for $k = o(n^{1/100})$, that the probability of $H_1,\dots,H_k$ being edge-disjoint is $(1+o(1))e^{-2\binom{k}{2}}$. This extends a corresponding estimate obtained by Robbins in the case $k=2$., Comment: 8 pages
- Published
- 2020
20. Resilience of the Rank of Random Matrices
- Author
-
Ferber, Asaf, Luh, Kyle, and McKinley, Gweneth
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Let $M$ be an $n \times m$ matrix of independent Rademacher ($\pm 1$) random variables. It is well known that if $n \leq m$, then $M$ is of full rank with high probability. We show that this property is resilient to adversarial changes to $M$. More precisely, if $m \geq n + n^{1-\varepsilon/6}$, then even after changing the sign of $(1-\varepsilon)m/2$ entries, $M$ is still of full rank with high probability. Note that this is asymptotically best possible as one can easily make any two rows proportional with at most $m/2$ changes. Moreover, this theorem gives an asymptotic solution to a slightly weakened version of a conjecture made by Van Vu., Comment: 15 pages
- Published
- 2019
- Full Text
- View/download PDF
21. Co-degrees resilience for perfect matchings in random hypergraphs
- Author
-
Ferber, Asaf and Hirschfeld, Lior
- Subjects
Mathematics - Combinatorics - Abstract
In this paper we prove an optimal co-degrees resilience property for the binomial $k$-uniform hypergraph model $H_{n,p}^k$ with respect to perfect matchings. That is, for a sufficiently large $n$ which is divisible by $k$, and $p\geq C_k\log_n/n$, we prove that with high probability every subgraph $H\subseteq H^k_{n,p}$ with minimum co-degree (meaning, the number of supersets every set of size $k-1$ is contained in) at least $(1/2+o(1))np$ contains a perfect matching.
- Published
- 2019
- Full Text
- View/download PDF
22. Almost all Steiner triple systems are almost resolvable
- Author
-
Ferber, Asaf and Kwan, Matthew
- Subjects
Mathematics - Combinatorics - Abstract
We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).
- Published
- 2019
- Full Text
- View/download PDF
23. On the counting problem in inverse Littlewood--Offord theory
- Author
-
Ferber, Asaf, Jain, Vishesh, Luh, Kyle, and Samotij, Wojciech
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Let $\epsilon_1, \dotsc, \epsilon_n$ be i.i.d. Rademacher random variables taking values $\pm 1$ with probability $1/2$ each. Given an integer vector $\boldsymbol{a} = (a_1, \dotsc, a_n)$, its concentration probability is the quantity $\rho(\boldsymbol{a}):=\sup_{x\in \mathbb{Z}}\Pr(\epsilon_1 a_1+\dots+\epsilon_n a_n = x)$. The Littlewood-Offord problem asks for bounds on $\rho(\boldsymbol{a})$ under various hypotheses on $\boldsymbol{a}$, whereas the inverse Littlewood-Offord problem, posed by Tao and Vu, asks for a characterization of all vectors $\boldsymbol{a}$ for which $\rho(\boldsymbol{a})$ is large. In this paper, we study the associated counting problem: How many integer vectors $\boldsymbol{a}$ belonging to a specified set have large $\rho(\boldsymbol{a})$? The motivation for our study is that in typical applications, the inverse Littlewood-Offord theorems are only used to obtain such counting estimates. Using a more direct approach, we obtain significantly better bounds for this problem than those obtained using the inverse Littlewood--Offord theorems of Tao and Vu and of Nguyen and Vu. Moreover, we develop a framework for deriving upper bounds on the probability of singularity of random discrete matrices that utilizes our counting result. To illustrate the methods, we present the first `exponential-type' (i.e., $\exp(-n^c)$ for some positive constant $c$) upper bounds on the singularity probability for the following two models: (i) adjacency matrices of dense signed random regular digraphs, for which the previous best known bound is $O(n^{-1/4})$ due to Cook; and (ii) dense row-regular $\{0,1\}$-matrices, for which the previous best known bound is $O_{C}(n^{-C})$ for any constant $C>0$ due to Nguyen.
- Published
- 2019
24. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs
- Author
-
Ferber, Asaf and Jain, Vishesh
- Subjects
Mathematics - Combinatorics - Abstract
In this note, we prove that there exists a universal constant $c=\frac{43}{50}$ such that for every $k\in \mathbb{N}$ and every $d
- Published
- 2019
25. A quantitative Lov\'asz criterion for Property B
- Author
-
Ferber, Asaf and Shapira, Asaf
- Subjects
Mathematics - Combinatorics ,05D05 - Abstract
A well known observation of Lov\'asz is that if a hypergraph is not $2$-colorable, then at least one pair of its edges intersect at a single vertex. %This very simple criterion turned out to be extremly useful . In this short paper we consider the quantitative version of Lov\'asz's criterion. That is, we ask how many pairs of edges intersecting at a single vertex, should belong to a non $2$-colorable $n$-uniform hypergraph? Our main result is an {\em exact} answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollob\'as's two families theorem with Pluhar's randomized coloring algorithm., Comment: A note on Property B
- Published
- 2019
- Full Text
- View/download PDF
26. Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
- Author
-
Ferber, Asaf and Jain, Vishesh
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
Let $M_n$ denote a random symmetric $n \times n$ matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ and $-1$ with probability $1/2$ each). It is widely conjectured that $M_n$ is singular with probability at most $(2+o(1))^{-n}$. On the other hand, the best known upper bound on the singularity probability of $M_n$, due to Vershynin (2011), is $2^{-n^c}$, for some unspecified small constant $c > 0$. This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of $M_n$ is at most $2^{-n^{1/4}\sqrt{\log{n}}/1000}$ for all sufficiently large $n$. The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij., Comment: Final version incorporating referee comments
- Published
- 2018
- Full Text
- View/download PDF
27. Towards the linear arboricity conjecture
- Author
-
Ferber, Asaf, Fox, Jacob, and Jain, Vishesh
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics - Abstract
The linear arboricity of a graph $G$, denoted by $\text{la}(G)$, is the minimum number of edge-disjoint linear forests (i.e. forests in which every connected component is a path) in $G$ whose union covers all the edges of $G$. A famous conjecture due to Akiyama, Exoo, and Harary from 1980 asserts that $\text{la}(G)\leq \lceil (\Delta(G)+1)/2 \rceil$, where $\Delta(G)$ denotes the maximum degree of $G$. This conjectured upper bound would be best possible, as is easily seen by taking $G$ to be a regular graph. In this paper, we show that for every graph $G$, $\text{la}(G)\leq \frac{\Delta}{2}+O(\Delta^{2/3-\alpha})$ for some $\alpha > 0$, thereby improving the previously best known bound due to Alon and Spencer from 1992. For graphs which are sufficiently good spectral expanders, we give even better bounds. Our proofs of these results further give probabilistic polynomial time algorithms for finding such decompositions into linear forests.
- Published
- 2018
28. Long monotone trails in random edge-labelings of random graphs
- Author
-
Angel, Omer, Ferber, Asaf, Sudakov, Benny, and Tassion, Vincent
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Given a graph $G$ and a bijection $f : E(G)\rightarrow \{1, 2, \ldots,e(G)\}$, we say that a trail/path in $G$ is $f$-\emph{increasing} if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chv\'atal and Koml\'os raised the question of providing the worst-case estimates of the length of the longest increasing trail/path over all edge orderings of $K_n$. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is $n-1$, and the case of a path is still widely open. Recently Lavrov and Loh proposed to study the average case of this problem in which the edge ordering is chosen uniformly at random. They conjectured (and it was proved by Martinsson) that such an ordering with high probability (whp) contains an increasing Hamilton path. In this paper we consider random graph $G=G(n,p)$ and its edge ordering chosen uniformly at random. In this setting we determine whp the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average case of the result of Graham and Kleitman, showing that the random edge ordering of $K_n$ has whp an increasing trail of length $(1-o(1))en$ and this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erd\H{o}-Renyi graphs with $p=o(1)$.
- Published
- 2018
29. On the number of Hadamard matrices via anti-concentration
- Author
-
Ferber, Asaf, Jain, Vishesh, and Zhao, Yufei
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $Ax = b$, where the coordinates of the vector $x$ are restricted to take values in some small subset (e.g. $\{\pm 1\}$) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Hal\'asz. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Hal\'asz's inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Hal\'asz-type inequalities which beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses which are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of $n\times n$ Hadamard matrices, and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random $\{\pm 1\}$ matrix.
- Published
- 2018
30. 1-factorizations of pseudorandom graphs
- Author
-
Ferber, Asaf and Jain, Vishesh
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics - Abstract
A $1$-factorization of a graph $G$ is a collection of edge-disjoint perfect matchings whose union is $E(G)$. A trivial necessary condition for $G$ to admit a $1$-factorization is that $|V(G)|$ is even and $G$ is regular; the converse is easily seen to be false. In this paper, we consider the problem of finding $1$-factorizations of regular, pseudorandom graphs. Specifically, we prove that an $(n,d,\lambda)$-graph $G$ (that is, a $d$-regular graph on $n$ vertices whose second largest eigenvalue in absolute value is at most $\lambda$) admits a $1$-factorization provided that $n$ is even, $C_0\leq d\leq n-1$ (where $C_0$ is a universal constant), and $\lambda\leq d^{1-o(1)}$. In particular, since (as is well known) a typical random $d$-regular graph $G_{n,d}$ is such a graph, we obtain the existence of a $1$-factorization in a typical $G_{n,d}$ for all $C_0\leq d\leq n-1$, thereby extending to all possible values of $d$ results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed $d$. Moreover, we also obtain a lower bound for the number of distinct $1$-factorizations of such graphs $G$ which is off by a factor of $2$ in the base of the exponent from the known upper bound. This lower bound is better by a factor of $2^{nd/2}$ than the previously best known lower bounds, even in the simplest case where $G$ is the complete graph. Our proofs are probabilistic and can be easily turned into polynomial time (randomized) algorithms.
- Published
- 2018
31. Number of 1-factorizations of regular high-degree graphs
- Author
-
Ferber, Asaf, Jain, Vishesh, and Sudakov, Benny
- Subjects
Mathematics - Combinatorics - Abstract
A $1$-factor in an $n$-vertex graph $G$ is a collection of $\frac{n}{2}$ vertex-disjoint edges and a $1$-factorization of $G$ is a partition of its edges into edge-disjoint $1$-factors. Clearly, a $1$-factorization of $G$ cannot exist unless $n$ is even and $G$ is regular (that is, all vertices are of the same degree). The problem of finding $1$-factorizations in graphs goes back to a paper of Kirkman in 1847 and has been extensively studied since then. Deciding whether a graph has a $1$-factorization is usually a very difficult question. For example, it took more than 60 years and an impressive tour de force of Csaba, K\"uhn, Lo, Osthus and Treglown to prove an old conjecture of Dirac from the 1950s, which says that every $d$-regular graph on $n$ vertices contains a $1$-factorization, provided that $n$ is even and $d\geq 2\lceil \frac{n}{4}\rceil-1$. In this paper we address the natural question of estimating $F(n,d)$, the number of $1$-factorizations in $d$-regular graphs on an even number of vertices, provided that $d\geq \frac{n}{2}+\varepsilon n$. Improving upon a recent result of Ferber and Jain, which itself improved upon a result of Cameron from the 1970s, we show that $F(n,d)\geq \left((1+o(1))\frac{d}{e^2}\right)^{nd/2}$, which is asymptotically best possible., Comment: Final version, incorporating comments by referees. To appear in Combinatorica
- Published
- 2018
32. Every graph contains a linearly sized induced subgraph with all degrees odd
- Author
-
Ferber, Asaf and Krivelevich, Michael
- Published
- 2022
- Full Text
- View/download PDF
33. Supersaturated sparse graphs and hypergraphs
- Author
-
Ferber, Asaf, McKinley, Gweneth Anne, and Samotij, Wojciech
- Subjects
Mathematics - Combinatorics - Abstract
A central problem in extremal graph theory is to estimate, for a given graph $H$, the number of $H$-free graphs on a given set of $n$ vertices. In the case when $H$ is not bipartite, fairly precise estimates on this number are known. In particular, thirty years ago, Erd\H{o}s, Frankl, and R\"odl proved that there are $2^{(1+o(1))\text{ex}(n,H)}$ such graphs. In the bipartite case, however, nontrivial bounds have been proven only for relatively few special graphs $H$. We make a first attempt at addressing this enumeration problem for a general bipartite graph $H$. We show that an upper bound of $2^{O(\text{ex}(n,H))}$ on the number of $H$-free graphs with $n$ vertices follows merely from a rather natural assumption on the growth rate of $n \mapsto \text{ex}(n,H)$; an analogous statement remains true when $H$ is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd\H{o}s and Simonovits. The bounds on the number of $H$-free hypergraphs are derived from it using the method of hypergraph containers.
- Published
- 2017
34. Dirac-type theorems in random hypergraphs
- Author
-
Ferber, Asaf and Kwan, Matthew
- Published
- 2022
- Full Text
- View/download PDF
35. Counting Hamilton cycles in sparse random directed graphs
- Author
-
Ferber, Asaf, Kwan, Matthew, and Sudakov, Benny
- Subjects
Mathematics - Combinatorics - Abstract
Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if $p\ge(\log n+\omega(1))/n$ then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically $n!(p(1+o(1)))^{n}$. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically $n!(\log n/n(1+o(1)))^{n}$ directed Hamilton cycles.
- Published
- 2017
36. Spanning universality in random graphs
- Author
-
Ferber, Asaf and Nenadov, Rajko
- Subjects
Mathematics - Combinatorics - Abstract
A graph is said to be $\mathcal{H}(n, \Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\Delta$. Using a `matching-based' embedding technique introduced by Alon and F\"uredi, Dellamonica, Kohayakawa, R\"odl and Ruci\'nski showed that the random graph $G_{n,p}$ is asymptotically almost surely $\mathcal{H}(n, \Delta)$-universal for $p = \tilde \Omega(n^{-1/\Delta})$ - a threshold for the property that every subset of $\Delta$ vertices has a common neighbour. This bound has become a benchmark in the field and many subsequent results on embedding spanning structures of maximum degree $\Delta$ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that $G_{n,p}$ is almost surely $\mathcal{H}(n, \Delta)$-universal for $p = \tilde \Omega(n^{- 1/(\Delta-1/2)})$.
- Published
- 2017
37. Optimal Threshold for a Random Graph to be 2-Universal
- Author
-
Ferber, Asaf, Kronenberg, Gal, and Luh, Kyle
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
For a family of graphs $\mathcal{F}$, a graph $G$ is $\mathcal{F}$-universal if $G$ contains every graph in $\mathcal{F}$ as a (not necessarily induced) subgraph. For the family of all graphs on $n$ vertices and of maximum degree at most two, $\mathcal{H}(n,2)$, we prove that there exists a constant $C$ such that for $p \geq C \left( \frac{\log n}{n^2} \right)^{\frac{1}{3}}$, the binomial random graph $G(n,p)$ is typically $\mathcal{H}(n,2)$-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of Johansson, Kahn, and Vu for triangle factors. Our result improves significantly on the previous best bound of $p \geq C \left(\frac{\log n}{n}\right)^{\frac{1}{2}}$ due to Kim and Lee. In fact, we prove the stronger result that for the family of all graphs on $n$ vertices, of maximum degree at most two and of girth at least $\ell$, $\mathcal{H}^{\ell}(n,2)$, $G(n,p)$ is typically $\mathcal H^{\ell}(n,2)$-universal when $p \geq C \left(\frac{\log n}{n^{\ell -1}}\right)^{\frac{1}{\ell}}$. This result is also optimal up to the constant factor. Our results verify (in a weak form) a classical conjecture of Kahn and Kalai.
- Published
- 2016
38. Counting Hamilton decompositions of oriented graphs
- Author
-
Ferber, Asaf, Long, Eoin, and Sudakov, Benny
- Subjects
Mathematics - Combinatorics - Abstract
A Hamilton cycle in a directed graph $G$ is a cycle that passes through every vertex of $G$. A Hamiltonian decomposition of $G$ is a partition of its edge set into disjoint Hamilton cycles. In the late $60$s Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled by K\"uhn and Osthus, who proved more generally that every $r$-regular $n$-vertex oriented graph $G$ (without antiparallel edges) with $r=cn$ for some fixed $c>3/8$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this paper we address the natural question of estimating the number of such decompositions of $G$ and show that this number is $n^{(1-o(1))cn^2}$. In addition, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture., Comment: 17 pages
- Published
- 2016
39. Resilience for the Littlewood-Offord Problem
- Author
-
Bandeira, Afonso S., Ferber, Asaf, and Kwan, Matthew
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
Consider the sum $X(\xi)=\sum_{i=1}^n a_i\xi_i$, where $a=(a_i)_{i=1}^n$ is a sequence of non-zero reals and $\xi=(\xi_i)_{i=1}^n$ is a sequence of i.i.d. Rademacher random variables (that is, $\Pr[\xi_i=1]=\Pr[\xi_i=-1]=1/2$). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities $\Pr[X=x]$. In this paper we study a resilience version of the Littlewood-Offord problem: how many of the $\xi_i$ is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems., Comment: This version addresses referee's comments
- Published
- 2016
40. Packing Loose Hamilton Cycles
- Author
-
Ferber, Asaf, Luh, Kyle, Montealegre, Daniel, and Nguyen, Oanh
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
A subset $C$ of edges in a $k$-uniform hypergraph $H$ is a \emph{loose Hamilton cycle} if $C$ covers all the vertices of $H$ and there exists a cyclic ordering of these vertices such that the edges in $C$ are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random $k$-uniform hypergraph $H^k_{n,p}$ has vertex set $[n]$ and an edge set $E$ obtained by adding each $k$-tuple $e\in \binom{[n]}{k}$ to $E$ with probability $p$, independently at random. Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but $o(|E|)$ edges, referred to as the \emph{packing problem}. While it is known that the threshold probability for the appearance of a loose Hamilton cycle in $H^k_{n,p}$ is $p=\Theta\left(\frac{\log n}{n^{k-1}}\right)$, the best known bounds for the packing problem are around $p=\text{polylog}(n)/n$. Here we make substantial progress and prove the following asymptotically (up to a polylog$(n)$ factor) best possible result: For $p\geq \log^{C}n/n^{k-1}$, a random $k$-uniform hypergraph $H^k_{n,p}$ with high probability contains $N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$ edge-disjoint loose Hamilton cycles. Our proof utilizes and modifies the idea of "online sprinkling" recently introduced by Vu and the first author.
- Published
- 2016
41. Law of Iterated Logarithm for random graphs
- Author
-
Ferber, Asaf, Montealegre, Daniel, and Vu, Van
- Subjects
Mathematics - Combinatorics - Abstract
A milestone in Probability Theory is the law of the iterated logarithm (LIL), proved by Khinchin and independently by Kolmogorov in the 1920s, which asserts that for iid random variables $\{t_i\}_{i=1}^{\infty}$ with mean $0$ and variance $1$ $$ \Pr \left[ \limsup_{n\rightarrow \infty} \frac{ \sum_{i=1}^n t_i }{\sigma_n \sqrt {2 \log \log n }} =1 \right] =1 . $$ In this paper we prove that LIL holds for various functionals of random graphs and hypergraphs models. We first prove LIL for the number of copies of a fixed subgraph $H$. Two harder results concern the number of global objects: perfect matchings and Hamiltonian cycles. The main new ingredient in these results is a large deviation bound, which may be of independent interest. For random $k$-uniform hypergraphs, we obtain the Central Limit Theorem (CLT) and LIL for the number of Hamilton cycles., Comment: Fixed typos and added referee suggestions
- Published
- 2016
42. Packing trees of unbounded degrees in random graphs
- Author
-
Ferber, Asaf and Samotij, Wojciech
- Subjects
Mathematics - Combinatorics ,05C05, 05C80 - Abstract
In this paper, we address the problem of packing large trees in $G_{n,p}$. In particular, we prove the following result. Suppose that $T_1, \dotsc, T_N$ are $n$-vertex trees, each of which has maximum degree at most $(np)^{1/6} / (\log n)^6$. Then with high probability, one can find edge-disjoint copies of all the $T_i$ in the random graph $G_{n,p}$, provided that $p \geq (\log n)^{36}/n$ and $N \le (1-\varepsilon)np/2$ for a positive constant $\varepsilon$. Moreover, if each $T_i$ has at most $(1-\alpha)n$ vertices, for some positive $\alpha$, then the same result holds under the much weaker assumptions that $p \geq (\log n)^2/(cn)$ and $\Delta(T_i) \leq c np / \log n$ for some~$c$ that depends only on $\alpha$ and $\varepsilon$. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.
- Published
- 2016
- Full Text
- View/download PDF
43. Packing perfect matchings in random hypergraphs
- Author
-
Ferber, Asaf and Vu, Van
- Subjects
Mathematics - Combinatorics - Abstract
We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as \emph{online sprinkling}. As an illustrative application of this method, we show that for any fixed integer $k\geq 3$, the binomial $k$-uniform random hypergraph $H^{k}_{n,p}$ contains $N:=(1-o(1))\binom{n-1}{k-1}p$ edge-disjoint perfect matchings, provided $p\geq \frac{\log^{C}n}{n^{k-1}}$, where $C:=C(k)$ is an integer depending only on $k$. Our result for $N$ is asymptotically best optimal and for $p$ is optimal up to the $polylog(n)$ factor., Comment: Relevant citations have been added
- Published
- 2016
44. Embedding large graphs into a random graph
- Author
-
Ferber, Asaf, Luh, Kyle, and Nguyen, Oanh
- Subjects
Mathematics - Combinatorics ,05C80 - Abstract
In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 5$, $\varepsilon > 0$ and let $H$ be a graph on $(1-\varepsilon)n$ vertices and with maximum degree $\Delta$. We show that a random graph $G_{n,p}$ with high probability contains a copy of $H$, provided that $p\gg (n^{-1}\log^{1/\Delta}n)^{2/(\Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. We note that this $polylog$ term matches the conjectured threshold for the spanning case., Comment: Incorporated referee comments. To appear in Bulletin of the London Mathematical Society
- Published
- 2016
- Full Text
- View/download PDF
45. Random matrices: Law of the iterated logarithm
- Author
-
Ferber, Asaf, Montealegre, Daniel, and Vu, Van
- Subjects
Mathematics - Probability - Abstract
The theory of random matrices contains many central limit theorems. We have central limit theorems for eigenvalues statistics, for the log-determinant and log-permanent, for limiting distribution of individual eigenvalues in the bulk, and many others. In this notes, we discuss the following problem: Is it possible to prove the law of the iterated logarithm? We illustrate this possibility by showing that this is indeed the case for the log of the permanent of random Bernoulli matrices and pose open questions concerning several other matrix parameters.
- Published
- 2016
46. Packing and counting arbitrary Hamilton cycles in random digraphs
- Author
-
Ferber, Asaf and Long, Eoin
- Subjects
Mathematics - Combinatorics ,05C45, 05C20, 05C80 - Abstract
We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in ${\cal D}(n,p)$ for nearly optimal $p$ (up to a $\log ^cn$ factor). In particular, we show that given $t = (1-o(1))np$ Hamilton cycles $C_1,\ldots ,C_{t}$, each of which is oriented arbitrarily, a digraph $D \sim {\cal D}(n,p)$ w.h.p. contains edge disjoint copies of $C_1,\ldots ,C_t$, provided $p=\omega(\log ^3 n/n)$. We also show that given an arbitrarily oriented $n$-vertex cycle $C$, a random digraph $D \sim {\cal D}(n,p)$ w.h.p. contains $(1\pm o(1))n!p^n$ copies of $C$, provided $p \geq \log ^{1 + o(1)}n/n$., Comment: 13 pages
- Published
- 2016
47. Packing spanning graphs from separable families
- Author
-
Ferber, Asaf, Lee, Choongbum, and Mousset, Frank
- Subjects
Mathematics - Combinatorics - Abstract
Let $\mathcal G$ be a separable family of graphs. Then for all positive constants $\epsilon$ and $\Delta$ and for every sufficiently large integer $n$, every sequence $G_1,\dotsc,G_t\in\mathcal G$ of graphs of order $n$ and maximum degree at most $\Delta$ such that $e(G_1)+\dotsb+e(G_t) \leq (1-\epsilon)\binom{n}{2}$ packs into $K_n$. This improves results of B\"ottcher, Hladk\'y, Piguet, and Taraz when $\mathcal G$ is the class of trees and of Messuti, R\"odl, and Schacht in the case of a general separable family. The result also implies approximate versions of the Oberwolfach problem and of the Tree Packing Conjecture of Gy\'arf\'as (1976) for the case that all trees have maximum degree at most $\Delta$. The proof uses the local resilience of random graphs and a special multi-stage packing procedure.
- Published
- 2015
48. Lower bounds for multicolor Ramsey numbers
- Author
-
Conlon, David and Ferber, Asaf
- Published
- 2021
- Full Text
- View/download PDF
49. Strong games played on random graphs
- Author
-
Ferber, Asaf and Pfister, Pascal
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Computer Science and Game Theory ,Mathematics - Combinatorics - Abstract
In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique, a perfect matching, a Hamilton cycle, etc.). It is well known that Red can always ensure at least a draw in any strong game, but finding explicit winning strategies is a difficult and a quite rare task. We consider strong games played on the edge set of a random graph G ~ G(n,p) on n vertices. We prove, for sufficiently large $n$ and a fixed constant 0 < p < 1, that Red can w.h.p win the perfect matching game on a random graph G ~ G(n,p).
- Published
- 2015
50. Rainbow Hamilton cycles in random graphs and hypergraphs
- Author
-
Ferber, Asaf and Krivelevich, Michael
- Subjects
Mathematics - Combinatorics ,05C80, 05C15, 05C65, 05C45 - Abstract
Let $H$ be an edge colored hypergraph. We say that $H$ contains a \emph{rainbow} copy of a hypergraph $S$ if it contains an isomorphic copy of $S$ with all edges of distinct colors. We consider the following setting. A randomly edge colored random hypergraph $H\sim \mathcal H_c^k(n,p)$ is obtained by adding each $k$-subset of $[n]$ with probability $p$, and assigning it a color from $[c]$ uniformly, independently at random. As a first result we show that a typical $H\sim \mathcal H^2_c(n,p)$ (that is, a random edge colored graph) contains a rainbow Hamilton cycle, provided that $c=(1+o(1))n$ and $p=\frac{\log n+\log\log n+\omega(1)}{n}$. This is asymptotically best possible with respect to both parameters, and improves a result of Frieze and Loh. Secondly, based on an ingenious coupling idea of McDiarmid, we provide a general tool for tackling problems related to finding "nicely edge colored" structures in random graphs/hypergraphs. We illustrate the generality of this statement by presenting two interesting applications. In one application we show that a typical $H\sim \mathcal H^k_c(n,p)$ contains a rainbow copy of a hypergraph $S$, provided that $c=(1+o(1))|E(S)|$ and $p$ is (up to a multiplicative constant) a threshold function for the property of containment of a copy of $S$. In the second application we show that a typical $G\sim \mathcal H_{c}^2(n,p)$ contains $(1-o(1))np/2$ edge disjoint Hamilton cycles, each of which is rainbow, provided that $c=\omega(n)$ and $p=\omega(\log n/n)$.
- Published
- 2015
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.