Toll convexity

A walk $W$ between two non-adjacent vertices in a graph $G$ is called tolled if the first vertex of $W$ is among vertices from $W$ adjacent only to the second vertex of $W$, and the last vertex of $W$ is among vertices from $W$ adjacent only to the second-last vertex of $W$. In the resulting interval convexity, a set $S\subset V\left(G\right)$ is toll convex if for any two non-adjacent vertices $x,y\in S$ any vertex in a tolled walk between $x$ and $y$ is also in $S$. The main result of the paper is that a graph is a convex geometry (i.e. satisfies the Minkowski–Krein–Milman property stating that any convex subset is the convex hull of its extreme vertices) with respect to toll convexity if and only if it is an interval graph. Furthermore, some well-known types of invariants are studied with respect to toll convexity, and toll convex sets in three standard graph products are completely described.     

A local duality principle in derived categories of commutative Noetherian rings

Let R be a commutative Noetherian ring. We introduce the notion of colocalization functors ${\gamma }_W$ with supports in arbitrary subsets W of Spec R. If W is a specialization-closed subset, then ${\gamma }_W$ coincides with the right derived functor ${\mathrm{R}\mathrm{\Gamma }}_W$ of the section functor ${\mathrm{\Gamma }}_W$ with support in W. We prove that the local duality theorem and the vanishing theorem of Grothendieck type hold for ${\gamma }_W$ with W being an arbitrary subset.     

A formal approach to subgrammar extraction for NLP

The problem of subgrammar extraction is precisely defined in the following way: Given a grammar $G$ and a set of words $W$, find a smallest subgrammar of $G$ that accepts the same set of sentences from $W^1$ as $G$, and for each of them produces the same parse trees. In practical Natural Language Processing applications, the set of words $W$ is obtained from the text unit. There are practical motivations for doing this operation “just-in-time”, i.e. just before processing the text; hence it is required that this operation be done in an automatic and efficient way. After defining the problem in the general framework, we discuss the problem for context-free grammars (CFG), and give an efficient algorithm for it. We prove that finding the smallest subgrammar for HPSGs is an NP-hard problem, and give an efficient algorithm that solves an easier, approximate version of the problem. We also discuss how the algorithm can be efficiently implemented.     

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that $|W|=k$, for a fixed positive integer k. The enumeration is performed within $O(n)$ delay, where $n=|V(G)|$ consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset $W\subseteq V(G)$ can be computed in polynomial time, provided that the size of W is bounded by a constant.     

W-associahedra have the non-leaving-face property

We use a projection argument to uniformly prove that $W$-permutahedra and $W$-associahedra have the property that if $v,v^{\prime }$ are two vertices on the same face $f$, then any geodesic between $v$ and $v^{\prime }$ does not leave $f$. In type $A$, we show that our geometric projection recovers a slight modification of the combinatorial projection in Sleator et al. (1988).     

The invertibility of adapted perturbations of identity on the Wiener space

Let $(W,H,\mu )$ be the classical Wiener space. Assume that $U=I_W+u$ is an adapted perturbation of identity, i.e., $u:W\to H$ is adapted to the canonical filtration of W. We give some sufficient analytic conditions on u which imply the invertibility of the map U. To cite this article: A.S. Üstünel, M. Zakai, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

A characterization of a class of hyperplanes of DW(2n−1,F)

A hyperplane of the symplectic dual polar space $DW(2n?1,\mathbb{F})$, $n\ge 2$, is said to be of subspace-type if it consists of all maximal singular subspaces of $W(2n?1,\mathbb{F})$ meeting a given $(n?1)$-dimensional subspace of $\text{PG}(2n?1,\mathbb{F})$. We show that a hyperplane of $DW(2n?1,\mathbb{F})$ is of subspace-type if and only if every hex $F$ of $DW(2n?1,\mathbb{F})$ intersects it in either $F$, a singular hyperplane of $F$ or the extension of a full subgrid of a quad. In the case $\mathbb{F}$ is a perfect field of characteristic 2, a stronger result can be proved, namely a hyperplane $H$ of $DW(2n?1,\mathbb{F})$ is of subspace-type or arises from the spin-embedding of $DW(2n?1,\mathbb{F})?DQ(2n,\mathbb{F})$ if and only if every hex $F$ intersects it in either $F$, a singular hyperplane of $F$, a hexagonal hyperplane of $F$ or the extension of a full subgrid of a quad.     

Symplectic subspaces of symplectic Grassmannians

Let $V$ be a non-degenerate symplectic space of dimension $2n$ over the field $\mathbb{F}$ and for a natural number $l<n$ denote by $C_l\left(V\right)$ the incidence geometry whose points are the totally isotropic $l$-dimensional subspaces of $V$. Two points $U,W$ of $C_l\left(V\right)$ will be collinear when $W\subset U^{\perp }$ and $dim(U\cap W)=l-1$ and then the line on $U$ and $W$ will consist of all the $l$-dimensional subspaces of $U+W$ which contain $U\cap W$. The isomorphism type of this geometry is denoted by $C_{n,l}\left(\mathbb{F}\right)$. When $\mathrm{char}\left(\mathbb{F}\right)\ne 2$ we classify subspaces $S$ of $C_l\left(\mathbb{F}\right)$ where $S\cong C_{m,k}\left(\mathbb{F}\right)$.