Search

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ász. 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ász'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ász-type inequalities that 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 that 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. [ABSTRACT FROM AUTHOR]

Racial and ethnic disparities in obstetrics are prevalent in the United States (US). We aimed to assess whether the success rate of external cephalic version (ECV) is affected by maternal race/ethnicity. We conducted a retrospective analysis based on the CDC Natality Live Birth database for 2016–2018. We compared the success rates of ECV across US pregnant women of different racial/ethnic groups (non-Hispanic Whites, non-Hispanic Blacks, non-Hispanic Asians, and Hispanics) using the Pearson chi-square test and used multivariate logistic regression to control for confounding variables. Statistical signiciance was determined as p<0.05 and results were displayed as adjusted odds ratios (aOR) with 95% confidence intervals (95% CI). Of the 11,150,527 births, 26,255 women underwent an ECV and met inclusion criteria. The overall ECV success rate was 52.75% (13,850 women). Non-Hispanic Blacks had the highest ECV success rate (64.52%), followed by Hispanics (59.21%) and non-Hispanic Asians (55.51%). These rates were significantly higher than those of non-Hispanic Whites (49.27%, p<0.001). Non-Hispanic Blacks were associated with the highest success rate compared to non-Hispanic Whites (adjusted OR 1.95, 95% CI 1.77–2.15). The success rate of ECV varies among different maternal racial/ethnic groups. Non-Hispanic White women have the lowest ECV success rate, while non-Hispanic Black women have the highest ECV success rate. [ABSTRACT FROM AUTHOR]

Consider a random $n\times n$ zero-one matrix with 'sparsity' 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. [ABSTRACT FROM AUTHOR]

Let ε1,...,εn be independent and identically distributed Rademacher random variables taking values ±1 with probability 1/2 each. Given an integer vector a=(a1,...,an), its concentration probability is the quantity ρ(a):=supx∈ZPr(ε1a1+⋯+εnan=x). The Littlewood–Offord problem asks for bounds on ρ(a) under various hypotheses on a, whereas the inverse Littlewood–Offord problem, posed by Tao and Vu, asks for a characterization of all vectors a for which ρ(a) is large. In this paper, we study the associated counting problem: How many integer vectors a belonging to a specified set have large ρ(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' (that is, exp(−cnc) 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 OC(n−C) for any constant C>0, due to Nguyen. [ABSTRACT FROM AUTHOR]

Let M be an n × m matrix of independent Rademacher (±1) random variables. It is well known that if n ≤ 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 ≥ n + n1−ε/6, then even after changing the sign of (1 – ε)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 in [17]. [ABSTRACT FROM AUTHOR]

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, Erd̋s, Frankl, and Rödl proved that there are 2(1+ o (1))ex(n , H) such graphs. In the bipartite case, however, bounds of the form 2 O (ex(n , H)) have been proven only for relatively few special graphs H. As a 1st attempt at addressing this problem in full generality, we show that such a bound follows merely from a rather natural assumption on the growth rate of n ↦ 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̋s and Simonovits. The bounds on the number of H -free hypergraphs are derived from it using the method of hypergraph containers. [ABSTRACT FROM AUTHOR]

Given a graph G and a bijection ƒ : E(G) → {1, 2, . . . ,e(G)}, we say that a trail/path in G is ƒ-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. 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 wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path. In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1−o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1). [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of packing large trees in Gn,p. In particular, we prove the following result. Suppose that T1,...,TN are n‐vertex trees, each of which has maximum degree at most (np)1/6/(logn)6. Then with high probability, one can find edge‐disjoint copies of all the Ti in the random graph Gn,p, provided that p⩾(logn)36/n and N⩽(1−ε)np/2 for a positive constant ε. Moreover, if each Ti has at most (1−α)n vertices, for some positive α, then the same result holds under the much weaker assumptions that p⩾(logn)2/(cn) and Δ(Ti)⩽cnp/logn for some c that depends only on α and ε. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results. [ABSTRACT FROM AUTHOR]