A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from their labels. We give tight bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a well-behaved growth function between $2^{O(n \log n)}$ and $2^{O(n^{2-\delta})}$ for any $\delta > 0$. Specifically, we show that for any function $f: \mathbb N \to \mathbb R$ satisfying $\log n \leqslant f(n) \leqslant n^{1-\delta}$ for any fixed $\delta > 0$, and some sub-multiplicative condition, there are monotone graph classes with growth $2^{O(nf(n))}$ that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand, any such class does admit adjacency labels of size $O(f(n)\log n)$. Surprisingly this tight bound is a $\Theta(\log n)$ factor away from the information-theoretic bound of $O(f(n))$. The special case when $f = \log$ implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes.
相關內容
A technique that allows a formation-enforcing control (FEC) derived from graph rigidity theory to interface with a realistic relative localization system onboard lightweight Unmanned Aerial Vehicles (UAVs) is proposed in this paper. The proposed methodology enables reliable real-world deployment of UAVs in tight formation using real relative localization systems burdened by non-negligible sensory noise, which is typically not fully taken into account in FEC algorithms. The proposed solution is based on decomposition of the gradient descent-based FEC command into interpretable elements, and then modifying these individually based on the estimated distribution of sensory noise, such that the resulting action limits the probability of overshooting the desired formation. The behavior of the system has been analyzed and the practicality of the proposed solution has been compared to pure gradient-descent in real-world experiments where it presented significantly better performance in terms of oscillations, deviation from the desired state and convergence time.
We describe the classification of orthogonal arrays OA$(2048,14,2,7)$, or, equivalently, completely regular $\{14;2\}$-codes in the $14$-cube ($30848$ equivalence classes). In particular, we find that there is exactly one almost-OA$(2048,14,2,7+1)$, up to equivalence. As derived objects, OA$(1024,13,2,6)$ ($202917$ classes) and completely regular $\{12,2;2,12\}$- and $\{14,12,2;2,12,14\}$-codes in the $13$- and $14$-cubes, respectively, are also classified. Keywords: binary orthogonal array, completely regular code, binary 1-perfect code.
We introduce a novel approach for decomposing and learning every scale of a given multiscale objective function in $\mathbb{R}^d$, where $d\ge 1$. This approach leverages a recently demonstrated implicit bias of the optimization method of gradient descent by Kong and Tao, which enables the automatic generation of data that nearly follow Gibbs distribution with an effective potential at any desired scale. One application of this automated effective potential modeling is to construct reduced-order models. For instance, a deterministic surrogate Hamiltonian model can be developed to substantially soften the stiffness that bottlenecks the simulation, while maintaining the accuracy of phase portraits at the scale of interest. Similarly, a stochastic surrogate model can be constructed at a desired scale, such that both its equilibrium and out-of-equilibrium behaviors (characterized by auto-correlation function and mean path) align with those of a damped mechanical system with the original multiscale function being its potential. The robustness and efficiency of our proposed approach in multi-dimensional scenarios have been demonstrated through a series of numerical experiments. A by-product of our development is a method for anisotropic noise estimation and calibration. More precisely, Langevin model of stochastic mechanical systems may not have isotropic noise in practice, and we provide a systematic algorithm to quantify its covariance matrix without directly measuring the noise. In this case, the system may not admit closed form expression of its invariant distribution either, but with this tool, we can design friction matrix appropriately to calibrate the system so that its invariant distribution has a closed form expression of Gibbs.
Let $G$ be a graph of order $n$. A classical upper bound for the domination number of a graph $G$ having no isolated vertices is $\lfloor\frac{n}{2}\rfloor$. However, for several families of graphs, we have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$ which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph $G$ to have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$, and some conditions sufficient for a graph $G$ to have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$. We also present a characterization of all connected graphs $G$ of order $n$ with $\gamma(G) = \lfloor\sqrt{n}\rfloor$. Further, we prove that for a graph $G$ not satisfying $rad(G)=diam(G)=rad(\overline{G})=diam(\overline{G})=2$, deciding whether $\gamma(G) \le \lfloor\sqrt{n}\rfloor$ or $\gamma(\overline{G}) \le \lfloor\sqrt{n}\rfloor$ can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph $G$.
For a commutative ring $R,$ with non-zero zero divisors $Z^{\ast}(R)$. The zero divisor graph $\Gamma(R)$ is a simple graph with vertex set $Z^{\ast}(R)$, and two distinct vertices $x,y\in V(\Gamma(R))$ are adjacent if and only if $x\cdot y=0.$ In this note, provide counter examples to the eigenvalues, the energy and the second Zagreb index related to zero divisor graphs of rings obtained in [Johnson and Sankar, J. Appl. Math. Comp. (2023), \cite{johnson}]. We correct the eigenvalues (energy) and the Zagreb index result for the zero divisor graphs of ring $\mathbb{Z}_{p}[x]/\langle x^{4} \rangle.$ We show that for any prime $p$, $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ is non-hyperenergetic and for prime $p\geq 3$, $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ is hypoenergetic. We give a formulae for the topological indices of $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ and show that its Zagreb indices satisfy Hansen and Vuki$\check{c}$cevi\'c conjecture \cite{hansen}.
Gradient-enhanced Kriging (GE-Kriging) is a well-established surrogate modelling technique for approximating expensive computational models. However, it tends to get impractical for high-dimensional problems due to the size of the inherent correlation matrix and the associated high-dimensional hyper-parameter tuning problem. To address these issues, a new method, called sliced GE-Kriging (SGE-Kriging), is developed in this paper for reducing both the size of the correlation matrix and the number of hyper-parameters. We first split the training sample set into multiple slices, and invoke Bayes' theorem to approximate the full likelihood function via a sliced likelihood function, in which multiple small correlation matrices are utilized to describe the correlation of the sample set rather than one large one. Then, we replace the original high-dimensional hyper-parameter tuning problem with a low-dimensional counterpart by learning the relationship between the hyper-parameters and the derivative-based global sensitivity indices. The performance of SGE-Kriging is finally validated by means of numerical experiments with several benchmarks and a high-dimensional aerodynamic modeling problem. The results show that the SGE-Kriging model features an accuracy and robustness that is comparable to the standard one but comes at much less training costs. The benefits are most evident for high-dimensional problems with tens of variables.
The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$-path $P$ so that all internal vertices of $P$ are not in $S$. This is also said as $x,y$ are visible with respect to $S$, or $S$-visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside $S$. Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters. The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankievicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Tur\'an problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.
We show that there are sampling projections on arbitrary $n$-dimensional subspaces of $B(D)$ with at most $2n$ samples and norm of order $\sqrt{n}$, where $B(D)$ is the space of complex-valued bounded functions on a set $D$. This gives a more explicit form of the Kadets-Snobar theorem for the uniform norm and improves upon Auerbach's lemma. We discuss consequences for optimal recovery in $L_p$.
Let $G$ be a simple finite connected graph with vertex set $V(G) = \{v_1,v_2,\ldots,v_n\}$. Denote the degree of vertex $v_i$ by $d_i$ for all $1 \leq i \leq n$. The Randi\'c matrix of $G$, denoted by $R(G) = [r_{i,j}]$, is the $n \times n$ matrix whose $(i,j)$-entry $r_{i,j}$ is $r_{i,j} = 1/\sqrt{d_id_j}$ if $v_i$ and $v_j$ are adjacent in $G$ and 0 otherwise. A tree is a connected acyclic graph. A level-wise regular tree is a tree rooted at one vertex $r$ or two (adjacent) vertices $r$ and $r'$ in which all vertices with the minimum distance $i$ from $r$ or $r'$ have the same degree $m_i$ for $0 \leq i \leq h$, where $h$ is the height of $T$. In this paper, we give a complete characterization of the eigenvalues with their multiplicity of the Randi\'c matrix of level-wise regular trees. We prove that the eigenvalues of the Randi\'c matrix of a level-wise regular tree are the eigenvalues of the particular tridiagonal matrices, which are formed using the degree sequence $(m_0,m_1,\ldots,m_{h-1})$ of level-wise regular trees.
In this contribution we deal with Gaussian quadrature rules based on orthogonal polynomials associated with a weight function $w(x)= x^{\alpha} e^{-x}$ supported on an interval $(0,z)$, $z>0.$ The modified Chebyshev algorithm is used in order to test the accuracy in the computation of the coefficients of the three-term recurrence relation, the zeros and weights, as well as the dependence on the parameter $z.$
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191