Moment subset sums over finite fields

The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case $m=1$, this recovers previous results of Nguyen-Wang (the case $m=1,p>2$) [22] and the results of Choe-Choe (the case $m=1,p=2$) [3].     

Tensor products of n-complete algebras

If A and B are n- and m-representation finite k-algebras, then their tensor product $\mathrm{\Lambda }=A{?}_{k}B$ is not in general $(n+m)$-representation finite. However, we prove that if A and B are acyclic and satisfy the weaker assumption of n- and m-completeness, then Λ is $(n+m)$-complete. This mirrors the fact that taking higher Auslander algebra does not preserve d-representation finiteness in general, but it does preserve d-completeness. As a corollary, we get the necessary condition for Λ to be $(n+m)$-representation finite which was found by Herschend and Iyama by using a certain twisted fractionally Calabi–Yau property.     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

Constructions of optimal orthogonal arrays with repeated rows

We construct orthogonal arrays ${\mathsf{OA}}_{\lambda }(k,n)$ (of strength two) having a row that is repeated $m$ times, where $m$ is as large as possible. In particular, we consider OAs where the ratio $m∕\lambda$ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any $k\ge n+1$, albeit with large $\lambda$. We also study basic OAs; these are optimal OAs in which $gcd(m,\lambda )=1$. We construct a basic OA with $n=2$ and $k=4t+1$, provided that a Hadamard matrix of order $8t+4$ exists. This completely solves the problem of constructing basic OAs with $n=2$, modulo the Hadamard matrix conjecture.     

On the bijective colouring of Cantor trees based on transducers

Given a vertex colouring of the infinite n-ary Cantor tree with m colours ($n,m\ge 2$), the natural problem arises: may this colouring induce a bijective colouring of the infinite paths starting at the root, i.e., that every infinite m-coloured string is used for some of these paths but different paths are not coloured identically? In other words, we ask if the above vertex colouring may define a bijective short map between the corresponding Cantor spaces. We show that the answer is positive if and only if $n\ge m$, and provide an effective construction of the bijective colouring in terms of Mealy automata and functions defined by such automata. We also show that a finite Mealy automaton may define such a bijective colouring only in the trivial case, i.e. $m=n$.     

Embeddings of canonical modules and resolutions of connected sums

For an ideal $I_{m,n}$ generated by all square-free monomials of degree m in a polynomial ring R with n variables, we obtain a specific embedding of a canonical module of $R/I_{m,n}$ to $R/I_{m,n}$ itself. The construction of this explicit embedding depends on a minimal free R-resolution of an ideal generated by $I_{m,n}$. Using this embedding, we give a resolution of connected sums of several copies of certain Artin $\mathsf{k}$-algebras where $\mathsf{k}$ is a field.     

Enumerations of universal cycles for k-permutations

Universal cycle for k-permutations is a cyclic arrangement in which each k-permutation appears exactly once as k consecutive elements. Enumeration problem of universal cycles for k-permutations is discussed and one new enumerating method is proposed in this paper. Accurate enumerating formulae are provided when $k=2,3$.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

γ-variable first-order logic of uniform attachment random graphs

We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with m edges joining the new vertex with m different vertices chosen uniformly at random from $1,\dots ,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m?2$ variables.     

Improvements on Hippchen's conjecture

Let G be a k-connected graph on n vertices. Hippchen's Conjecture (2008) states that two longest paths in G share at least k vertices. Gutiérrez (2020) recently proved the conjecture when $k\le 4$ or $k\ge \frac{n?2}{3}$. We improve upon both results; namely, we show that two longest paths in G share at least k vertices when $k=5$ or $k\ge \frac{n+2}{5}$. This completely resolves two conjectures by Gutiérrez in the affirmative.     

The Helmholtz equation in heterogeneous media: A priori bounds,well-posedness,and resonances

We consider the exterior Dirichlet problem for the heterogeneous Helmholtz equation, i.e. the equation $\mathrm{?}?(A\mathrm{?}u)+k^{2}nu=?f$ where both A and n are functions of position. We prove new a priori bounds on the solution under conditions on A, n, and the domain that ensure nontrapping of rays; the novelty is that these bounds are explicit in k, A, n, and geometric parameters of the domain. We then show that these a priori bounds hold when A and n are $L^{\infty }$ and satisfy certain monotonicity conditions, and thereby obtain new results both about the well-posedness of such problems and about the resonances of acoustic transmission problems (i.e. A and n discontinuous) where the transmission interfaces are only assumed to be $C^0$ and star-shaped; the novelty of this latter result is that until recently the only known results about resonances of acoustic transmission problems were for $C^{\infty }$ convex interfaces with strictly positive curvature.     

A faster algorithm for the continuous bilevel knapsack problem

We construct a fast algorithm with time complexity $O(nlogn)$ for a continuous bilevel knapsack problem with interdiction constraints for $n$ items. This improves on a recent algorithm from the literature with quadratic time complexity $O\left(n^2\right)$.