Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCauchy-Davenport Theorem for linear maps: Simplification and Extension
63
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give a new proof of the Cauchy-Davenport Theorem for linear maps given by Herdade et al., (2015). This theorem gives a lower bound on the size of the image of a linear map on a grid. Our proof is purely combinatorial and offers a partial insight into the range of parameters not handled previously.
rate research
Read More
We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets $A,B$ of the finite field $mathbb{F}_p$, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset $A+B$ in terms of the sizes of the sets $A$ and $B$. Our theorem considers a general linear map $L: mathbb{F}_p^n to mathbb{F}_p^m$, and subsets $A_1, ldots, A_n subseteq mathbb{F}_p$, and gives a lower bound on the size of $L(A_1 times A_2 times ldots times A_n)$ in terms of the sizes of the sets $A_1, ldots, A_n$. Our proof uses Alons Combinatorial Nullstellensatz and a variation of the polynomial method.
A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence $x$ over a finite alphabet is ultimately periodic if and only if, for some $n$, the number of different factors of length $n$ appearing in $x$ is less than $n+1$. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let $dge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $ZZ^d$ definable by a first order formula in the Presburger arithmetic $<ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension $d$ and characterize sets of $ZZ^d$ definable in $<ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
The beautiful Beraha-Kahane-Weiss theorem has found many applications within graph theory, allowing for the determination of the limits of root of graph polynomials in settings as vast as chromatic polynomials, network reliability, and generating polynomials related to independence and domination. Here we extend the class of functions to which the BKW theorem can be applied, and provide some applications in combinatorics.
By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no truly subquadratic algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.
The aim of this note is to characterize all pairs of sufficiently smooth functions for which the mean value in the Cauchy Mean Value Theorem is taken at a point which has a well-determined position in the interval. As an application of this result, a partial answer is given to a question posed by Sahoo and Riedel.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
