Approximating the maximum size of a k-regular induced subgraph by an upper bound on the co-k-plex number

Let ?? _k and $ {\hat{\alpha }_k} $ denote respectively the maximum cardinality of a k-regular induced subgraph and the co-k-plex number of a given graph. In this paper, we introduce a convex quadratic programming upper bound on $ {\hat{\alpha }_k} $ , which is also an upper bound on ?? _k . The new bound denoted by $ {\hat{\upsilon }_k} $ improves the bound ?? _k given in [3]. For regular graphs, we prove a necessary and sufficient condition under which $ {\hat{\upsilon }_k} $ equals ?? _k . We also show that the graphs for which $ {\hat{\alpha }_k} $ equals $ {\hat{\upsilon }_k} $ coincide with those such that ?? _k equals ?? _k . Next, an improvement of $ {\hat{\upsilon }_k} $ denoted by $ {\hat{\vartheta }_k} $ is proposed, which is not worse than the upper bound ? _k for ?? _k introduced in [8]. Finally, some computational experiments performed to appraise the gains brought by $ {\hat{\vartheta }_k} $ are reported.     

Bounds on the degree of APN polynomials: the case of x ?1?+?g(x)

In this paper we consider APN functions ${f:\mathcal{F}_{2^m}\to \mathcal{F}_{2^m}}$ of the form f(x) = x ^?1 + g(x) where g is any non ${\mathcal{F}_{2}}$ -affine polynomial. We prove a lower bound on the degree of the polynomial g. This bound in particular implies that such a function f is APN on at most a finite number of fields ${\mathcal{F}_{2^m}}$ . Furthermore we prove that when the degree of g is less than 7 such functions are APN only if m ?? 3 where these functions are equivalent to x ³.     

On the planar integrable differential systems

In this paper, we prove that the C ¹ planar differential systems that are integrable and non-Hamiltonian roughly speaking are C ¹ equivalent to the linear differential systems ${\dot u= u}$ , ${\dot v= v}$ . Additionally, we show that these systems have always a Lie symmetry. These results are improved for the class of polynomial differential systems defined in ${\mathbb{R}^2}$ or ${\mathbb{C}^2}$ .     

Algebraic classification of physical structures with zero. I

An algebraic version is considered of the axiomatization of physical structures. An arbitrary set R with a distinguished element O (zero) is taken as a set of measurements. Under an additional condition, understood to be an analog of the requirement that a physical structure is one-metric, the structure of a topological skew field with zero O is introduced on R; and on the object sets $\mathcal{M}$ and $\mathcal{N}$ , the structure of finite-dimensional vector spaces over the skew field is introduced. This leads to a complete classification of the corresponding physical structures. The classification theorem can be considered also as a variant of the axiomatics connected with a bilinear form on a pair of finite-dimensional vector spaces over a skew field; i.e., the variant which uses, as axioms, only the combinatorial properties of a bilinear form as a map $\mathcal{M} \times \mathcal{N} \to R$ (i.e., without the axioms of addition and multiplication).     

On the Stanley depth of weakly polymatroidal ideals

Let ${\mathbb{K}}$ be a field and ${S = \mathbb{K}[x_1,\dots,x_n]}$ be the polynomial ring in n variables over the field ${\mathbb{K}}$ . In this paper, it is shown that Stanley’s conjecture holds for I and S/I if I is a product of monomial prime ideals or I is a high enough power of a polymatroidal or a stable ideal generated in a single degree.     

Specializations of indecomposable polynomials

We address some questions concerning indecomposable polynomials and their behaviour under specialization. For instance we give a bound on a prime p for the reduction modulo p of an indecomposable polynomial ${P(x)\in {\mathbb{Z}}[x]}$ to remain indecomposable. We also obtain a Hilbert like result for indecomposability: if f(t ₁, . . . , t _r , x) is an indecomposable polynomial in several variables with coefficients in a field of characteristic p?=?0 or p?>?deg(f), then the one variable specialized polynomial ${f(t_1^\ast+\alpha_1^\ast x,\ldots,t_r^\ast+\alpha_r^\ast x,x)}$ is indecomposable for all ${(t_1^\ast, \ldots, t_r^\ast, \alpha_1^\ast, \ldots,\alpha_r^\ast)\in \overline k^{2r}}$ outside a proper Zariski closed subset.     

On the ∞-Norm of the Cubic form of Complete Hyperbolic Affine Hyperspheres

Let ${M_n \subset \mathbb R^{n+1}}$ be a complete hyperbolic affine hypersphere with mean curvature H, ${H < 0}$ , and let C be its cubic form. We derive a differential inequality and an upper bound on the scalar function ${||C||_{\infty}}$ defined by the fiber-wise maximum of the value of C on the unit sphere bundle of M. The bounds are attained for the affine hyperspheres which are asymptotic to a simplicial cone. The results have applications in conic optimization.     

The rank and generating set for inverse limits of wreath products of Abelian groups

We derive an exact formula for the topological rank d(W) of the inverse limit ${W = \ldots \wr A_2 \wr A_1}$ of iterated wreath products of arbitrary nontrivial finite Abelian groups. By using the language of automorphisms of a spherically homogeneous rooted tree, we construct and study a topological generating set for W with cardinality ${d(A_1) + \rho'}$ , where ${\rho'}$ is the topological rank of the profinite Abelian group ${A_2 \times A_3 \times \cdots}$ . In particular, if the group A ₁ is cyclic, this approach gives a minimal generating set for W.     

Improved Enumeration of Simple Topological Graphs

A simple topological graph $T=(V(T), E(T))$ T = ( V ( T ) , E ( T ) ) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $G$ G and $H$ H are isomorphic if $H$ H can be obtained from $G$ G by a homeomorphism of the sphere, and weakly isomorphic if $G$ G and $H$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $G$ G with $n$ n vertices, $m$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{O(n^2\log (m/n))}$ 2 O ( n 2 log ( m / n ) ) , and at most $2^{O(mn^{1/2}\log n)}$ 2 O ( m n 1 / 2 log n ) if $m\le n^{3/2}$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $2^{O(n^{3/2}\log n)}$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $n$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $n$ n vertices to $2^{n^2\cdot \alpha (n)^{O(1)}}$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{m^2+O(mn)}$ 2 m 2 + O ( m n ) and at least $2^{\Omega (m^2)}$ 2 Ω ( m 2 ) for graphs with $m>(6+\varepsilon )n$ m > ( 6 + ε ) n .     

On ideals with the Rees property

A homogeneous ideal I of a polynomial ring S is said to have the Rees property if, for any homogeneous ideal ${J \subset S}$ which contains I, the number of generators of J is smaller than or equal to that of I. A homogeneous ideal ${I \subset S}$ is said to be ${\mathfrak{m}}$ -full if ${\mathfrak{m}I:y=I}$ for some ${y \in \mathfrak{m}}$ , where ${\mathfrak{m}}$ is the graded maximal ideal of ${S}$ . It was proved by one of the authors that ${\mathfrak{m}}$ -full ideals have the Rees property and that the converse holds in a polynomial ring with two variables. In this note, we give examples of ideals which have the Rees property but are not ${\mathfrak{m}}$ -full in a polynomial ring with more than two variables. To prove this result, we also show that every Artinian monomial almost complete intersection in three variables has the Sperner property.     

Some Inverse Problems for d-Orthogonal Polynomials

This paper is devoted to the study of the generalized inverse problem of the left product of a d–dimensional vector form by a polynomial. The objective is to find the regularity conditions of the vector linear form ${\mathcal{V}}$ defined by ${\mathcal{U} = \mathcal{RV}}$ , where ${\mathcal{R}}$ is a d × d matrix polynomial. In such a case, the d–OPS {Q _n } _{n ≥ 0} corresponding to ${\mathcal{V}}$ is d–quasi– orthogonal of order l with respect to ${\mathcal{U}}$ . Secondly, we study the inverse problem: Given a d -OPS P _{n n ≥ 0} with respect to ${\mathcal{U}}$ , characterize the parameters ${\{a^{(i)}_{n}\}{^{dl}_{i=1}}}$ such that the sequence $${Q_{n+dl} = P_{n+dl} + \sum _{i=1}^{dl} a_{n+dl}^{(i)}P_{n+dl-i},\quad n\geq 0}$$ , is d–orthogonal with respect to some regular vector linear form ${\mathcal{V}}$ . As an immediate consequence, find the explicit relation between ${\mathcal{U}}$ and ${\mathcal{V}}$ .     

The Algebra of Polynomial Integro-Differential Operators is a Holonomic Bimodule over the Subalgebra of Polynomial Differential Operators

In contrast to its subalgebra $A_n:=K\langle x_1, \ldots , x_n, \frac{\partial}{\partial x_1}, \ldots ,\frac{\partial}{\partial x_n}\rangle $ of polynomial differential operators (i.e. the n’th Weyl algebra), the algebra ${\mathbb{I}}_n:=K\langle x_1, \ldots ,$ $ x_n, \frac{\partial}{\partial x_1}, \ldots ,\frac{\partial}{\partial x_n}, \int_1, \ldots , \int_n\rangle $ of polynomial integro-differential operators is neither left nor right Noetherian algebra; moreover it contains infinite direct sums of nonzero left and right ideals. It is proved that ${\mathbb{I}}_n$ is a left (right) coherent algebra iff n?=?1; the algebra ${\mathbb{I}}_n$ is a holonomic A _n -bimodule of length 3 ⁿ and has multiplicity 3 ⁿ with respect to the filtration of Bernstein, and all 3 ⁿ simple factors of ${\mathbb{I}}_n$ are pairwise non-isomorphic A _n -bimodules. The socle length of the A _n -bimodule ${\mathbb{I}}_n$ is n?+?1, the socle filtration is found, and the m’th term of the socle filtration has length ${n\choose m}2^{n-m}$ . This fact gives a new canonical form for each polynomial integro-differential operator. It is proved that the algebra ${\mathbb{I}}_n$ is the maximal left (resp. right) order in the largest left (resp. right) quotient ring of the algebra ${\mathbb{I}}_n$ .     

Convex underestimators of polynomials

Convex underestimators of a polynomial on a box. Given a non convex polynomial ${f\in \mathbb{R}[{\rm x}]}$ and a box ${{\rm B}\subset \mathbb{R}^n}$ , we construct a sequence of convex polynomials ${(f_{dk})\subset \mathbb{R}[{\rm x}]}$ , which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator ${f^{*}_{d}}$ of f. Indeed, ${f^{*}_{d}}$ minimizes the L ₁-norm ${\Vert f-g\Vert_1}$ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular α BB method and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k.     

Disjoint Edges in Complete Topological Graphs

It is shown that every complete $n$ -vertex simple topological graph has at $\varOmega (n^{1/3})$ pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Tóth, which appears as Problem 5 from Chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.     

On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small Degree

This paper studies the group theoretical protocol of Diffie?CHellman key exchange in the case of symmetrical group ${S_{p^n}}$ and more general Cremona group ${C(\mathbb K^n)}$ of polynomial automorphisms of free module ${\mathbb K^n}$ over arbitrary commutative ring ${\mathbb K}$ . This algorithm depends very much on the choice of the base ${g_n \in C( \mathbb K^n)}$ . It is important to work with the base ${g_n \in C( \mathbb K^n)}$ , which is a polynomial map of a small degree and a large order such that the degrees of all powers ${g_n^k}$ are also bounded by a small constant. We suggest fast algorithms for generation of a map ${g_n={f_n} \xi_nf_n^{-1}}$ , where ?? _n is an affine transformation (degree is 1) of a large order and f _n is a fixed nonlinear polynomial map in n variables such that ${f_n^{-1}}$ is also a polynomial map and both maps f _n and ${f_n^{-1}}$ are of small degrees. The method is based on properties of infinite families of graphs with a large cycle indicator and families of graphs of a large girth in particular. It guaranties that the order of g _n is tending to infinity as the dimension n tends to infinity. We propose methods of fast generation of special families of cubical maps f _n such that ${f_n^{-1}}$ is also of degree 3 based on properties of families of graphs of a large girth and graphs with a large cycle indicator. At the end we discuss cryptographical applications of maps of the kind ?? f _n ??^?1 and some graph theoretical problems motivated by such applications.     

Representation of Polynomials by Linear Combinations of Radial Basis Functions

Let ${\mathcal {P}_{n}^{d}}$ denote the space of polynomials on ? ^d of total degree n. In this work, we introduce the space of polynomials ${\mathcal {Q}_{2 n}^{d}}$ such that ${\mathcal {P}_{n}^{d}}\subset {\mathcal {Q}_{2 n}^{d}}\subset\mathcal{P}_{2n}^{d}$ and which satisfy the following statement: Let h be any fixed univariate even polynomial of degree n and $\mathcal{A}$ be a finite set in ? ^d . Then every polynomial P from the space  ${\mathcal {Q}_{2 n}^{d}}$ may be represented by a linear combination of radial basis functions of the form h(∥x+a∥), $a\in \mathcal{A}$ , if and only if the set $\mathcal{A}$ is a uniqueness set for the space  ${\mathcal {Q}_{2 n}^{d}}$ .     

Value-sets of polynomials at p-adic integers

In this paper we are concerned with the classification of the subsets A of ${\mathbb{Z}_p}$ which occur as images ${f(\mathbb{Z}_p^r)}$ of polynomial functions ${f:\mathbb{Z}_p^r\to \mathbb{Z}_p}$ , limiting ourselves to compact-open subsets (i.e. finite unions of open balls). We shall prove three main results: (i) Every compact-open ${A\subset \mathbb{Z}_p}$ is of the shape ${A=f(\mathbb{Z}_p^r)}$ for suitable r and ${f\in\mathbb{Z}_p[X_1,\ldots ,X_r]}$ . (ii) For each r ₀ there is a compact-open A such that in (i) we cannot take r < r ₀. (iii) For any compact-open set ${A\subset \mathbb{Z}_p}$ there exists a polynomial ${f\in\mathbb{Q}_p[X]}$ such that ${f(\mathbb{Z}_p)=A}$ . We shall also discuss in more detail which sets A can be represented as ${f(\mathbb{Z}_p)}$ for a polynomial ${f\in\mathbb{Z}_p[X]}$ in a single variable.