Sidon spaces have been introduced by Bachoc, Serra and Z\'emor as the $q$-analogue of Sidon sets, classical combinatorial objects introduced by Simon Szidon. In 2018 Roth, Raviv and Tamo introduced the notion of $r$-Sidon spaces, as an extension of Sidon spaces, which may be seen as the $q$-analogue of $B_r$-sets, a generalization of classical Sidon sets. Thanks to their work, the interest on Sidon spaces has increased quickly because of their connection with cyclic subspace codes they pointed out. This class of codes turned out to be of interest since they can be used in random linear network coding. In this work we focus on a particular class of them, the one-orbit cyclic subspace codes, through the investigation of some properties of Sidon spaces and $r$-Sidon spaces, providing some upper and lower bounds on the possible dimension of their \textit{r-span} and showing explicit constructions in the case in which the upper bound is achieved. Moreover, we provide further constructions of $r$-Sidon spaces, arising from algebraic and combinatorial objects, and we show examples of $B_r$-sets constructed by means of them.
相關內容
Given a graph~$G$, the domination number, denoted by~$\gamma(G)$, is the minimum cardinality of a dominating set in~$G$. Dual to the notion of domination number is the packing number of a graph. A packing of~$G$ is a set of vertices whose pairwise distance is at least three. The packing number~$\rho(G)$ of~$G$ is the maximum cardinality of one such set. Furthermore, the inequality~$\rho(G) \leq \gamma(G)$ is well-known. Henning et al.\ conjectured that~$\gamma(G) \leq 2\rho(G)+1$ if~$G$ is subcubic. In this paper we progress towards this conjecture by showing that~${\gamma(G) \leq \frac{120}{49}\rho(G)}$ if~$G$ is a bipartite cubic graph. We also show that $\gamma(G) \leq 3\rho(G)$ if~$G$ is a maximal outerplanar graph, and that~$\gamma(G) \leq 2\rho(G)$ if~$G$ is a biconvex graph. Moreover, in the last case, we show that this upper bound is tight.
We introduce $\varepsilon$-approximate versions of the notion of Euclidean vector bundle for $\varepsilon \geq 0$, which recover the classical notion of Euclidean vector bundle when $\varepsilon = 0$. In particular, we study \v{C}ech cochains with coefficients in the orthogonal group that satisfy an approximate cocycle condition. We show that $\varepsilon$-approximate vector bundles can be used to represent classical vector bundles when $\varepsilon > 0$ is sufficiently small. We also introduce distances between approximate vector bundles and use them to prove that sufficiently similar approximate vector bundles represent the same classical vector bundle. This gives a way of specifying vector bundles over finite simplicial complexes using a finite amount of data, and also allows for some tolerance to noise when working with vector bundles in an applied setting. As an example, we prove a reconstruction theorem for vector bundles from finite samples. We give algorithms for the effective computation of low-dimensional characteristic classes of vector bundles directly from discrete and approximate representations and illustrate the usage of these algorithms with computational examples.
In 2006, Arnold, Falk, and Winther developed finite element exterior calculus, using the language of differential forms to generalize the Lagrange, Raviart--Thomas, Brezzi--Douglas--Marini, and N\'ed\'elec finite element spaces for simplicial triangulations. In a recent paper, Licht asks whether, on a single simplex, one can construct bases for these spaces that are invariant with respect to permuting the vertices of the simplex. For scalar fields, standard bases all have this symmetry property, but for vector fields, this question is more complicated: such invariant bases may or may not exist, depending on the polynomial degree of the element. In dimensions two and three, Licht constructs such invariant bases for certain values of the polynomial degree $r$, and he conjectures that his list is complete, that is, that no such basis exists for other values of $r$. In this paper, we show that Licht's conjecture is true in dimension two. However, in dimension three, we show that Licht's ideas can be extended to give invariant bases for many more values of $r$; we then show that this new larger list is complete. Along the way, we develop a more general framework for the geometric decomposition ideas of Arnold, Falk, and Winther.
Construction of a large class of Mutually Unbiased Bases (MUBs) for non-prime power composite dimensions ($d = k\times s$) is a long standing open problem, which leads to different construction methods for the class Approximate MUBs (AMUBs) by relaxing the criterion that the absolute value of the dot product between two vectors chosen from different bases should be $\leq \frac{\beta}{\sqrt{d}}$. In this chapter, we consider a more general class of AMUBs (ARMUBs, considering the real ones too), compared to our earlier work in [Cryptography and Communications, 14(3): 527--549, 2022]. We note that the quality of AMUBs (ARMUBs) constructed using RBD$(X,A)$ with $|X|= d$, critically depends on the parameters, $|s-k|$, $\mu$ (maximum number of elements common between any pair of blocks), and the set of block sizes. We present the construction of $\mathcal{O}(\sqrt{d})$ many $\beta$-AMUBs for composite $d$ when $|s-k|< \sqrt{d}$, using RBDs having block sizes approximately $\sqrt{d}$, such that $|\braket{\psi^l_i|\psi^m_j}| \leq \frac{\beta}{\sqrt{d}}$ where $\beta = 1 + \frac{|s-k|}{2\sqrt{d}}+ \mathcal{O}(d^{-1}) \leq 2$. Moreover, if real Hadamard matrix of order $k$ or $s$ exists, then one can construct at least $N(k)+1$ (or $N(s)+1$) many $\beta$-ARMUBs for dimension $d$, with $\beta \leq 2 - \frac{|s-k|}{2\sqrt{d}}+ \mathcal{O}(d^{-1})< 2$, where $N(w)$ is the number of MOLS$(w)$. This improves and generalizes some of our previous results for ARMUBs from two points, viz., the real cases are now extended to complex ones too. The earlier efforts use some existing RBDs, whereas here we consider new instances of RBDs that provide better results. Similar to the earlier cases, the AMUBs (ARMUBs) constructed using RBDs are in general very sparse, where the sparsity $(\epsilon)$ is $1 - \mathcal{O}(d^{-\frac{1}{2}})$.
Logical characterisations, rule formats and compositionality for input-output conformance simulation
Input-output conformance simulation (iocos) has been proposed by Gregorio-Rodr\'iguez, Llana and Mart\'inez-Torres as a simulation-based behavioural preorder underlying model-based testing. This relation is inspired by Tretmans' classic ioco relation, but has better worst-case complexity than ioco and supports stepwise refinement. The goal of this paper is to develop the theory of iocos by studying logical characterisations of this relation, rule formats for it and its compositionality. More specifically, this article presents characterisations of iocos in terms of modal logics and compares them with an existing logical characterisation for ioco proposed by Beohar and Mousavi. It also offers a characteristic-formula construction for iocos over finite processes in an extension of the proposed modal logics with greatest fixed points. A precongruence rule format for iocos and a rule format ensuring that operations take quiescence properly into account are also given. Both rule formats are based on the GSOS format by Bloom, Istrail and Meyer. The general modal decomposition methodology of Fokkink and van Glabbeek is used to show how to check the satisfaction of properties expressed in the logic for iocos in a compositional way for operations specified by rules in the precongruence rule format for iocos .
We consider finite element approximations to the optimal constant for the Hardy inequality with exponent $p=2$ in bounded domains of dimension $n=1$ or $n \geq 3$. For finite element spaces of piecewise linear and continuous functions on a mesh of size $h$, we prove that the approximate Hardy constant converges to the optimal Hardy constant at a rate proportional to $1/| \log h |^2$. This result holds in dimension $n=1$, in any dimension $n \geq 3$ if the domain is the unit ball and the finite element discretization exploits the rotational symmetry of the problem, and in dimension $n=3$ for general finite element discretizations of the unit ball. In the first two cases, our estimates show excellent quantitative agreement with values of the discrete Hardy constant obtained computationally.
A roadmap for an algebraic set $V$ defined by polynomials with coefficients in some real field, say $\mathbb{R}$, is an algebraic curve contained in $V$ whose intersection with all connected components of $V\cap\mathbb{R}^{n}$ is connected. These objects, introduced by Canny, can be used to answer connectivity queries over $V\cap \mathbb{R}^{n}$ provided that they are required to contain the finite set of query points $\mathcal{P}\subset V$; in this case,we say that the roadmap is associated to $(V, \mathcal{P})$. In this paper, we make effective a connectivity result we previously proved, to design a Monte Carlo algorithm which, on input (i) a finite sequence of polynomials defining $V$ (and satisfying some regularity assumptions) and (ii) an algebraic representation of finitely many query points $\mathcal{P}$ in $V$, computes a roadmap for $(V, \mathcal{P})$. This algorithm generalizes the nearly optimal one introduced by the last two authors by dropping a boundedness assumption on the real trace of $V$. The output size and running times of our algorithm are both polynomial in $(nD)^{n\log d}$, where $D$ is the maximal degree of the input equations and $d$ is the dimension of $V$. As far as we know, the best previously known algorithm dealing with such sets has an output size and running time polynomial in $(nD)^{n\log^2 n}$.
Extremal behaviour and convergence rates for sample--based geometric quantiles and half space depths
We consider the empirical versions of geometric quantile and halfspace depth, and study their extremal behaviour as a function of the sample size. The objective of this study is to establish connection between the rates of convergence and tail behaviour of the corresponding underlying distributions. The intricate interplay between the sample size and the parameter driving the extremal behaviour forms the main result of this analysis. In the process, we also fill certain gaps in the understanding of population versions of geometric quantile and halfspace depth.
The joint bidiagonalization (JBD) process iteratively reduces a matrix pair $\{A,L\}$ to two bidiagonal forms simultaneously, which can be used for computing a partial generalized singular value decomposition (GSVD) of $\{A,L\}$. The process has a nested inner-outer iteration structure, where the inner iteration usually can not be computed exactly. In this paper, we study the inaccurately computed inner iterations of JBD by first investigating influence of computational error of the inner iteration on the outer iteration, and then proposing a reorthogonalized JBD (rJBD) process to keep orthogonality of a part of Lanczos vectors. An error analysis of the rJBD is carried out to build up connections with Lanczos bidiagonalizations. The results are then used to investigate convergence and accuracy of the rJBD based GSVD computation. It is shown that the accuracy of computed GSVD components depend on the computing accuracy of inner iterations and condition number of $(A^T,L^T)^T$ while the convergence rate is not affected very much. For practical JBD based GSVD computations, our results can provide a guideline for choosing a proper computing accuracy of inner iterations in order to obtain approximate GSVD components with a desired accuracy. Numerical experiments are made to confirm our theoretical results.
The approach to giving a proof-theoretic semantics for IMLL taken by Gheorghiu, Gu and Pym is an interesting adaptation of the work presented by Sandqvist in his 2015 paper for IPL. What is particularly interesting is how naturally the move to the substructural setting provided a semantics for the multiplicative fragment of intuitionistic linear logic. Whilst ultimately the authors of the semantics for IMLL used their foundations to provide a semantics for bunched implication logic, it begs the question, what of the rest of intuitionistic linear logic? In this paper, I present a semantics for intuitionistic linear logic, by first presenting a semantics for the multiplicative and additive fragment after which we focus solely on considering the modality "of-course", thus giving a proof-theoretic semantics for intuitionistic linear logic.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191