Largest initial segments pointwise fixed by automorphisms of models of set theory

Given a model \(\mathcal {M}\) of set theory, and a nontrivial automorphism j of \(\mathcal {M}\), let \(\mathcal {I}_{\mathrm {fix}}(j)\) be the submodel of \(\mathcal {M}\) whose universe consists of elements m of \(\mathcal {M}\) such that \(j(x)=x\) for every x in the transitive closure of m (where the transitive closure of m is computed within \(\mathcal {M}\)). Here we study the class \(\mathcal {C}\) of structures of the form \(\mathcal {I}_{\mathrm {fix}}(j)\), where the ambient model \(\mathcal {M}\) satisfies a frugal yet robust fragment of \(\mathrm {ZFC}\) known as \(\mathrm {MOST}\), and \(j(m)=m\) whenever m is a finite ordinal in the sense of \(\mathcal {M}.\) Our main achievement is the calculation of the theory of \(\mathcal {C}\) as precisely \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\). The following theorems encapsulate our principal results: Theorem A. Every structure in \(\mathcal {C}\) satisfies \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm { Collection}\). Theorem B. Each of the following three conditions is sufficient for a countable structure \(\mathcal {N}\) to be in \(\mathcal {C}\):(a) \(\mathcal {N}\) is a transitive model of \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\).(b) \(\mathcal {N}\) is a recursively saturated model of \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\).(c) \(\mathcal {N}\) is a model of \(\mathrm {ZFC}\). Theorem C. Suppose \(\mathcal {M}\) is a countable recursively saturated model of \(\mathrm {ZFC}\) and I is a proper initial segment of \(\mathrm {Ord}^{\mathcal {M}}\) that is closed under exponentiation and contains \(\omega ^\mathcal {M}\) . There is a group embedding \(j\longmapsto \check{j}\) from \(\mathrm {Aut}(\mathbb {Q})\) into \(\mathrm {Aut}(\mathcal {M})\) such that I is the longest initial segment of \(\mathrm {Ord}^{\mathcal {M}}\) that is pointwise fixed by \(\check{j}\) for every nontrivial \(j\in \mathrm {Aut}(\mathbb {Q}).\) In Theorem C, \(\mathrm {Aut}(X)\) is the group of automorphisms of the structure X, and \(\mathbb {Q}\) is the ordered set of rationals.     

Vizing Bound for the Chromatic Number on Some Graph Classes

We are interested in hereditary classes of graphs \({\mathcal {G}}\) such that every graph \(G \in {\mathcal {G}}\) satisfies \(\varvec{\chi }(G) \le \omega (G) + 1\), where \(\chi (G)\) (\(\omega (G)\)) denote the chromatic (clique) number of G. This upper bound is called the Vizing bound for the chromatic number. Apart from perfect graphs few classes are known to satisfy the Vizing bound in the literature. We show that if G is (\(P_6, S_{1, 2, 2}\), diamond)-free, then \(\chi (G) \le \omega (G)+1\), and we give examples to show that the bound is sharp.     

Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.     

Nonsolvable Groups with no Prime Dividing Four Character Degrees

Given a finite group G, we say that G has property \(\mathcal P_{k}\) if every set of k distinct irreducible character degrees of G is setwise relatively prime. In this paper, we show that if G is a finite nonsolvable group satisfying \(\mathcal P_{4}, \)then G has at most 8 distinct character degrees. Combining with work of D. Benjamin on finite solvable groups, we deduce that a finite group G has at most 9 distinct character degrees if G has property \(\mathcal P_{4}\) and this bound is sharp.     

Perfect state transfer in Laplacian quantum walk

For a graph G and a related symmetric matrix M, the continuous-time quantum walk on G relative to M is defined as the unitary matrix \(U(t) = \exp (-itM)\), where t varies over the reals. Perfect state transfer occurs between vertices u and v at time \(\tau \) if the (u, v)-entry of \(U(\tau )\) has unit magnitude. This paper studies quantum walks relative to graph Laplacians. Some main observations include the following closure properties for perfect state transfer. If an n-vertex graph has perfect state transfer at time \(\tau \) relative to the Laplacian, then so does its complement if \(n\tau \in 2\pi {\mathbb {Z}}\). As a corollary, the join of \(\overline{K}_{2}\) with any m-vertex graph has perfect state transfer relative to the Laplacian if and only if \(m \equiv 2\pmod {4}\). This was previously known for the join of \(\overline{K}_{2}\) with a clique (Bose et al. in Int J Quant Inf 7:713–723, 2009). If a graph G has perfect state transfer at time \(\tau \) relative to the normalized Laplacian, then so does the weak product \(G \times H\) if for any normalized Laplacian eigenvalues \(\lambda \) of G and \(\mu \) of H, we have \(\mu (\lambda -1)\tau \in 2\pi {\mathbb {Z}}\). As a corollary, a weak product of \(P_{3}\) with an even clique or an odd cube has perfect state transfer relative to the normalized Laplacian. It was known earlier that a weak product of a circulant with odd integer eigenvalues and an even cube or a Cartesian power of \(P_{3}\) has perfect state transfer relative to the adjacency matrix. As for negative results, no path with four vertices or more has antipodal perfect state transfer relative to the normalized Laplacian. This almost matches the state of affairs under the adjacency matrix (Godsil in Discret Math 312(1):129–147, 2011).     

Inflation of Finite Lattices Along All-or-nothing Sets

We introduce a new generalization of Alan Day’s doubling construction. For ordered sets \(\mathcal {L}\) and \(\mathcal {K}\) and a subset \(E \subseteq \ \leq _{\mathcal {L}}\) we define the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) arising from inflation of \(\mathcal {L}\) along E by \(\mathcal {K}\). Under the restriction that \(\mathcal {L}\) and \(\mathcal {K}\) are finite lattices, we find those subsets \(E \subseteq \ \leq _{\mathcal {L}}\) such that the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) is a lattice. Finite lattices that can be constructed in this way are classified in terms of their congruence lattices.A finite lattice is binary cut-through codable if and only if there exists a 0?1 spanning chain \(\left \{\theta _{i}\colon 0 \leq i \leq n \right \}\) in \(Con(\mathcal {L})\) such that the cardinality of the largest block of ?? _i /?? _i?1 is 2 for every i with 1≤i≤n. These are exactly the lattices that can be constructed by inflation from the 1-element lattice using only the 2-element lattice. We investigate the structure of binary cut-through codable lattices and describe an infinite class of lattices that generate binary cut-through codable varieties.     

Symbolic Computation Applied to the Study of the Kernel of a Singular Integral Operator with Non-Carleman Shift and Conjugation

On the Hilbert space \(\widetilde{L}_{2}(\mathbb {T})\) the singular integral operator with non-Carleman shift and conjugation \(K=P_{+}+(aI+AC)P_{-}\) is considered, where \(P_{\pm }\) are the Cauchy projectors, \(A=\sum \nolimits _{j=0}^{m}a_{j}U^{j}\), \(a,a_{j}\), \(j=\overline{1,m}\), are continuous functions on the unit circle \(\mathbb {T}\), U is the shift operator and C is the operator of complex conjugation. We show how the symbolic computation capabilities of the computer algebra system Mathematica can be used to explore the dimension of the kernel of the operator K. The analytical algorithm [ADimKer-NonCarleman] is presented; several nontrivial examples are given.     

Notes on the Kazhdan–Lusztig Theorem on Equivalence of the Drinfeld Category and the Category of $\boldsymbol{U}_{\!\boldsymbol q}{\boldsymbol {\mathfrak g}}$-Modules

We discuss the proof of Kazhdan and Lusztig of the equivalence of the Drinfeld category \({\mathcal D}({\mathfrak g},\hbar)\) of \({\mathfrak g}\)-modules and the category of finite dimensional \(U_q{\mathfrak g}\)-modules, \(q=e^{\pi i\hbar}\), for \(\hbar\in{\mathbb C}\setminus{\mathbb Q}^*\). Aiming at operator algebraists the result is formulated as the existence for each \(\hbar\in i{\mathbb R}\) of a normalized unitary 2-cochain \({\mathcal F}\) on the dual \(\hat G\) of a compact simple Lie group G such that the convolution algebra of G with the coproduct twisted by \({\mathcal F}\) is *-isomorphic to the convolution algebra of the q-deformation G _q of G, while the coboundary of \({\mathcal F}^{-1}\) coincides with Drinfeld’s KZ-associator defined via monodromy of the Knizhnik–Zamolodchikov equations.     

Group theoretic characterizations of Buekenhout–Metz unitals in $\mathop{\mathrm{PG}}(2,q^{2})$

Let G be the group of projectivities stabilizing a unital \(\mathcal{U}\) in \(\mathop{\mathrm{PG}}(2,q^{2})\) and let A,B be two distinct points of \(\mathcal{U}\). In this paper we prove that, if G has an elation group of order q with center A and a group of projectivities stabilizing both A and B of order a divisor of q?1 greater than \(2(\sqrt{q}-1)\), then \(\mathcal{U}\) is an ovoidal Buekenhout–Metz unital. From this result two group theoretic characterizations of orthogonal Buekenhout–Metz unitals are given.     

Affine ADE bundles over surfaces with $$ p _{g}=0$$

Given any Kodaira curve C in a complex surface X, we construct a simply-laced affine Lie algebra bundle \(\mathcal {E}\) over X. When \( p _{g}(X)=0\), we construct deformations of holomorphic structures on \(\mathcal {E}\) such that the new bundle is trivial over any ADE curve \( C^{\prime }\) inside C and therefore descends to the singular surface obtained by contracting \(C^{\prime }\).     

The limit case of a domination property

The domination number γ(G) of a connected graph G of order n is bounded below by(n+2-e(G))/ 3 , where (G) denotes the maximum number of leaves in any spanning tree of G. We show that (n+2-e(G))/ 3 = γ(G) if and only if there exists a tree T ∈ T ( G) ∩ R such that n1(T ) = e(G), where n1(T ) denotes the number of leaves of T1, R denotes the family of all trees in which the distance between any two distinct leaves is congruent to 2 modulo 3, and T (G) denotes the set composed by the spanning trees of G. As a consequence of the study, we show that if (n+2-e(G))/ 3 = γ(G), then there exists a minimum dominating set in G whose induced subgraph is an independent set. Finally, we characterize all unicyclic graphs G for which equality (n+2-e(G))/ 3= γ(G) holds and we show that the length of the unique cycle of any unicyclic graph G with (n+2-e(G))/ 3= γ(G) belongs to {4} ∪ {3 , 6, 9, . . . }.     

Matching Trees for Simplicial Complexes and Homotopy Type of Devoid Complexes of Graphs

We generalize some homotopy calculation techniques such as splittings and matching trees that are introduced for the computations in the case of the independence complexes of graphs to arbitrary simplicial complexes. We then exemplify their efficiency on some simplicial complexes, the devoid complexes of graphs, \(\mathcal {D}(G;\mathcal {F})\) whose faces are vertex subsets of G that induce \(\mathcal {F}\)-free subgraphs, where G is a multigraph and \(\mathcal {F}\) is a family of multigraphs. Additionally, we compute the homotopy type of dominance complexes of chordal graphs.     

Hausdorffness for Lie algebra homology of Schwartz spaces and applications to the comparison conjecture

Let H be a real algebraic group acting equivariantly with finitely many orbits on a real algebraic manifold X and a real algebraic bundle \({\mathcal {E}}\) on X. Let \(\mathfrak {h}\) be the Lie algebra of H. Let \(\mathcal {S}(X,{\mathcal {E}})\) be the space of Schwartz sections of \({\mathcal {E}}\). We prove that \(\mathfrak {h}\mathcal {S}(X,{\mathcal {E}})\) is a closed subspace of \(\mathcal {S}(X,{\mathcal {E}})\) of finite codimension. We give an application of this result in the case when H is a real spherical subgroup of a real reductive group G. We deduce an equivalence of two old conjectures due to Casselman: the automatic continuity and the comparison conjecture for zero homology. Namely, let \(\pi \) be a Casselman–Wallach representation of G and V be the corresponding Harish–Chandra module. Then the natural morphism of coinvariants \(V_{\mathfrak {h}}\rightarrow \pi _{\mathfrak {h}}\) is an isomorphism if and only if any linear \(\mathfrak {h}\)-invariant functional on V is continuous in the topology induced from \(\pi \). The latter statement is known to hold in two important special cases: if H includes a symmetric subgroup, and if H includes the nilradical of a minimal parabolic subgroup of G.     

Some infinite families of Ramsey ($${\varvec{P}}_\mathbf{3},{\varvec{P}}_{{\varvec{n}}}$$)-minimal trees

For any given two graphs G and H, the notation \(F\rightarrow \) (G, H) means that for any red–blue coloring of all the edges of F will create either a red subgraph isomorphic to G or a blue subgraph isomorphic to H. A graph F is a Ramsey (G, H)-minimal graph if \(F\rightarrow \) (G, H) but \(F-e\nrightarrow (G,H)\), for every \(e \in E(F)\). The class of all Ramsey (G, H)-minimal graphs is denoted by \(\mathcal {R}(G,H)\). In this paper, we construct some infinite families of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n=8\) and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n\ge 10\).     

Approximations for constructing tree-form structures using specific material with fixed length

Substituting for the ordinary objective to minimize the sum of lengths of all edges in some graph structure of a weighted graph, we propose a new problem of constructing certain tree-form structure in same graph, where all edges needed in such a tree-form structure are supposed to be cut from some pieces of a specific material with fixed length. More precisely, we study a new problem defined as follows: a weighted graph \(G=(V,E; w)\), a tree-form structure \(\mathcal{S}\) and some pieces of specific material with length L, where a length function \(w:E\rightarrow Q^+\), satisfying \(w(u,v) \le L\) for each edge uv in G, we are asked how to construct a required tree-form structure \(\mathcal{S}\) as a subgraph \(G'\) of G such that each edge needed in \(G'\) is constructed by a part of a piece of such a specific material, the new objective is to minimize the number of necessary pieces of such a specific material to construct all edges in \(G'\). For this new objective defined, we obtain three results: (1) We present a \(\frac{3}{2}\)-approximation algorithm to construct a spanning tree of G; (2) We design a \(\frac{3}{2}\)-approximation algorithm to construct a single-source shortest paths tree of G; (3) We provide a 4-approximation algorithms to construct a metric Steiner tree of G.     

Representations of Currents Taking Values in a Totally Disconnected Group

Let \(G={\mathcal{A}ut(\mathcal{T})}\) be the group of all automorphisms of a homogeneous tree \(\mathcal{T}\) of degree q?+?1?≥?3 and (X, m) a compact metrizable measure space with a probability measure m. We assume that μ has no atoms. The group \(\mathcal{G}={\mathcal{A}ut(\mathcal{T})}^X=G^X\) of bounded measurable currents is the completion of the group of step functions \(f:X\to{\mathcal{A}ut(\mathcal{T})}\) with respect to a suitable metric. Continuos functions form a dense subgroup of \(\mathcal{G}\). Following the ideas of I.M. Gelfand, M.I. Graev and A.M. Vershik we shall construct an irreducible family of representations of \(\mathcal{G}\). The existence of such representations depends deeply from the nonvanisching of the first cohomology group \(H^1({\mathcal{A}ut(\mathcal{T})},\pi)\) for a suitable infinite dimensional π.     

A characterization of the desarguesian and the Figueroa planes of order $$q^{3}$$

Let \(\Pi \) be a plane of order \(q^{3}\), \(q>2\), admitting \(G\cong PGL(3,q)\) as a collineation group. By Dempwolff (Geometriae Dedicata 18:101–112, 1985) the plane \(\Pi \) contains a G-invariant subplane \(\pi _{0}\) isomorphic to PG(2, q) on which G acts 2-transitively. In this paper it is shown that, if the homologies of \(\pi _{0}\) contained in G extend to \(\Pi \) then \(\Pi \) is either the desarguesian or the Figueroa plane.     

On Riesz Transforms Characterization of <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> Spaces Associated with Some Schrödinger Operators

Let \(\mathcal Lf(x)=-\Delta f (x)+V(x)f(x)\), V?≥?0, \(V\in L^1_{loc}(\mathbb R^d)\), be a non-negative self-adjoint Schrödinger operator on \(\mathbb R^d\). We say that an L ¹-function f is an element of the Hardy space \(H^1_{\mathcal L}\) if the maximal function

$ \mathcal M_{\mathcal L} f(x)=\sup\limits_{t>0}|e^{-t\mathcal L} f(x)| $

belongs to \(L^1(\mathbb R^d)\). We prove that under certain assumptions on V the space \(H^1_{\mathcal L}\) is also characterized by the Riesz transforms \(R_j=\frac{\partial}{\partial x_j}\mathcal L^{-1\slash 2}\), j?=?1,...,d, associated with \(\mathcal L\). As an example of such a potential V one can take any V?≥?0, \(V\in L^1_{loc}\), in one dimension.

     

Numerical semigroups whose fractions are of maximal embedding dimension

Each saturated (resp., Arf) numerical semigroup S has the property that each of its fractions \(\frac{S}{k}\) is saturated (resp., Arf), but the property of being of maximal embedding dimension (MED) is not stable under formation of fractions. If S is a numerical semigroup, then S is MED (resp., Arf; resp., saturated) if and only if, for each 2≤k∈?, \(S = \frac{T}{k}\) for infinitely many MED (resp., Arf; resp., saturated) numerical semigroups T. Let \(\mathcal{A}\) (resp., \(\mathcal{F}\)) be the class of Arf numerical semigroups (resp., of numerical semigroups each of whose fractions is of maximal embedding dimension). Then there exists an infinite strictly ascending chain \(\mathcal{A} =\mathcal{C}_{1} \subset\mathcal{C}_{2} \subset\mathcal{C}_{3}\subset \,\cdots\, \subset\mathcal{F}\), where, like \(\mathcal{A}\) and \(\mathcal{F}\), each \(\mathcal{C}_{n}\) is stable under the formation of fractions.     

Symmetric Pairs and Self-Adjoint Extensions of Operators,with Applications to Energy Networks

We provide a streamlined construction of the Friedrichs extension of a densely-defined self-adjoint and semibounded operator A on a Hilbert space \(\mathcal {H}\), by means of a symmetric pair of operators. A symmetric pair is comprised of densely defined operators \(J: \mathcal {H}_1 \rightarrow \mathcal {H}_2\) and \(K: \mathcal {H}_2 \rightarrow \mathcal {H}_1\) which are compatible in a certain sense. With the appropriate definitions of \(\mathcal {H}_1\) and J in terms of A and \(\mathcal {H}\), we show that \((\textit{JJ}^\star )^{-1}\) is the Friedrichs extension of A. Furthermore, we use related ideas (including the notion of unbounded containment) to construct a generalization of the construction of the Krein extension of A as laid out in a previous paper of the authors. These results are applied to the study of the graph Laplacian on infinite networks, in relation to the Hilbert spaces \(\ell ^2(G)\) and \(\mathcal {H}_{\mathcal {E}}\) (the energy space).