Uniformization of {\mathcal {G}}-bundles

We show some of the conjectures of Pappas and Rapoport concerning the moduli stack Bun_G{{\rm Bun}_\mathcal {G}} of G{\mathcal {G}}-torsors on a curve C, where G{\mathcal {G}} is a semisimple Bruhat-Tits group scheme on C. In particular we prove the analog of the uniformization theorem of Drinfeld-Simpson in this setting. Furthermore we apply this to compute the connected components of these moduli stacks and to calculate the Picard group of Bun_G{{\rm Bun}_\mathcal {G}} in case G{\mathcal {G}} is simply connected.     

Induced Graph Packing Problems

Let H{\mathcal{H}} be a set of undirected graphs. The induced H{\mathcal{H}} -packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H{\mathcal{H}} . In this paper we focus on the case when H{\mathcal{H}} consists of factor-critical graphs and a certain family of ‘propellers’. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai–Edmonds type structure theorem and a Berge–Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H{\mathcal{H}} consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans.     

Counting Ω-ideals

Let ${\mathbb{A}}Let \mathbbA{\mathbb{A}} be a universal algebra of signature Ω, and let I{\mathcal{I}} be an ideal in the Boolean algebra P_\mathbbA{\mathcal{P}_{\mathbb{A}}} of all subsets of \mathbbA{\mathbb{A}} . We say that I{\mathcal{I}} is an Ω-ideal if I{\mathcal{I}} contains all finite subsets of \mathbbA{\mathbb{A}} and f(Aⁿ) ? I{f(A^{n}) \in \mathcal{I}} for every n-ary operation f ? W{f \in \Omega} and every A ? I{A \in \mathcal{I}} . We prove that there are 2^2à₀{2^{2^{\aleph_0}}} Ω-ideals in P_\mathbbA{\mathcal{P}_{\mathbb{A}}} provided that \mathbbA{\mathbb{A}} is countably infinite and Ω is countable.     

Desingularization of singular Riemannian foliation

Let F{\mathcal{F}} be a singular Riemannian foliation on a compact Riemannian manifold M. By successive blow-ups along the strata of F{\mathcal{F}} we construct a regular Riemannian foliation [^(F)]{\hat{\mathcal{F}}} on a compact Riemannian manifold [^(M)]{\hat{M}} and a desingularization map [^(r)]:[^(M)]? M{\hat{\rho}:\hat{M}\rightarrow M} that projects leaves of [^(F)]{\hat{\mathcal{F}}} into leaves of F{\mathcal{F}}. This result generalizes a previous result due to Molino for the particular case of a singular Riemannian foliation whose leaves were the closure of leaves of a regular Riemannian foliation. We also prove that, if the leaves of F{\mathcal{F}} are compact, then, for each small ${\epsilon >0 }${\epsilon >0 }, we can find [^(M)]{\hat{M}} and [^(F)]{\hat{\mathcal{F}}} so that the desingularization map induces an e{\epsilon}-isometry between M/F{M/\mathcal{F}} and [^(M)]/[^(F)]{\hat{M}/\hat{\mathcal{F}}}. This implies in particular that the space of leaves M/F{M/\mathcal{F}} is a Gromov-Hausdorff limit of a sequence of Riemannian orbifolds {([^(M)]_n/[^(F)]_n)}{\{(\hat{M}_{n}/\hat{\mathcal{F}}_{n})\}}.     

Lifting of convex functions on Carnot groups and lack of convexity for a gauge function

Let ${\mathbb{G}}Let \mathbbG{\mathbb{G}} be a Carnot group of step r and m generators and homogeneous dimension Q. Let \mathbbF_m,r{\mathbb{F}_{m,r}} denote the free Lie group of step r and m generators. Let also p:\mathbbF_m,r?\mathbbG{\pi:\mathbb{F}_{m,r}\to\mathbb{G}} be a lifting map. We show that any horizontally convex function u on \mathbbG{\mathbb{G}} lifts to a horizontally convex function u°p{u\circ \pi} on \mathbbF_m,r{\mathbb{F}_{m,r}} (with respect to a suitable horizontal frame on \mathbbF_m,r{\mathbb{F}_{m,r}}). One of the main aims of the paper is to exhibit an example of a sub-Laplacian L=?_j=1^m X_j²{\mathcal{L}=\sum_{j=1}^m X_j^2} on a Carnot group of step two such that the relevant L{\mathcal{L}}-gauge function d (i.e., d ^2-Q is the fundamental solution for L{\mathcal{L}}) is not h-convex with respect to the horizontal frame {X ₁, . . . , X _m }. This gives a negative answer to a question posed in Danielli et al. (Commun. Anal. Geom. 11 (2003), 263–341).     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

Augmented Teichmüller spaces and orbifolds

We study complex analytic properties of the augmented Teichmüller spaces [`(T)]<sub>g,n</sub>{\overline{\mathcal{T}}_{g,n}} obtained by adding to the classical Teichmüller spaces T<sub>g,n</sub>{\mathcal{T}_{g,n}} points corresponding to Riemann surfaces with nodal singularities. Unlike T<sub>g,n</sub>{\mathcal{T}_{g,n}}, the space [`(T)]_g,n{\overline{\mathcal{T}}_{g,n}} is not a complex manifold (it is not even locally compact). We prove, however, that the quotient of the augmented Teichmüller space by any finite index subgroup of the Teichmüller modular group has a canonical structure of a complex orbifold. Using this structure, we construct natural maps from [`(T)]{\overline{\mathcal{T}}} to stacks of admissible coverings of stable Riemann surfaces. This result is important for understanding the cup-product in stringy orbifold cohomology. We also establish some new technical results from the general theory of orbifolds which may be of independent interest.     

Around splitting and reaping for partitions of ω

We investigate splitting number and reaping number for the structure (ω) ^ω of infinite partitions of ω. We prove that \mathfrakr_d ￡ non(M),non(N),\mathfrakd{\mathfrak{r}_{d}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N}),\mathfrak{d}} and \mathfraks_d 3 \mathfrakb{\mathfrak{s}_{d}\geq\mathfrak{b}} . We also show the consistency results ${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})}${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and ${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})}${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})} . To prove the consistency \mathfrakr_d < add(M){\mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and \mathfraks_d < cof(M){\mathfrak{s}_{d} < \mathsf{cof}(\mathcal{M})} we introduce new cardinal invariants \mathfrakr_pair{\mathfrak{r}_{pair}} and \mathfraks_pair{\mathfrak{s}_{pair}} . We also study the relation between \mathfrakr_pair, \mathfraks_pair{\mathfrak{r}_{pair}, \mathfrak{s}_{pair}} and other cardinal invariants. We show that cov(M),cov(N) ￡ \mathfrakr_pair ￡ \mathfraks_d,\mathfrakr{\mathsf{cov}(\mathcal{M}),\mathsf{cov}(\mathcal{N})\leq\mathfrak{r}_{pair}\leq\mathfrak{s}_{d},\mathfrak{r}} and \mathfraks ￡ \mathfraks_pair ￡ non(M),non(N){\mathfrak{s}\leq\mathfrak{s}_{pair}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N})} .     

Corrigendum to “Resource-monotonicity for house allocation problems”

Ehlers and Klaus (Int J Game Theory 32:545–560, 2003) study so-called allocation problems and claim to characterize all rules satisfying efficiency, independence of irrelevant objects, and resource-monotonicity on two preference domains (Ehlers and Klaus 2003, Theorem 1). They explicitly prove Theorem 1 for preference domain R₀{\mathcal{R}_0} which requires that the null object is always the worst object and mention that the corresponding proofs for the larger domain R{\mathcal{R}} of unrestricted preferences “are completely analogous.” In Example 1 and Lemma 1, this corrigendum provides a counterexample to Ehlers and Klaus (2003, Theorem 1) on the general domain R{\mathcal{R}} . We also propose a way of correcting the result on the general domain R{\mathcal{R}} by strengthening independence of irrelevant objects: in addition to requiring that the chosen allocation should depend only on preferences over the set of available objects (which always includes the null object), we add a situation in which the allocation should also be invariant when preferences over the null object change. Finally, we offer a short proof of the corrected result that uses the established result of Theorem 1 for the restricted domain R₀{\mathcal{R}_0}.     

On the Right (Left) Invertible Completions for Operator Matrices

Let ${\mathcal {H}_{1}}Let H₁{\mathcal {H}_{1}} and H₂{\mathcal {H}_{2}} be separable Hilbert spaces, and let A ? B(H₁), B ? B(H₂){A \in \mathcal {B}(\mathcal {H}_{1}),\, B \in \mathcal {B}(\mathcal {H}_{2})} and C ? B(H₂, H₁){C \in \mathcal {B}(\mathcal {H}_{2},\, \mathcal {H}_{1})} be given operators. A necessary and sufficient condition is given for ${\left(\begin{smallmatrix}A &\enspace C\\ X &\enspace B \end{smallmatrix}\right)}${\left(\begin{smallmatrix}A &\enspace C\\ X &\enspace B \end{smallmatrix}\right)} to be a right (left) invertible operator for some X ? B(H₁, H₂){X \in \mathcal {B}(\mathcal {H}_{1},\, \mathcal {H}_{2})}. Furthermore, some related results are obtained.     

Ergodic Subequivalence Relations Induced by a Bernoulli Action

Let Γ be a countable group and denote by S{\mathcal{S}} the equivalence relation induced by the Bernoulli action G\curvearrowright [0, 1]^G{\Gamma\curvearrowright [0, 1]^{\Gamma}}, where [0, 1]^Γ is endowed with the product Lebesgue measure. We prove that, for any subequivalence relation R{\mathcal{R}} of S{\mathcal{S}}, there exists a partition {X _i } _i≥0 of [0, 1]^Γ into R{\mathcal{R}}-invariant measurable sets such that R_|X0{\mathcal{R}_{\vert X_{0}}} is hyperfinite and R_|Xi{\mathcal{R}_{\vert X_{i}}} is strongly ergodic (hence ergodic and non-hyperfinite), for every i ≥ 1.     

On quasiconvexity and relatively hyperbolic structures on groups

Let G be a group which is hyperbolic relative to a collection of subgroups H₁{\mathcal{H}_1}, and it is also hyperbolic relative to a collection of subgroups H₂{\mathcal{H}_2}. Suppose that H₁ ì H₂{\mathcal{H}_1 \subset \mathcal{H}_2}. We characterize when a relative quasiconvex subgroup of (G, H₂){(G, \mathcal H_2)} is still relatively quasiconvex in (G, H₁){(G, \mathcal H_1)}. We also show that relative quasiconvexity is preserved when passing from (G, H₁){(G, \mathcal H_1)} to (G, H₂){(G, \mathcal H_2)}. Applications are discussed.     

On a graph related to permutability in finite groups

For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete.     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

On Well-posed Mutually Nearest and Mutually Furthest Point Problems in Banach Spaces

Let G be a non-empty closed(resp．bounded closed)boundedly relatively weakly compact subset in a strictly convex Kadec Banach space X．Let K(X)denote the space of all non-empty compact convex subsets of X endowed with the Hausdorff distance．Moreover,let KG(X)denote the closure of the set {A∈K(x)：A∩G=0}．We prove that the set of all A∈KG(X)(resp．A∈K(X)),such that the minimization (resp．maximization)problem min(A,G)(resp．max(A,G))is well posed,contains a dense Gδ-subset of KG(X)(resp．K(X))．thus extending the recent results due to Blasi,Myjak and Papini and Li．     

Hedetniemi’s Conjecture and Dense Boolean Lattices

The category D{\mathcal{D}} of finite directed graphs is Cartesian closed, hence it has a product and exponential objects. For a fixed K, let K^DK^{\mathcal{D}} be the class of all directed graphs of the form K ^G , preordered by the existence of homomorphisms, and factored by homomorphic equivalence. It has long been known that K^DK^{\mathcal{D}} is always a Boolean lattice. In this paper we prove that for any complete graph K _n with n ≥ 3, K_n^DK_n^{\mathcal{D}} is dense, hence up to isomorphism it is the unique countable dense Boolean lattice. In graph theory, the structure of K_n^DK_n^{\mathcal{D}} is connected to the conjecture of Hedetniemi on the chromatic number of a categorical product of graphs.     

Cartan-Dieudonné Theorem for {\mathcal {A}}-Modules

Like the classical Cartan-Dieudonné theorem, the sheaf-theoretic version shows that A{\mathcal {A}}-isometries on a convenient A{\mathcal {A}}-module E{\mathcal {E}} of rank n can be decomposed in at most n orthogonal symmetries (reflections) with respect to non-isotropic hyperplanes. However, the coefficient sheaf of \mathbb C{\mathbb {C}}-algebras A{\mathcal {A}} is assumed to be a PID \mathbb C{\mathbb {C}}-algebra sheaf and, if (E,f){(\mathcal {E},\phi)} is a pairing with f{\phi} a non-degenerate A{\mathcal {A}}-bilinear morphism, we assume that E{\mathcal {E}} has nowhere-zero (local) isotropic sections; but, for Riemannian sheaves of A{\mathcal {A}}-modules, this is not necessarily required.     

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes and graph classes , an ()-system is a Boolean dynamical system such that all local transition functions lie in and the underlying graph lies in . Let be a class of Boolean functions which is closed under composition and let be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If contains the self-dual functions and contains the planar graphs, then the fixed-point existence problem for ()-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If contains the self-dual functions and contains the graphs having vertex covers of size one, then the fixed-point existence problem for ()-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.      

On $${\mathcal{F}}$$ -supplemented subgroups of finite groups

Let G be a finite group and a formation of finite groups. We say that a subgroup H of G is -supplemented in G if there exists a subgroup T of G such that G = TH and is contained in the -hypercenter of G/H _G . In this paper, we use -supplemented subgroups to study the structure of finite groups. A series of previously known results are unified and generalized. Research of the author is supported by a NNSF grant of China (Grant #10771180).