Search results for " Combinatoric"

Reverse-safe data structures for text indexing

2021

We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstruction of the data they encode (i.e., they cannot be easily reversed). A data structure D is called z-reverse-safe when there exist at least z datasets with the same set of answers as the ones stored by D. The main challenge is to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and has size close to the size of the original dataset it encodes. Given a text of length n and an integer z, we propose an algorithm which constructs a z-reverse-safe data structure that has size O(n) and answers pattern matching queries of length at most d optim…

Packing colorings of subcubic outerplanar graphs

2018

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…

Integrability of orthogonal projections, and applications to Furstenberg sets

2022

Let $\mathcal{G}(d,n)$ be the Grassmannian manifold of $n$-dimensional subspaces of $\mathbb{R}^{d}$, and let $\pi_{V} \colon \mathbb{R}^{d} \to V$ be the orthogonal projection. We prove that if $\mu$ is a compactly supported Radon measure on $\mathbb{R}^{d}$ satisfying the $s$-dimensional Frostman condition $\mu(B(x,r)) \leq Cr^{s}$ for all $x \in \mathbb{R}^{d}$ and $r > 0$, then $$\int_{\mathcal{G}(d,n)} \|\pi_{V}\mu\|_{L^{p}(V)}^{p} \, d\gamma_{d,n}(V) \tfrac{1}{2}$ and $t \geq 1 + \epsilon$ for a small absolute constant $\epsilon > 0$. We also prove a higher dimensional analogue of this estimate for codimension-1 Furstenberg sets in $\mathbb{R}^{d}$. As another corollary of our method,…

A note on higher order Melnikov functions

2005

We present several classes of planar polynomial Hamilton systems and their polynomial perturbations leading to vanishing of the first Melnikov integral. We discuss the form of higher order Melnikov integrals. In particular, we present new examples where the second order Melnikov integral is not an Abelian integral.

Quasi-linear time computation of the abelian periods of a word

2012

Computing abelian periods in words

2011

International audience

Automorphisms of hyperelliptic GAG-codes

2009

Abstract We determine the n –automorphism group of generalized algebraic-geometry codes associated with rational, elliptic and hyperelliptic function fields. Such group is, up to isomorphism, a subgroup of the automorphism group of the underlying function field.

Additivity of affine designs

2020

We show that any affine block design $$\mathcal{D}=(\mathcal{P},\mathcal{B})$$ is a subset of a suitable commutative group $${\mathfrak {G}}_\mathcal{D},$$ with the property that a k-subset of $$\mathcal{P}$$ is a block of $$\mathcal{D}$$ if and only if its k elements sum up to zero. As a consequence, the group of automorphisms of any affine design $$\mathcal{D}$$ is the group of automorphisms of $${\mathfrak {G}}_\mathcal{D}$$ that leave $$\mathcal P$$ invariant. Whenever k is a prime p,  $${\mathfrak {G}}_\mathcal{D}$$ is an elementary abelian p-group.

Tsen–Lang Theory for Cpi-fields

1995

Linear and cyclic radio k-labelings of trees

2007

International audience; Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two distinct vertices x and y, where dG(x,y) is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear (cyclic, respectively) radio k-labeling number of G is the minimum span of a linear (cyclic, respectively) radio k-labeling of G. In this p…