Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

Self-orthogonal decompositions of graphs into matchings

Given a simple graph H, a self-orthogonal decomposition (SOD) of H is a collection of subgraphs of H, all isomorphic to some graph G, such that every edge of H occurs in exactly two of the subgraphs and any two of the subgraphs share exactly one edge. Our concept of SOD is a natural generalization of the well-studied orthogonal double covers (ODC) of complete graphs. If for some given G there is an appropriate H, then our goal is to find one with as few vertices as possible. Special attention is paid to the case when G a matching with $n-1$ edges. We conjecture that $v(H)=2n-2$ is best possible if $n\ne 4$ is even and $v(H)=2n$ if n is odd. We present a construction which proves this conjecture for all but 4 of the possible residue classes of n modulo 18.     

On mixed codes with covering radius 1 and minimum distance 2: (extended abstract)

Let R, S and T be finite sets with $|R|=r$, $|S|=s$ and $|T|=t$. A code $C\subset R\times S\times T$ with covering radius 1 and minimum distance 2 is closely connected to a certain generalized partial Latin rectangle. We present various constructions of such codes and some lower bounds on their minimal cardinality $K(r,s,t;2)$. These bounds turn out to be best possible in many instances. Focussing on the special case $t=s$ we determine $K(r,s,s;2)$ when r divides s, when $r=s-1$, when s is large, relative to r, when r is large, relative to s, as well as $K(3r,2r,2r;2)$. Finally, a table with bounds on $K(r,s,s;2)$ is given.     

The indecomposable tournaments T with |W5(T)|=|T|−2

We consider a tournament $T=(V,A)$. For $X?V$, the subtournament of T induced by X is $T[X]=(X,A\cap (X\times X))$. An interval of T is a subset X of V such that, for $a,b\in X$ and $x\in V?X$, $(a,x)\in A$ if and only if $(b,x)\in A$. The trivial intervals of T are ?, $\{x\}(x\in V)$ and V. A tournament is indecomposable if all its intervals are trivial. For $n?2$, $W_{2n+1}$ denotes the unique indecomposable tournament defined on $\{0,\dots ,2n\}$ such that $W_{2n+1}[\{0,\dots ,2n?1\}]$ is the usual total order. Given an indecomposable tournament T, $W_5(T)$ denotes the set of $v\in V$ such that there is $W?V$ satisfying $v\in W$ and $T[W]$ is isomorphic to $W_5$. Latka [6] characterized the indecomposable tournaments T such that $W_5(T)=?$. The authors [1] proved that if $W_5(T)\ne ?$, then $|W_5(T)|?|V|?2$. In this note, we characterize the indecomposable tournaments T such that $|W_5(T)|=|V|?2$.     

Improved Cotlar's inequality in the context of local Tb theorems

In the context of local Tb theorems with $L^p$ testing conditions we prove an enhanced Cotlar's inequality. This is related to the problem of removing the so called buffer assumption of Hytönen–Nazarov, which is the final barrier for the full solution of S. Hofmann's problem. We also investigate the problem of extending the Hytönen–Nazarov result to non-homogeneous measures. We work not just with the Lebesgue measure but with measures μ in ${\mathbb{R}}^d$ satisfying $\mu (B(x,r))\le C{r}^n$, $n\in (0,d]$. The range of exponents in the Cotlar type inequality depend on n. Without assuming buffer we get the full range of exponents $p,q\in (1,2]$ for measures with $n\le 1$, and in general we get $p,q\in [2??(n),2]$, $?(n)>0$. Consequences for (non-homogeneous) local Tb theorems are discussed.     

On Vertex Partitions and the Colin de Verdière Parameter

We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with $\mu (G)⩾2$ admits a vertex partition into two graphs with μ at most $\mu (G)-1$. Here we prove that any graph G with $\mu (G)⩾3$ admits a vertex partition into three graphs with μ at most $\mu (G)-2$. This study is extended to other minor-monotone graph parameters like the Hadwiger number.     

The enumeration of permutations whose posets have a maximum element

Recently, Tenner [B.E. Tenner, Reduced decompositions and permutation patterns, J. Algebraic. Combin., in press, preprint arXiv: math.CO/0506242] studied the set of posets of a permutation of length n with unique maximal element, which arise naturally when studying the set of zonotopal tilings of Elnitsky's polygon. In this paper, we prove that the number of such posets is given by$P_{5n}-4P_{5(n-1)}+2P_{5(n-2)}-\sum _{j=0}^{n-2}{C}_j{P}_{5(n-2-j)},$ where $P_n$ is the nth Padovan number and $C_n$ is the nth Catalan number.     

Le problème des diviseurs de zéro pour les groupes de Lie nilpotents

Let G be a non-Abelian, connected, nilpotent Lie group. Then there exist $0\ne \alpha \in C_c(G)$ and $0\ne \xi \in L^2(G)$ such that $\alpha 1\xi =0$, contrary to what happens for the group ${\mathbb{R}}^n$. Moreover, the set of zero divisors is a total subset of $L^2(G)$. This result is first proven for the Heisenberg group $H_n$ where it is based on the existence of non-trivial Schwartz functions f satisfying $f1(X_k+\mathrm{i}{Y}_k)=0$ for $1?k?n$. To cite this article: J. Ludwig et al., C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Solvable PST-groups,strong Sylow bases and mutually permutable products

A subgroup H of a group G is said to permute with the subgroup K of G if $HK=KH$. Subgroups H and K are mutually permutable (totally permutable) in G if every subgroup of H permutes with K and every subgroup of K permutes with H (if every subgroup of H permutes with every subgroup of K). If H and K are mutually permutable and $H\cap K=1$, then H and K are totally permutable. A subgroup H of G is S-permutable in G if H permutes with every Sylow subgroup of G. A group G is called a PST-group if S-permutability is a transitive relation in G. Let $\{p_1,\dots ,p_n,p_{n+1},\dots ,p_k\}$ be the set of prime divisors of the order of a finite group G with $\{p_1,\dots ,p_n\}$ the set of prime divisors of the order of the normal subgroup N of G. A set of Sylow subgroups $\{P_1,\dots ,P_n,P_{n+1},\dots ,P_k\}$, $P_i\in {\mathrm{Syl}}_{p_i}(G)$, form a strong Sylow system with respect to N if $P_i{P}_j$ is a mutually permutable product for all $i\in \{1,2,\dots ,n\}$ and $j\in \{1,2,\dots ,k\}$. We show that a finite group G is a solvable PST-group if and only if it has a normal subgroup N such that $G/N$ is nilpotent and G has a strong Sylow system with respect to N. It is also shown that G is a solvable PST-group if and only if G has a normal solvable PST-subgroup N and $G/N^{″}$ is a solvable PST-group.     

A failing eigenfunction expansion associated with an indefinite Sturm–Liouville problem

We consider the indefinite Sturm–Liouville problem $?f^{″}=\lambda rf$, $f^{\prime }(?1)=f^{\prime }(1)=0$ where $r\in L^1[?1,1]$ satisfies $xr(x)>0$. Conditions are presented such that the (normed) eigenfunctions $f_n$ form a Riesz basis of the Hilbert space $L_{|r|}^2[?1,1]$ (using known results for a modified problem). The main focus is on the non-Riesz basis case: We construct a function $f\in L_{|r|}^2[?1,1]$ having no eigenfunction expansion $f=\sum {\beta }_n{f}_n$. Furthermore, a sequence $({\alpha }_n)\in l^2$ is constructed such that the “Fourier series” $\sum {\alpha }_n{f}_n$ does not converge in $L_{|r|}^2[?1,1]$. These problems are closely related to the regularity property of the closed non-semibounded symmetric sesquilinear form $\mathfrak{t}[u,v]=\int u^{\prime }{\overline{v}}^{\prime }pdx$ with Dirichlet boundary conditions in $L^2[?1,1]$ where $p=1/r$. For the associated operator $T_{\mathfrak{t}}$ we construct elements in the difference between $\mathrm{dom}\mathfrak{t}$ and the domain of the associated regular closed form, i.e. $\mathrm{dom}{|T_{\mathfrak{t}}|}^{1/2}$.