Erd\H{o}s and West (Discrete Mathematics'85) considered the class of $n$ vertex intersection graphs which have a {\em $d$-dimensional} {\em $t$-representation}, that is, each vertex of a graph in the class has an associated set consisting of at most $t$ $d$-dimensional axis-parallel boxes. In particular, for a graph $G$ and for each $d \geq 1$, they consider $i_d(G)$ to be the minimum $t$ for which $G$ has such a representation. For fixed $t$ and $d$, they consider the class of $n$ vertex labeled graphs for which $i_d(G) \leq t$, and prove an upper bound of $(2nt+\frac{1}{2})d \log n - (n - \frac{1}{2})d \log(4\pi t)$ on the logarithm of size of the class. In this work, for fixed $t$ and $d$ we consider the class of $n$ vertex unlabeled graphs which have a {\em $d$-dimensional $t$-representation}, denoted by $\mathcal{G}_{t,d}$. We address the problem of designing a succinct data structure for the class $\mathcal{G}_{t,d}$ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). To this end, for each $n$ such that $td^2$ is in $o(n / \log n)$, we first prove a lower bound of $(2dt-1)n \log n - O(ndt \log \log n)$-bits on the size of any data structure for encoding an arbitrary graph that belongs to $\mathcal{G}_{t,d}$. We then present a $((2dt-1)n \log n + dt\log t + o(ndt \log n))$-bit data structure for $\mathcal{G}_{t,d}$ that supports navigational queries efficiently. Contrasting this data structure with our lower bound argument, we show that for each fixed $t$ and $d$, and for all $n \geq 0$ when $td^2$ is in $o(n/\log n)$ our data structure for $\mathcal{G}_{t,d}$ is succinct. As a byproduct, we also obtain succinct data structures for graphs of bounded boxicity (denoted by $d$ and $t = 1$) and graphs of bounded interval number (denoted by $t$ and $d=1$) when $td^2$ is in $o(n/\log n)$.
相關內容
Analysis-suitable $G^1$ (AS-$G^1$) multi-patch spline surfaces [4] are particular $G^1$-smooth multi-patch spline surfaces, which are needed to ensure the construction of $C^1$-smooth multi-patch spline spaces with optimal polynomial reproduction properties [16]. We present a novel local approach for the design of AS-$G^1$ multi-patch spline surfaces, which is based on the use of Lagrange multipliers. The presented method is simple and generates an AS-$G^1$ multi-patch spline surface by approximating a given $G^1$-smooth but non-AS-$G^1$ multi-patch surface. Several numerical examples demonstrate the potential of the proposed technique for the construction of AS-$G^1$ multi-patch spline surfaces and show that these surfaces are especially suited for applications in isogeometric analysis by solving the biharmonic problem, a particular fourth order partial differential equation, with optimal rates of convergence over them.
We embark on a systematic study of the $(k+1)$-th derivative of $x^{k-r}H(x^r)$, where $H(x):=-x\log x-(1-x)\log(1-x)$ is the binary entropy and $k>r\geq 1$ are integers. Our motivation is the conjectural entropy inequality $\alpha_k H(x^k)\geq x^{k-1}H(x)$, where $0<\alpha_k<1$ is given by a functional equation. The $k=2$ case was the key technical tool driving recent breakthroughs on the union-closed sets conjecture. We express $ \frac{d^{k+1}}{dx^{k+1}}x^{k-r}H(x^r)$ as a rational function, an infinite series, and a sum over generalized Stirling numbers. This allows us to reduce the proof of the entropy inequality for real $k$ to showing that an associated polynomial has only two real roots in the interval $(0,1)$, which also allows us to prove the inequality for fractional exponents such as $k=3/2$. The proof suggests a new framework for proving tight inequalities for the sum of polynomials times the logarithms of polynomials, which converts the inequality into a statement about the real roots of a simpler associated polynomial.
Most categorical models for dependent types have traditionally been heavily set based: contexts form a category, and for each we have a set of types in said context -- and for each type a set of terms of said type. This is the case for categories with families, categories with attributes, and natural models; in particular, all of them can be traced back to certain discrete Grothendieck fibrations. We extend this intuition to the case of general, non necessarily discrete, fibrations, so that over a given context one has not only a set but a category of types. We argue that the added structure can be attributed to a notion of subtyping that shares many features with that of coercive subtyping, in the sense that it is the product of thinking about subtyping as an abbreviation mechanism: we say that a given type $A'$ is a subtype of $A$ if there is a unique coercion from $A'$ to $A$. Whenever we need a term of type $A$, then, it suffices to have a term of type $A'$, which we can `plug-in' into $A$. For this version of subtyping we provide rules, coherences, and explicit models, and we compare and contrast it to coercive subtyping as introduced by Z. Luo and others. We conclude by suggesting how the tools we present can be employed in finding appropriate rules relating subtyping and certain type constructors.
We revisit $k$-Dominating Set, one of the first problems for which a tight $n^k-o(1)$ conditional lower bound (for $k\ge 3$), based on SETH, was shown (P\u{a}tra\c{s}cu and Williams, SODA 2007). However, the underlying reduction creates dense graphs, raising the question: how much does the sparsity of the graph affect its fine-grained complexity? We first settle the fine-grained complexity of $k$-Dominating Set in terms of both the number of nodes $n$ and number of edges $m$. Specifically, we show an $mn^{k-2-o(1)}$ lower bound based on SETH, for any dependence of $m$ on $n$. This is complemented by an $mn^{k-2+o(1)}$-time algorithm for all $k\ge 3$. For the $k=2$ case, we give a randomized algorithm that employs a Bloom-filter inspired hashing to improve the state of the art of $n^{\omega+o(1)}$ to $m^{\omega/2+o(1)}$. If $\omega=2$, this yields a conditionally tight bound for all $k\ge 2$. To study if $k$-Dominating Set is special in its sensitivity to sparsity, we consider a class of very related problems. The $k$-Dominating Set problem belongs to a type of first-order definable graph properties that we call monochromatic basic problems. These problems are the natural monochromatic variants of the basic problems that were proven complete for the class FOP of first-order definable properties (Gao, Impagliazzo, Kolokolova, and Williams, TALG 2019). We show that among these problems, $k$-Dominating Set is the only one whose fine-grained complexity decreases in sparse graphs. Only for the special case of reflexive properties, is there an additional basic problem that can be solved faster than $n^{k\pm o(1)}$ on sparse graphs. For the natural variant of distance-$r$ $k$-dominating set, we obtain a hardness of $n^{k-o(1)}$ under SETH for every $r\ge 2$ already on sparse graphs, which is tight for sufficiently large $k$.
A {\em packing coloring} of a graph $G$ is a mapping assigning a positive integer (a color) to every vertex of $G$ such that every two vertices of color $k$ are at distance at least $k+1$. The least number of colors needed for a packing coloring of $G$ is called the {\em packing chromatic number} of $G$. In this paper, we continue the study of the packing chromatic number of hypercubes and we improve the upper bounds reported by Torres and Valencia-Pabon ({\em P. Torres, M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Appl. Math. 190--191 (2015), 127--140}) by presenting recursive constructions of subsets of distant vertices making use of the properties of the extended Hamming codes. We also answer in negative a question on packing coloring of Cartesian products raised by Bre\v{s}ar, Klav\v{z}ar, and Rall ({\em Problem 5, Bre\v{s}ar et al., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees. Discrete Appl. Math. 155 (2007), 2303--2311.}).
A new $H(\textrm{divdiv})$-conforming finite element is presented, which avoids the need for super-smoothness by redistributing the degrees of freedom to edges and faces. This leads to a hybridizable mixed method with superconvergence for the biharmonic equation. Moreover, new finite element divdiv complexes are established. Finally, new weak Galerkin and $C^0$ discontinuous Galerkin methods for the biharmonic equation are derived.
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating system of the vertex set of a graph $G$ is called a vertex-separating path (tree) system of $G$ if the elements of the separating system are paths (trees) in the graph $G$. In this paper, we focus on the size of the smallest vertex-separating path (tree) system for different types of graphs, including trees, grids, and maximal outerplanar graphs.
Natural data observed in $\mathbb{R}^n$ is often constrained to an $m$-dimensional manifold $\mathcal{M}$, where $m < n$. This work focuses on the task of building theoretically principled generative models for such data. Current generative models learn $\mathcal{M}$ by mapping an $m$-dimensional latent variable through a neural network $f_\theta: \mathbb{R}^m \to \mathbb{R}^n$. These procedures, which we call pushforward models, incur a straightforward limitation: manifolds cannot in general be represented with a single parameterization, meaning that attempts to do so will incur either computational instability or the inability to learn probability densities within the manifold. To remedy this problem, we propose to model $\mathcal{M}$ as a neural implicit manifold: the set of zeros of a neural network. We then learn the probability density within $\mathcal{M}$ with a constrained energy-based model, which employs a constrained variant of Langevin dynamics to train and sample from the learned manifold. In experiments on synthetic and natural data, we show that our model can learn manifold-supported distributions with complex topologies more accurately than pushforward models.
For a permutation $\pi: [K]\rightarrow [K]$, a sequence $f: \{1,2,\cdots, n\}\rightarrow \mathbb R$ contains a $\pi$-pattern of size $K$, if there is a sequence of indices $(i_1, i_2, \cdots, i_K)$ ($i_1<i_2<\cdots<i_K$), satisfying that $f(i_a)<f(i_b)$ if $\pi(a)<\pi(b)$, for $a,b\in [K]$. Otherwise, $f$ is referred to as $\pi$-free. For the special case where $\pi = (1,2,\cdots, K)$, it is referred to as the monotone pattern. \cite{newman2017testing} initiated the study of testing $\pi$-freeness with one-sided error. They focused on two specific problems, testing the monotone permutations and the $(1,3,2)$ permutation. For the problem of testing monotone permutation $(1,2,\cdots,K)$, \cite{ben2019finding} improved the $(\log n)^{O(K^2)}$ non-adaptive query complexity of \cite{newman2017testing} to $O((\log n)^{\lfloor \log_{2} K\rfloor})$. Further, \cite{ben2019optimal} proposed an adaptive algorithm with $O(\log n)$ query complexity. However, no progress has yet been made on the problem of testing $(1,3,2)$-freeness. In this work, we present an adaptive algorithm for testing $(1,3,2)$-freeness. The query complexity of our algorithm is $O(\epsilon^{-2}\log^4 n)$, which significantly improves over the $O(\epsilon^{-7}\log^{26}n)$-query adaptive algorithm of \cite{newman2017testing}. This improvement is mainly achieved by the proposal of a new structure embedded in the patterns.
Given a Binary Decision Diagram $B$ of a Boolean function $\varphi$ in $n$ variables, it is well known that all $\varphi$-models can be enumerated in output polynomial time, and in a compressed way (using don't-care symbols). We show that all $N$ many $\varphi$-models of fixed Hamming-weight $k$ can be enumerated as well in time polynomial in $n$ and $|B|$ and $N$. Furthermore, using novel wildcards, again enables a compressed enumeration of these models.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191