Improving a 2003 result of Bohman and Holzman, we show that for $n \geq 1$, the Shannon capacity of the complement of the $2n+1$-cycle is at least $(2^{r_n} + 1)^{1/r_n} = 2 + \Omega(2^{-r_n}/r_n)$, where $r_n = \exp(O((\log n)^2))$ is the number of partitions of $2(n-1)$ into powers of $2$.
相關內容
We consider a Tamari interval of size $n$ (i.e., a pair of Dyck paths which are comparable for the Tamari relation) chosen uniformly at random. We show that the height of a uniformly chosen vertex on the upper or lower path scales as $n^{3/4}$, and has an explicit limit law. By the Bernardi-Bonichon bijection, this result also describes the height of points in the canonical Schnyder trees of a uniform random plane triangulation of size $n$. The exact solution of the model is based on polynomial equations with one and two catalytic variables. To prove the convergence from the exact solution, we use a version of moment pumping based on D-finiteness, which is essentially automatic and should apply to many other models. We are not sure to have seen this simple trick used before. It would be interesting to study the universality of this convergence for decomposition trees associated to positive Bousquet-M\'elou--Jehanne equations.
A well-known result due to Caro (1979) and Wei (1981) states that every graph $G$ has an independent set of size at least $\sum_{v\in V(G)} \frac{1}{d(v) + 1}$, where $d(v)$ denotes the degree of vertex $v$. Alon, Kahn, and Seymour (1987) showed the following generalization: For every $k\geq 0$, every graph $G$ has a $k$-degenerate induced subgraph with at least $\sum_{v \in V(G)}\min\{1, \frac {k+1}{d(v)+1}\}$ vertices. In particular, for $k=1$, every graph $G$ with no isolated vertices has an induced forest with at least $\sum_{v\in V(G)} \frac{2}{d(v) + 1}$ vertices. Akbari, Amanihamedani, Mousavi, Nikpey, and Sheybani (2019) conjectured that, if $G$ has minimum degree at least $2$, then one can even find an induced linear forest of that order in $G$, that is, a forest where each component is a path. In this paper, we prove this conjecture and show a number of related results. In particular, if there is no restriction on the minimum degree of $G$, we show that there are infinitely many ``best possible'' functions $f$ such that $\sum_{v\in V(G)} f(d(v))$ is a lower bound on the maximum order of a linear forest in $G$, and we give a full characterization of all such functions $f$.
The $n$-vehicle exploration problem (NVEP) is a combinatorial search problem, which tries to find a permutation of $n$ vehicles to make one of the vehicles travel the maximal distance. Assuming the $n$ vehicles travel together, with some vehicles being used to refuel others, and at last all the vehicles return to the start point. NVEP has a fractional form of objective function, and its computational complexity of general case remains open. Given a directed graph $G$, if it has a Hamiltonian path, then the Hamiltonian path can be reduced in polynomial time to a single instance of NVEP, in which the traveling distance is at least $n$. The total length consists of $n$ parts, each of which is required to equal to $1$. We prove that $G$ has a hamiltonian path of total weight of $n$ if and only if the reduced NVEP instance has a sequence of length at least $n$ with each term equals to $1$. Therefore we show that Hamiltonian path $\leq_P$ NVEP, and consequently prove that NVEP is NP-complete.
We present an estimator of the covariance matrix $\Sigma$ of random $d$-dimensional vector from an i.i.d. sample of size $n$. Our sole assumption is that this vector satisfies a bounded $L^p-L^2$ moment assumption over its one-dimensional marginals, for some $p\geq 4$. Given this, we show that $\Sigma$ can be estimated from the sample with the same high-probability error rates that the sample covariance matrix achieves in the case of Gaussian data. This holds even though we allow for very general distributions that may not have moments of order $>p$. Moreover, our estimator can be made to be optimally robust to adversarial contamination. This result improves the recent contributions by Mendelson and Zhivotovskiy and Catoni and Giulini, and matches parallel work by Abdalla and Zhivotovskiy (the exact relationship with this last work is described in the paper).
One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a realizable sample for $B$ is a signed subset $X=(X^+,X^-)$ of $V$ such that $B$ contains $X^+$ and is disjoint from $X^-$. A proper sample compression scheme of size $k$ consists of a compressor and a reconstructor. The compressor maps any realizable sample $X$ to a subsample $X'$ of size at most $k$. The reconstructor maps each such subsample $X'$ to a ball $B'$ of $G$ such that $B'$ includes $X^+$ and is disjoint from $X^-$. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.
Quantifying the heterogeneity is an important issue in meta-analysis, and among the existing measures, the $I^2$ statistic is the most commonly used measure in the literature. In this paper, we show that the $I^2$ statistic was, in fact, defined as problematic or even completely wrong from the very beginning. To confirm this statement, we first present a motivating example to show that the $I^2$ statistic is heavily dependent on the study sample sizes, and consequently it may yield contradictory results for the amount of heterogeneity. Moreover, by drawing a connection between ANOVA and meta-analysis, the $I^2$ statistic is shown to have, mistakenly, applied the sampling errors of the estimators rather than the variances of the study populations. Inspired by this, we introduce an Intrinsic measure for Quantifying the heterogeneity in meta-analysis, and meanwhile study its statistical properties to clarify why it is superior to the existing measures. We further propose an optimal estimator, referred to as the IQ statistic, for the new measure of heterogeneity that can be readily applied in meta-analysis. Simulations and real data analysis demonstrate that the IQ statistic provides a nearly unbiased estimate of the true heterogeneity and it is also independent of the study sample sizes.
Recently an algorithm was given in [Garde & Hyv\"onen, SIAM J. Math. Anal., 2024] for exact direct reconstruction of any $L^2$ perturbation from linearised data in the two-dimensional linearised Calder\'on problem. It was a simple forward substitution method based on a 2D Zernike basis. We now consider the three-dimensional linearised Calder\'on problem in a ball, and use a 3D Zernike basis to obtain a method for exact direct reconstruction of any $L^3$ perturbation from linearised data. The method is likewise a forward substitution, hence making it very efficient to numerically implement. Moreover, the 3D method only makes use of a relatively small subset of boundary measurements for exact reconstruction, compared to a full $L^2$ basis of current densities.
Near-Optimal differentially private low-rank trace regression with guaranteed private initialization
We study differentially private (DP) estimation of a rank-$r$ matrix $M \in \RR^{d_1\times d_2}$ under the trace regression model with Gaussian measurement matrices. Theoretically, the sensitivity of non-private spectral initialization is precisely characterized, and the differential-privacy-constrained minimax lower bound for estimating $M$ under the Schatten-$q$ norm is established. Methodologically, the paper introduces a computationally efficient algorithm for DP-initialization with a sample size of $n \geq \wt O (r^2 (d_1\vee d_2))$. Under certain regularity conditions, the DP-initialization falls within a local ball surrounding $M$. We also propose a differentially private algorithm for estimating $M$ based on Riemannian optimization (DP-RGrad), which achieves a near-optimal convergence rate with the DP-initialization and sample size of $n \geq \wt O(r (d_1 + d_2))$. Finally, the paper discusses the non-trivial gap between the minimax lower bound and the upper bound of low-rank matrix estimation under the trace regression model. It is shown that the estimator given by DP-RGrad attains the optimal convergence rate in a weaker notion of differential privacy. Our powerful technique for analyzing the sensitivity of initialization requires no eigengap condition between $r$ non-zero singular values.
In 2017, Aharoni proposed the following generalization of the Caccetta-H\"{a}ggkvist conjecture: if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil n/r \rceil$. In this paper, we prove that, for fixed $r$, Aharoni's conjecture holds up to an additive constant. Specifically, we show that for each fixed $r \geq 1$, there exists a constant $c_r$ such that if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $n/r + c_r$.
For the Euler scheme of the stochastic linear evolution equations, discrete stochastic maximal $ L^p $-regularity estimate is established, and a sharp error estimate in the norm $ \|\cdot\|_{L^p((0,T)\times\Omega;L^q(\mathcal O))} $, $ p,q \in [2,\infty) $, is derived via a duality argument.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191