More Like this

1. A Bijection Between Evil-Avoiding and Rectangular Permutations

   https://doi.org/10.37236/11841  

   Tung, Katherine (October 2023, The Electronic Journal of Combinatorics)

   Evil-avoiding permutations, introduced by Kim and Williams in 2022, arise in the study of the inhomogeneous totally asymmetric simple exclusion process. Rectangular permutations, introduced by Chirivì, Fang, and Fourier in 2021, arise in the study of Schubert varieties and Demazure modules. Taking a suggestion of Kim and Williams, we supply an explicit bijection between evil-avoiding and rectangular permutations in $$S_n$$ that preserves the number of recoils. We encode these classes of permutations as regular languages and construct a length-preserving bijection between words in these regular languages. We extend the bijection to another Wilf-equivalent class of permutations, namely the $$1$$-almost-increasing permutations, and exhibit a bijection between rectangular permutations and walks of length $2n-2$ in a path of seven vertices starting and ending at the middle vertex. 

   more » « less
2. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification

   https://doi.org/10.4230/LIPIcs.ICALP.2024.137  

   Gajarský, Jakub; McCarty, Rose (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generalization of graph classes of bounded degree and bounded treedepth, and they are a special case of graph classes of bounded expansion. We introduce a notion of decomposition for these classes and show that these decompositions can be efficiently computed. Also, a natural extension of our decomposition leads to a new characterization and decomposition for graph classes of bounded expansion (and an efficient algorithm computing this decomposition). We then focus on interpretations of graph classes of bounded tree rank. We give a characterization of graph classes interpretable in graph classes of tree rank 2. Importantly, our characterization leads to an efficient sparsification procedure: For any graph class 𝒞 interpretable in a graph class of tree rank at most 2, there is a polynomial time algorithm that to any G ∈ 𝒞 computes a (sparse) graph H from a fixed graph class of tree rank at most 2 such that G = I(H) for a fixed interpretation I. To the best of our knowledge, this is the first efficient "interpretation reversal" result that generalizes the result of Gajarský et al. [LICS 2016], who showed an analogous result for graph classes interpretable in classes of graphs of bounded degree. 

   more » « less
3. Hook formulae from Segre–MacPherson classes

   https://doi.org/10.5802/alco.428  

   Mihalcea, Leonardo C; Naruse, Hiroshi; Su, Changjian (January 2025, Algebraic Combinatorics)

   Nakada’s colored hook formula is a vast generalization of many important formulae in combinatorics, such as the classical hook length formula and the Peterson’s formula for the number of reduced expressions of minuscule Weyl group elements. In this paper, we use cohomological properties of Segre–MacPherson classes of Schubert cells and varieties to prove a generalization of a cohomological version of Nakada’s formula, in terms of smoothness properties of Schubert varieties. A key ingredient in the proof is the study of a decorated version of the Bruhat graph. Weights of the paths in this graph give the terms in the generalized Nakada’s formula, and the summation over all paths is equal to the equivariant multiplicity of the Chern–Schwartz–MacPherson class of a Richardson variety. Among the applications we mention an algorithm to calculate structure constants of multiplications of Segre–MacPherson classes of Schubert cells, and a skew version of Nakada–Peterson’s formula. 

   more » « less
4. Oracle Inequalities for Model Selection in Offline Reinforcement Learning

   Lee, J.; Tucker, G.; Nachum, O.; Dai, B.; Brunskill, E. (January 2022, Advances in neural information processing systems)

   In offline reinforcement learning (RL), a learner leverages prior logged data to learn a good policy without interacting with the environment. A major challenge in applying such methods in practice is the lack of both theoretically principled and practical tools for model selection and evaluation. To address this, we study the problem of model selection in offline RL with value function approximation. The learner is given a nested sequence of model classes to minimize squared Bellman error and must select among these to achieve a balance between approximation and estimation error of the classes. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal oracle inequalities up to logarithmic factors. The algorithm, MODBE, takes as input a collection of candidate model classes and a generic base offline RL algorithm. By successively eliminating model classes using a novel one-sided generalization test, MODBE returns a policy with regret scaling with the complexity of the minimally complete model class. In addition to its theoretical guarantees, it is conceptually simple and computationally efficient, amounting to solving a series of square loss regression problems and then comparing relative square loss between classes. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class. 

   more » « less
5. Task-Adaptive Few-shot Node Classification

   https://doi.org/10.1145/3534678.3539265  

   Wang, Song; Ding, Kaize; Zhang, Chuxu; Chen, Chen; Li, Jundong (August 2022, Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining)

   Node classification is of great importance among various graph mining tasks. In practice, real-world graphs generally follow the long-tail distribution, where a large number of classes only consist of limited labeled nodes. Although Graph Neural Networks (GNNs) have achieved significant improvements in node classification, their performance decreases substantially in such a few-shot scenario. The main reason can be attributed to the vast generalization gap between meta-training and meta-test due to the task variance caused by different node/class distributions in meta-tasks (i.e., node-level and class-level variance). Therefore, to effectively alleviate the impact of task variance, we propose a task-adaptive node classification framework under the few-shot learning setting. Specifically, we first accumulate meta-knowledge across classes with abundant labeled nodes. Then we transfer such knowledge to the classes with limited labeled nodes via our proposed task-adaptive modules. In particular, to accommodate the different node/class distributions among meta-tasks, we propose three essential modules to perform node-level, class-level, and task-level adaptations in each meta-task, respectively. In this way, our framework can conduct adaptations to different meta-tasks and thus advance the model generalization performance on meta-test tasks. Extensive experiments on four prevalent node classification datasets demonstrate the superiority of our framework over the state-of-the-art baselines. Our code is provided at https://github.com/SongW-SW/TENT https://github.com/SongW-SW/TENT. 

   more » « less