BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Per Alexandersson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Some classical graph problems such as finding minimal spanning tree, shortest path or maximal flow can be done efficiently. We describe slight variations of such problems which are shown to be NP-complete. Our proofs use straightforward reduction from $3$-SAT.
We show that the classical game LaserTank is $\mathrm{NP}$-complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mirrors and solid blocks. We show this by reducing $3$-SAT instances to LaserTank puzzles.
We conjecture an explicit positive combinatorial formula for the expansion of unicellular LLT polynomials in the elementary symmetric basis. This is an analogue of the Shareshian-Wachs conjecture and previously studied by Panova and the author in 2018. We show that the conjecture for unicellular LLT polynomials implies a similar formula for vertical-strip LLT polynomials. We prove positivity in the elementary basis in for the class of graphs called `melting lollipops' previously considered by Huh, Nam and Yoo. This is done by proving a curious relationship between a generalization of charge and orientations of unit-interval graphs. We also provide short bijective proofs of Lee's three-term recurrences for unicellular LLT polynomials and we show that these recurrences are enough to generate all unicellular LLT polynomials associated with abelian area sequences.
We give a $q$-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this $q$-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Möbius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving. Finally, we also introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.
We extend the family non-symmetric Macdonald polynomials and define general-basement Macdonald polynomials. We show that these also satisfy a triangularity property with respect to the monomials bases and behave well under the Demazure-Lusztig operators. The symmetric Macdonald polynomials $J_λ$ are expressed as a sum of general-basement Macdonald polynomials via an explicit formula. By letting $q=0$, we obtain $t$-deformations of key polynomials and Demazure atoms and we show that the Hall--Littlewood polynomials expand positively into these. This generalizes a result by Haglund, Luoto, Mason and van Willigenburg. As a corollary, we prove that Schur polynomials decompose with non-negative coefficients into $t$-deformations of general Demazure atoms and thus generalizing the $t=0$ case which was previously known. This gives a unified formula for the classical expansion of Schur polynomials in Hall-Littlewood polynomials and the expansion of Schur polynomials into Demazure atoms.
Given an arbitrary complex-valued infinite matrix A and a positive integer n we introduce a naturally associated polynomial basis B_A of C[x0...xn]. We discuss some properties of the locus of common zeros of all polynomials in B_A having a given degree m; the latter locus can be interpreted as the spectrum of the m*(m+n)-submatrix of A formed by its m first rows and m+n first columns. We initiate the study of the asymptotics of these spectra when m goes to infinity in the case when A is a banded Toeplitz matrix. In particular, we present and partially prove a conjectural multivariate analog of the well-known Schmidt-Spitzer theorem which describes the spectral asymptotics for the sequence of principal minors of an arbitrary banded Toeplitz matrix. Finally, we discuss relations between polynomial bases B_A and multivariate orthogonal polynomials.
Here we present certificates for 5 classes of 6-edged multigraphs whose symmetrized graph monomials may be represented as sum of squares, but not as linear combinations of partition square graphs. This is a complement to the results presented in Discriminants, symmetrized graph monomials, and sums of squares.
We prove that for arbitrary partitions $\mathbfλ \subseteq \mathbfκ,$ and integers $0\leq c<r\leq n,$ the sequence of Schur polynomials $S_{(\mathbfκ + k\cdot \mathbf{1}^c)/(\mathbfλ + k\cdot \mathbf{1}^r)}(x_1,...,x_n)$ for $k$ sufficiently large, satisfy a linear recurrence. The roots of the characteristic equation are given explicitly. These recurrences are also valid for certain sequences of minors of banded Toeplitz matrices. In addition, we show that Widom's determinant formula from 1958 is a special case of a well-known identity for Schur polynomials.
We show that sequences of skew Schur polynomials obtained from stretched semi-standard Young tableaux satisfy a linear recurrence, which we give explicitly. Using this, we apply this to finding certain asymptotic behavior of these Schur polynomials and present conjectures on minimal recurrences for stretched Schur polynomials.
Motivated by the necessities of the invariant theory of binary forms J. J. Sylvester constructed in 1878 for each graph with possible multiple edges but without loops its symmetrized graph monomial which is a polynomial in the vertex labels of the original graph. In the 20-th century this construction was studied by several authors. We pose the question for which graphs this polynomial is a non-negative resp. a sum of squares. This problem is motivated by a recent conjecture of F. Sottile and E. Mukhin on discriminant of the derivative of a univariate polynomial, and an interesting example of P. and A. Lax of a graph with 4 edges whose symmetrized graph monomial is non-negative but not a sum of squares. We present detailed information about symmetrized graph monomials for graphs with four and six edges, obtained by computer calculations.
In this paper, we generalize several results of the article "Analytic continuation of eigenvalues of a quartic oscillator" of A. Eremenko and A. Gabrielov. We consider a family of eigenvalue problems for a Schrödinger equation with even polynomial potentials of arbitrary degree d with complex coefficients, and k<(d+2)/2 boundary conditions. We show that the spectral determinant in this case consists of two components, containing even and odd eigenvalues respectively. In the case with k=(d+2)/2 boundary conditions, we show that the corresponding parameter space consists of infinitely many connected components.
In this paper, we generalize a recent result of A. Eremenko and A. Gabrielov on irreducibility of the spectral discriminant for the Schrödinger equation with quartic potentials. We consider the eigenvalue problem with a complex-valued polynomial potential of arbitrary degree d and show that the spectral determinant of this problem is connected and irreducible. In other words, every eigenvalue can be reached from any other by analytic continuation. We also prove connectedness of the parameter spaces of the potentials that admit eigenfunctions satisfying k>2 boundary conditions, except for the case d is even and k=d/2. In the latter case, connected components of the parameter space are distinguished by the number of zeros of the eigenfunctions.