Search

In the last decade, algorithmic frameworks based on a structural graph parameter called mim-width have been developed to solve generally NP-hard problems. However, it is known that the frameworks cannot be applied to the Clique problem, and the complexity status of many problems of finding dense induced subgraphs remains open when parameterized by mim-width. In this paper, we investigate the complexity of the problem of finding a maximum induced subgraph that satisfies prescribed properties from a given graph with small mim-width. We first give a meta-theorem implying that various induced subgraph problems are NP-hard for bounded mim-width graphs. Moreover, we show that some problems, including Clique and Induced Cluster Subgraph, remain NP-hard even for graphs with (linear) mim-width at most 2. In contrast to the intractability, we provide an algorithm that, given a graph and its branch decomposition with mim-width at most 1, solves Induced Cluster Subgraph in polynomial time. We emphasize that our algorithmic technique is applicable to other problems such as Induced Polar Subgraph and Induced Split Subgraph. Since a branch decomposition with mim-width at most 1 can be constructed in polynomial time for block graphs, interval graphs, permutation graphs, cographs, distance-hereditary graphs, convex graphs, and their complement graphs, our positive results reveal the polynomial-time solvability of various problems for these graph classes., Comment: To appear in the proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT 2024)

The problem of packing as many subgraphs isomorphic to $H \in \mathcal H$ as possible in a graph for a class $\mathcal H$ of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for $H$ that contains at least three vertices and at least three edges, respectively. In this paper, we consider ``list variants'' of these problems: Given a graph $G$, an integer $k$, and a collection $\mathcal L_{\mathcal H}$ of subgraphs of $G$ isomorphic to some $H \in \mathcal H$, the goal is to compute $k$ subgraphs in $\mathcal L_{\mathcal H}$ that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study arborescences in digraphs from the viewpoint of combinatorial reconfiguration, which is the field where we study reachability between two configurations of some combinatorial objects via some specified operations. Especially, we consider reconfiguration problems for time-respecting arborescences, which were introduced by Kempe, Kleinberg, and Kumar. We first prove that if the roots of the initial and target time-respecting arborescences are the same, then the target arborescence is always reachable from the initial one and we can find a shortest reconfiguration sequence in polynomial time. Furthermore, we show if the roots are not the same, then the target arborescence may not be reachable from the initial one. On the other hand, we show that we can determine whether the target arborescence is reachable form the initial one in polynomial time. Finally, we prove that it is NP-hard to find a shortest reconfiguration sequence in the case where the roots are not the same. Our results show an interesting contrast to the previous results for (ordinary) arborescences reconfiguration problems., Comment: 13 pages, 3 figures, WADS 2023

This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts the breadth-first search by compressing the solution space using ZDDs, and finds a shortest transformation between two given feasible solutions if exists. Moreover, the proposed framework provides rich information on the solution space, such as the connectivity of the solution space and all feasible solutions reachable from a specified one. We demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate their performances.

We propose a large-scale dataset of real-world rainy and clean image pairs and a method to remove degradations, induced by rain streaks and rain accumulation, from the image. As there exists no real-world dataset for deraining, current state-of-the-art methods rely on synthetic data and thus are limited by the sim2real domain gap; moreover, rigorous evaluation remains a challenge due to the absence of a real paired dataset. We fill this gap by collecting a real paired deraining dataset through meticulous control of non-rain variations. Our dataset enables paired training and quantitative evaluation for diverse real-world rain phenomena (e.g. rain streaks and rain accumulation). To learn a representation robust to rain phenomena, we propose a deep neural network that reconstructs the underlying scene by minimizing a rain-robust loss between rainy and clean images. Extensive experiments demonstrate that our model outperforms the state-of-the-art deraining methods on real rainy images under various conditions. Project website: https://visual.ee.ucla.edu/gt_rain.htm/.

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to in NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins., Comment: 17 pages, 10 figures

We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.

A growing number of papers are published in the area of superconducting materials science. However, novel text and data mining (TDM) processes are still needed to efficiently access and exploit this accumulated knowledge, paving the way towards data-driven materials design. Herein, we present SuperMat (Superconductor Materials), an annotated corpus of linked data derived from scientific publications on superconductors, which comprises 142 articles, 16052 entities, and 1398 links that are characterised into six categories: the names, classes, and properties of materials; links to their respective superconducting critical temperature (Tc); and parametric conditions such as applied pressure or measurement methods. The construction of SuperMat resulted from a fruitful collaboration between computer scientists and material scientists, and its high quality is ensured through validation by domain experts. The quality of the annotation guidelines was ensured by satisfactory Inter Annotator Agreement (IAA) between the annotators and the domain experts. SuperMat includes the dataset, annotation guidelines, and annotation support tools that use automatic suggestions to help minimise human errors.

Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xspace and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains \PSPACE-complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar \textsc{and/or}\xspace graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL, the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of \textsc{and}\xspace or \textsc{or}\xspace vertices of an \textsc{and/or}\xspace constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of \textsc{and}\xspace vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing \PSPACE.

Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup f$. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed by Ito et al. We investigate the problem of determining, given two spanning trees $T_1,T_2$ with an additional property $\Pi$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $\Pi$ all along. First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at least $k$ leaves (where $k$ is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when $k=n-2$., Comment: 32 pages, 8 figures

A vertex subset $I$ of a graph $G$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $I$. The \textsc{$k$-Path Vertex Cover Reconfiguration ($k$-PVCR)} problem asks if one can transform one $k$-path vertex cover into another via a sequence of $k$-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of \textsc{$k$-PVCR} from the viewpoint of graph classes under the well-known reconfiguration rules: $\mathsf{TS}$, $\mathsf{TJ}$, and $\mathsf{TAR}$. The problem for $k=2$, known as the \textsc{Vertex Cover Reconfiguration (VCR)} problem, has been well-studied in the literature. We show that certain known hardness results for \textsc{VCR} on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for \textsc{$k$-PVCR}. In particular, we prove a complexity dichotomy for \textsc{$k$-PVCR} on general graphs: on those whose maximum degree is $3$ (and even planar), the problem is $\mathtt{PSPACE}$-complete, while on those whose maximum degree is $2$ (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for \textsc{$k$-PVCR} on trees under each of $\mathsf{TJ}$ and $\mathsf{TAR}$. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given $k$-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest., Comment: 29 pages, 6 figures, to be published in IEICE Trans. Information and Systems

In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system $I$ and two feasible solutions $\boldsymbol{s}$ and $\boldsymbol{t}$ of $I$, and then asked to transform $\boldsymbol{s}$ to $\boldsymbol{t}$ by changing a value of only one variable at a time, while maintaining a feasible solution of $I$ throughout. $Z(I)$ for $I$ is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index $Z(I)$ of given $I$. We then show that the problem is (i) solvable in constant time if $Z(I)$ is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if $Z(I)$ is exactly one, and (iii) PSPACE-complete if $Z(I)$ is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge., Comment: Accepted by WALCOM2020

Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the dominating set reconfiguration problem, where two dominating sets are given and the question is merely whether they can be reached one from another through elementary operations. We show that this problem is PSPACE-complete, even if the input graph is a bipartite graph, a split graph, or has bounded pathwidth. On the positive side, we give linear-time algorithms for cographs, trees and interval graphs. We also study the parameterized complexity of this problem. More precisely, we show that the problem is W[2]-hard when parameterized by the upper bound on the size of an intermediary dominating set. On the other hand, we give fixed-parameter algorithms with respect to the minimum size of a vertex cover, or $d+s$ where $d$ is the degeneracy and $s$ is the upper bound of output solution., Comment: 15 pages, 8 figures

We introduce a new framework for reconfiguration problems, and apply it to independent sets as the first example. Suppose that we are given an independent set $I_0$ of a graph $G$, and an integer $l \ge 0$ which represents a lower bound on the size of any independent set of $G$. Then, we are asked to find an independent set of $G$ having the maximum size among independent sets that are reachable from $I_0$ by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least $l$. We show that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the fixed-parameter (in)tractability of the problem with respect to the following three parameters: the degeneracy $d$ of an input graph, a lower bound $l$ on the size of the independent sets, and a lower bound $s$ on the solution size. We show that the problem is fixed-parameter intractable when only one of $d$, $l$, and $s$ is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by $s+d$; this result implies that the problem parameterized only by $s$ is fixed-parameter tractable for planar graphs, and for bounded treewidth graphs.

Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.

Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether there exists a sequence of list edge-colorings of $G$ between $f_0$ and $f_r$ such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer $k \ge 6$ and planar graphs of maximum degree three, but any complexity hardness was unknown for the non-list variant. In this paper, we first improve the known result by proving that, for every integer $k \ge 4$, the problem remains PSPACE-complete even if an input graph is planar, bounded bandwidth, and of maximum degree three. We then give the first complexity hardness result for the non-list variant: for every integer $k \ge 5$, we prove that the non-list variant is PSPACE-complete even if an input graph is planar, of bandwidth linear in $k$, and of maximum degree $k$.

A general relation between entropy and an evolutionary superoperator is derived based on the theory of the real-time formulation. The formulation establishing the relation relies only on the framework of quantum statistical mechanics and the standard definition of the von Neumann entropy. Applying the theory of the imaginary-time formulation, a similar relation is obtained for the entropy change due to the change in reservoir temperatures. To show the usefulness of these formulas, we derived the expression for the entropy production induced by some dissipation in an open quantum system as the exemplary model system., Comment: 5 pages. Accepted in Foundations of Physics (close to accepted version). arXiv admin note: text overlap with arXiv:1103.4775, arXiv:1203.0485 by other authors

Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$. Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex. This problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, trees, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence such that the number of additions and deletions is bounded by $O(n)$, where $n$ is the number of vertices in the input graph.

Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time., Comment: 34 pages, 5 figures

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph $G$ is a set $S$ of vertices such that each vertex is either in $S$ or has a neighbour in $S$. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions $s$ and $t$ such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of $k$, we consider properties of $D_k(G)$, the graph consisting of a vertex for each dominating set of size at most $k$ and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that $D_{\Gamma(G)+1}(G)$ is not necessarily connected, for $\Gamma(G)$ the maximum cardinality of a minimal dominating set in $G$. The result holds even when graphs are constrained to be planar, of bounded tree-width, or $b$-partite for $b \ge 3$. Moreover, we construct an infinite family of graphs such that $D_{\gamma(G)+1}(G)$ has exponential diameter, for $\gamma(G)$ the minimum size of a dominating set. On the positive side, we show that $D_{n-m}(G)$ is connected and of linear diameter for any graph $G$ on $n$ vertices having at least $m+1$ independent edges., Comment: 12 pages, 4 figures

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if there is a sequence of {\em reconfiguration steps} that can be applied to transform $S$ into $T$ such that each step results in a feasible solution to $Q$. For most of the results in this paper, $S$ and $T$ are subsets of vertices of a given graph and a reconfiguration step adds or deletes a vertex. Our study is motivated by recent results establishing that for most NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: $k$, the size of the solutions, and $\ell$, the length of the sequence of steps. Our first general result is an algorithmic paradigm, the {\em reconfiguration kernel}, used to obtain fixed-parameter algorithms for the reconfiguration versions of {\sc Vertex Cover} and, more generally, {\sc Bounded Hitting Set} and {\sc Feedback Vertex Set}, all parameterized by $k$. In contrast, we show that reconfiguring {\sc Unbounded Hitting Set} is $W[2]$-hard when parameterized by $k+\ell$. We also demonstrate the $W[1]$-hardness of the reconfiguration versions of a large class of maximization problems parameterized by $k+\ell$, and of their corresponding deletion problems parameterized by $\ell$; in doing so, we show that there exist problems in FPT when parameterized by $k$, but whose reconfiguration versions are $W[1]$-hard when parameterized by $k+\ell$., Comment: IPEC 2013

A quantum statistical expression for the entropy of a nonequilibrium system is defined so as to be consistent with Gibbs' relation, and is shown to corresponds to dynamical variable by introducing analogous to the Heisenberg picture in quantum mechanics. The general relation between system-reservoir interactions and an entropy change operator in an open quantum system, relying just on the framework of statistical mechanics and the definition of von Neumann entropy. By using this formula, we can obtain the correct entropy production in the linear response framework. The present derivation of entropy production is directly based on the first principle of microscopic time-evolution, while the previous standard argument is due to the thermodynamic energy balance., Comment: 4 pages, no figure. Published in AIP Conf. Proc

The unusual quantum Hall effect (QHE) in graphene is often discussed in terms of Dirac fermions moving with a linear dispersion relation. The same phenomenon will be explained in terms of the more traditional composite bosons, which move with a linear dispersion relation. The "electron" (wave packet) moves easier in the direction [1,1,0,c-axis] = [1,1,0] of the honeycomb lattice than perpendicular to it, while the "hole" moves easier in [0,0,1]. Since "electrons" and "holes" move in different channels, the number densities can be high especially when the Fermi surface has "necks". The strong QHE arises from the phonon exchange attraction in the neighborhood of the "neck" Fermi surfaces. The plateau observed for the Hall conductivity and the accompanied resistivity drop is due to the Bose-Einstein condensation of the c-bosons, each forming from a pair of one-electron--two-fluxons c-fermions by phonon-exchange attraction., Comment: 12 pages, 3 figures. arXiv admin note: substantial text overlap with arXiv:1304.7631

A quantum statistical theory is developed for a fractional quantum Hall effects in terms of composite bosons (fermions) each of which contains a conduction electron and an odd (even) number of fluxons. The cause of the QHE is by assumption the phonon exchange attraction between the conduction electron ("electron", "hole") and fluxons (quanta of magnetic fluxes). We postulate that c-fermions with \emph{any} even number of fluxons have an effective charge (magnitude) equal to the electron charge $e$. The density of c-fermions with $m$ fluxons, $n_\phi^{(m)}$, is connected with the electron density $n_{\mathrm e}$ by $n_\phi^{(m)}=n_{\mathrm e}/m$, which implies a more difficult formation for higher $m$, generating correct values $me^2/h$ for the Hall conductivity $\sigma_{\mathrm H}\equiv j/E_{\mathrm H}$. For condensed c-bosons the density of c-bosons-with-$m$ fluxons, $n_\phi^{(m)}$, is connected with the boson density $n_0$ by $n_\phi^{(m)}=n_0/m$. This yields $\sigma_{\mathrm H}=m\,e^2/h$ for the magnetoconductivity, the value observed of the QHE at filling factor $\nu=1/m$ ($m=$odd numbers). Laughlin's theory and results about the fractional charge are not borrowed in the present work., Comment: 11 pages, 1 figure

Vanadium dioxide (VO$_2$) undergoes a metal-insulator transition (MIT) at 340 K with the structural change between tetragonal and monoclinic crystals as the temperature is lowered. The conductivity $\sigma$ drops at MIT by four orders of magnitude. The low-temperature monoclinic phase is known to have a lower ground-state energy. The existence of a $k$-vector ${\boldsymbol k}$ is prerequisite for the conduction since the ${\boldsymbol k}$ appears in the semiclassical equation of motion for the conduction electron (wave packet). Each wave packet is, by assumption, composed of the plane waves proceeding in the ${\boldsymbol k}$ direction perpendicular to the plane. The tetragonal (VO$_2$)$_3$ unit cells are periodic along the crystal's $x$-, $y$-, and z-axes, and hence there are three-dimensional $k$-vectors. The periodicity using the non-orthogonal bases does not legitimize the electron dynamics in solids. There are one-dimensional ${\boldsymbol k}$ along the c-axis for a monoclinic crystal. We believe this decrease in the dimensionality of the $k$-vectors is the cause of the conductivity drop. Triclinic and trigonal (rhombohedral) crystals have no $k$-vectors, and hence they must be insulators. The majority carriers in graphite are "electrons", which is shown by using an orthogonal unit cell for the hexagonal lattice., Comment: 8 pages, 1 figure

Two atoms in an optical lattice may be made to interact strongly at higher partial waves near a Feshbach resonance. These atoms, under appropriate constraints, could be bosonic or fermionic. The universal $l=2$ energy spectrum for such a system, with a caveat, is presented in this paper, and checked with the spectrum obtained by direct numerical integration of the Schr\"odinger equation. The results reported here extend those of Yip for p-wave resonance (Phys. Rev. A {\bf 78}, 013612 (2008)), while exploring the limitations of a universal expression for the spectrum for the higher partial waves., Comment: To be published in Physical Review A

We examine charmed-strange mesons within the framework of the constituent quark model, focusing on the states with L=1. We are particularly interested in the mixing of two spin-states that are involved in $D_{s1}(2536)$ and the recently discovered $D_{sJ}(2460)$. We assume that these two mesons form a pair of states with J=1. These spin-states are mixed by a type of the spin-orbit interaction that violates the total-spin conservation. Without assuming explicit forms for the interactions as functions of the interquark distance, we relate the matrix elements of all relevant spin-dependent interactions to the mixing angle and the observed masses of the L=1 quartet. We find that the spin-spin interaction, among various types of the spin-dependent interactions, plays a particularly interesting role in determining the spin structure of $D_{s1}(2536)$ and $D_{sJ}(2460)$.

We examine shape invariant potentials (excluding those that are obtained by scaling) in supersymmetric quantum mechanics from the stand-point of periodic orbit theory. An exact trace formula for the quantum spectra of such potentials is derived. Based on this result, and Barclay's functional relationship for such potentials, we present a new derivation of the result that the lowest order SWKB quantisation rule is exact., Comment: 4 pages, 1 figure, corrected typos, minor revisions, added references

We present closed analytical expressions for the particle and kinetic energy spatial densities at finite temperatures for a system of noninteracting fermions (bosons) trapped in a d-dimensional harmonic oscillator potential. For d=2 and 3, exact expressions for the N-particle densities are used to calculate perturbatively the temperature dependence of the splittings of the energy levels in a given shell due to a very weak interparticle interaction in a dilute Fermi gas. In two dimensions, we obtain analytically the surprising result that the |l|-degeneracy in a harmonic oscillator shell is not lifted in the lowest order even when the exact, rather than the Thomas-Fermi expression for the particle density is used. We also demonstrate rigorously (in two dimensions) the reduction of the exact zero-temperature fermionic expressions to the Thomas-Fermi form in the large-N limit., Comment: 14 pages, 4 figures included