Search

Let $T$ be a theory. If $T$ eliminates $\exists^\infty$, it need not follow that $T^{eq}$ eliminates $\exists^\infty$, as shown by the example of the $p$-adics. We give a criterion to determine whether $T^{eq}$ eliminates $\exists^\infty$. Specifically, we show that $T^{eq}$ eliminates $\exists^\infty$ if and only if $\exists^\infty$ is eliminated on all interpretable sets of "unary imaginaries." This criterion can be applied in cases where a full description of $T^{eq}$ is unknown. As an application, we show that $T^{eq}$ eliminates $\exists^\infty$ when $T$ is a C-minimal expansion of ACVF., Comment: 6 pages

An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of $d/2$ in dimension $d$, achieved by the "standard terminal simplices" and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino \& Schymura (2017) that the $d$-th covering minimum of the standard terminal $n$-simplex equals $d/2$, for every $n>d$. We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger's formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and we give strong evidence for its validity in arbitrary dimension., 44 pages, 7 figures

We show that certain type of tree forcings, including Sacks forcing, increases the covering of the strong measure zero ideal $\mathcal{SN}$. As a consequence, in Sacks model, such covering number is equal to the size of the continuum, which indicates that this covering number is consistently larger than any other classical cardinal invariant of the continuum. Even more, Sacks forcing can be used to force that $\mathrm{non}(\mathcal{SN}), Comment: 10 pages, 3 figures

We study the definability of ultrafilter bases on $$\omega $$ in the sense of descriptive set theory. As a main result we show that there is no coanalytic base for a Ramsey ultrafilter, while in L we can construct $$\Pi ^1_1$$ P-point and Q-point bases. We also show that the existence of a $${\varvec{\Delta }}^1_{n+1}$$ ultrafilter is equivalent to that of a $${\varvec{\Pi }}^1_n$$ ultrafilter base, for $$n \in \omega $$ . Moreover we introduce a Borel version of the classical ultrafilter number and make some observations.

Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal'perin in the 1970s, who presented a simple combinatorial characterization of the class. The multi-dimensional case has been studied by Toom and others, but no such characterization has been found. We prove a similar characterization for those one-dimensional monotonic cellular automata that are eroders even in the presence of random noise., Comment: 32 pages, 9 figures

We introduce a generalization of stationary set reflection which we call "filter reflection", and show it is compatible with the axiom of constructibility as well as with strong forcing axioms. We prove the independence of filter reflection from ZFC, and present applications of filter reflection to the study of canonical equivalence relations of the higher Cantor and Baire spaces.

In this paper, we study the Sobolev extension property of Lp-quasidisks which are the generalizations of classical quasidisks. After that, we also find some applications of this property.

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state $$\rho \in \mathbb {C}^{d\times d}$$ and the goal is to distinguish (with high probability) whether $$\rho $$ ’s spectrum satisfies some property $${\mathcal {P}}$$ or whether it is at least $$\epsilon $$ -far in $$\ell _1$$ -distance from satisfying $${\mathcal {P}}$$ . This problem was promoted in the survey of Montanaro and de Wolf (A survey of quantum property testing. Technical report, arXiv:1310.2035 , 2013) under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Unlike property testing probability distributions—where one generally hopes for algorithms with sample complexity that is sublinear in the domain size—here the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the (frequently rediscovered) “empirical Young diagram (EYD) algorithm” (Alicki et al. in J Math Phys 29(5):1158–1162, 1988; Keyl and Werner in Phys Rev A 64(5):052311, 2011; Hayashi and Matsumoto in Phys Rev A 66(2):022311, 2002; Christandl and Mitchison in Commun. Math. Phys. 261(3):789–797, 2006) can estimate the spectrum of any mixed state up to $$\epsilon $$ -accuracy using only $${\widetilde{O}}(d^2/\epsilon ^2)$$ copies. In this work, we show that given a mixed state $$\rho \in \mathbb {C}^{d \times d}$$ : Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov’s algebra of polynomial functions on Young diagrams.

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.

When does the complex product of a given number of subsets of a group generate the same subgroup as their union? We answer this question in a more general form by introducing HS-stability and characterising the HS-stable involution subsemigroup generated by a subset of a given involution semigroup. We study HS-stability for the special cases of regular ${}^{*}$-semigroups and commutative involution semigroups., Comment: 14 pages

Given a graph $H$, the extremal number $\mathrm{ex}(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K'_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$, we show that $\mathrm{ex}(n, K'_{s,t}) = O(n^{3/2 - \frac{1}{2s}})$. This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$. Second, for any integers $s, k \geq 1$, we show that $\mathrm{ex}(n, L) = \Theta(n^{1 + \frac{s}{sk+1}})$ for a particular graph $L$ depending on $s$ and $k$, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erd\H{o}s and Simonovits, which asserts that every rational number $r \in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H) = \Theta(n^r)$ for some appropriate graph $H$, giving infinitely many new realisable exponents and implying that $1 + 1/k$ is a limit point of realisable exponents for all $k \geq 1$. Writing $H^k$ for the $k$-subdivision of a graph $H$, this result also implies that for any bipartite graph $H$ and any $k$, there exists $\delta > 0$ such that $\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - \delta})$, partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $\mathrm{ex}(n, H) = o(n^{2 - 1/r})$., Comment: 21 pages

We consider the following question: If a simplicial complex $$\Gamma $$ has d-homology, then does the corresponding d-cycle always induce cycles of smaller dimension that are not boundaries? We provide an answer to this question in a fixed dimension. We use the breaking of homology to show the subadditivity property for the maximal degrees of syzygies of monomial ideals in a fixed homological degree.

We extend the facial weak order from finite Coxeter groups to central hyperplane arrangements. The facial weak order extends the poset of regions of a hyperplane arrangement to all its faces. We provide four non-trivially equivalent definitions of the facial weak order of a central arrangement: (1) by exploiting the fact that the faces are intervals in the poset of regions, (2) by describing its cover relations, (3) using covectors of the corresponding oriented matroid, and (4) using certain sets of normal vectors closely related to the geometry of the corresponding zonotope. Using these equivalent descriptions, we show that when the poset of regions is a lattice, the facial weak order is a lattice. In the case of simplicial arrangements, we further show that this lattice is semidistributive and give a description of its join-irreducible elements. Finally, we determine the homotopy type of all intervals in the facial weak order., 34 pages, 12 figures

For a graph G, $$L(G)^2$$ L ( G ) 2 is the square of the line graph of G – that is, vertices of $$L(G)^2$$ L ( G ) 2 are edges of G and two edges $$e,f\in E(G)$$ e , f ∈ E ( G ) are adjacent in $$L(G)^2$$ L ( G ) 2 if at least one vertex of e is adjacent to a vertex of f and $$e\ne f$$ e ≠ f . The strong chromatic index of G, denoted by $$s'(G)$$ s ′ ( G ) , is the chromatic number of $$L(G)^2$$ L ( G ) 2 . A strong clique in G is a clique in $$L(G)^2$$ L ( G ) 2 . Finding a bound for the maximum size of a strong clique in a graph with given maximum degree is a problem connected to a famous conjecture of Erdős and Nešetřil concerning strong chromatic index of graphs. In this note we prove that a size of a strong clique in a claw-free graph with maximum degree $$\varDelta $$ Δ is at most $$\varDelta ^2 + \frac{1}{2}\varDelta $$ Δ 2 + 1 2 Δ . This result improves the only known result $$1.125\varDelta ^2+\varDelta $$ 1.125 Δ 2 + Δ , which is a bound for the strong chromatic index of claw-free graphs.

For two integers $$k>0$$ k > 0 and $$\ell $$ ℓ , a graph $$G=(V,E)$$ G = ( V , E ) is called $$(k,\ell )$$ ( k , ℓ ) -tight if $$|E|=k|V|-\ell $$ | E | = k | V | - ℓ and $$i_G(X)\le k|X|-\ell $$ i G ( X ) ≤ k | X | - ℓ for each $$X\subseteq V$$ X ⊆ V for which $$i_G(X)\ge 1$$ i G ( X ) ≥ 1 , where $$i_G(X)$$ i G ( X ) denotes the number of induced edges by X. G is called $$(k,\ell )$$ ( k , ℓ ) -redundant if $$G-e$$ G - e has a spanning $$(k,\ell )$$ ( k , ℓ ) -tight subgraph for all $$e\in E$$ e ∈ E . We consider the following augmentation problem. Given a graph $$G=(V,E)$$ G = ( V , E ) that has a $$(k,\ell )$$ ( k , ℓ ) -tight spanning subgraph, find a graph $$H=(V,F)$$ H = ( V , F ) with the minimum number of edges, such that $$G\cup H$$ G ∪ H is $$(k,\ell )$$ ( k , ℓ ) -redundant. We give a polynomial algorithm and a min-max theorem for this augmentation problem when the input is $$(k,\ell )$$ ( k , ℓ ) -tight. For general inputs, we give a polynomial algorithm when $$k\ge \ell $$ k ≥ ℓ and show the NP-hardness of the problem when $$k k < ℓ . Since $$(k,\ell )$$ ( k , ℓ ) -tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of rigid frameworks redundantly rigid by adding a smallest set of new bars.

We calculate the spectrum of the diagram for each finite 3-transposition group. Such graphs with a given minimum eigenvalue have occurred in the context of compact Griess subalgebras of vertex operator algebras.

We study the notion of formal self duality in finite abelian groups. Formal duality in finite abelian groups has been proposed by Cohn, Kumar, Reiher and Schürmann. In this paper we give a precise definition of formally self dual sets and discuss results from the literature in this perspective. Also, we discuss the connection to formally dual codes. We prove that formally self dual sets can be reduced to primitive formally self dual sets similar to a previously known result on general formally dual sets. Furthermore, we describe several properties of formally self dual sets. Also, some new examples of formally self dual sets are presented within this paper. Lastly, we study formally self dual sets of the form $\{(x,F(x)) \ : \ x\in {\mathbb {F}}_{2^{n}}\}$ { ( x , F ( x ) ) : x ∈ F 2 n } where F is a vectorial Boolean function mapping ${\mathbb {F}}_{2^{n}}$ F 2 n to ${\mathbb {F}}_{2^{n}}$ F 2 n .

The critical relations are the building blocks of the relational clone of a relational structure with respect to the relational operations intersection and direct product. In this paper we describe the critical relations of crowns. As a consequence, we obtain that the subpower membership problem for any crown is polynomial-time solvable.

In their study of the equivariant K-theory of the generalized flag varieties G/P, where G is a complex semisimple Lie group, and P is a parabolic subgroup of G, Lenart and Postnikov introduced a combinatorial tool, called the alcove path model. It provides a model for the highest weight crystals with dominant integral highest weights, generalizing the model by semistandard Young tableaux. In this paper, we prove a simple and explicit formula describing the crystal isomorphism between the alcove path model and the Gelfand–Tsetlin pattern model for type A.

In 2011, Nathanson proposed several questions on minimal complements in a group or a semigroup. The notion of minimal complements and being a minimal complement leads to the notion of co-minimal pairs which was considered in a prior work of the authors. In this article, we study which type of subsets in the integers and free abelian groups of higher rank can be a part of a co-minimal pair. We show that a majority of lacunary sequences have this property. From the conditions established, one can show that any infinite subset of any finitely generated abelian group has uncountably many subsets which is a part of a co-minimal pair. Further, the uncountable collection of sets can be chosen so that they satisfy certain algebraic properties.

In strategic situations, agents base actions on knowledge and beliefs. This includes knowledge about others’ strategies and preferences over strategy profiles, but also about other external factors. Bernheim and Pearce in 1984 independently defined the game theoretic solution concept of rationalizability, which is built on the premise that rational agents will only take actions that are the best response to some situation that they consider possible. This accounts for other agents’ rationality as well, limiting the strategies to which a particular agent must respond, enabling further elimination until the strategies stabilize. We seek to generalize rationalizability to account not only for actions, but knowledge of the world as well. This will enable us to examine the interplay between action based and knowledge based rationality. We give an account of what it means for an action to be rational relative to a particular state of affairs, and in turn relative to a state of knowledge. We present a class of games, Epistemic Messaging Games (EMG), with a communication stage that clarifies the epistemic state among the players prior to the players’ actions. We use a history based model, which frames individual knowledge in terms of local projections of a global history. With this framework, we give an account of rationalizability for subclasses of EMG.

This paper studies Menon–Sury’s identity in a general case, i.e., the Menon–Sury’s identity involving Dirichlet characters in residually finite Dedekind domains. By using the filtration of the ring $${\mathfrak {D}}/{\mathfrak {n}}$$ and its unit group $$U({\mathfrak {D}}/{\mathfrak {n}})$$ , we explicitly compute the following two summations: $$\begin{aligned} \sum _{\begin{array}{c} a\in U({\mathfrak {D}}/{\mathfrak {n}}) \\ b_1, \ldots , b_r\in {\mathfrak {D}}/{\mathfrak {n}} \end{array}} N(\langle a-1,b_1, b_2, \ldots , b_r \rangle +{\mathfrak {n}})\chi (a) \end{aligned}$$ and $$\begin{aligned} \sum _{\begin{array}{c} a_{1},\ldots , a_{s}\in U({\mathfrak {D}}/{\mathfrak {n}}) \\ b_1, \ldots , b_r\in {\mathfrak {D}}/{\mathfrak {n}} \end{array}} N(\langle a_{1}-1,\ldots , a_{s}-1,b_1, b_2, \ldots , b_r \rangle +{\mathfrak {n}})\chi _{1}(a_1) \cdots \chi _{s}(a_s), \end{aligned}$$ where $${\mathfrak {D}}$$ is a residually finite Dedekind domain and $${\mathfrak {n}}$$ is a nonzero ideal of $${\mathfrak {D}}$$ , $$N({\mathfrak {n}})$$ is the cardinality of quotient ring $${\mathfrak {D}}/{\mathfrak {n}}$$ , $$\chi _{i}~(1\le i\le s)$$ are Dirichlet characters mod $${\mathfrak {n}}$$ with conductor $${\mathfrak {d}}_i$$ .

We study the reachability problem for queue automata and lossy queue automata. Concretely, we consider the set of queue contents which are forwards resp. backwards reachable from a given set of queue contents. Here, we prove the preservation of regularity if the queue automaton loops through some special sets of transformation sequences. This is a generalization of the results by Boigelot et al. and Abdulla et al. regarding queue automata looping through a single sequence of transformations. We also prove that our construction is possible in polynomial time.

We consider three types of set-systems that have interesting applications in algebraic combinatorics and representation theory: maximal collections of the so-called strongly, weakly, and chord separated subsets of a set $$[n]=\{1,2,\ldots ,n\}$$ . These collections are known to admit nice geometric interpretations; namely, they are, respectively, in bijection with rhombus tilings on the zonogon Z(n, 2), combined tilings on Z(n, 2), and fine zonotopal tilings (or “cubillages”) on the 3-dimensional zonotope Z(n, 3). We describe interrelations between these three types of set-systems in $$2^{[n]}$$ , working in terms of their geometric models. In particular, we characterize the sets of rhombus and combined tilings properly embeddable in a fixed 3-dimensional cubillage and give efficient methods of extending a given rhombus or combined tiling to a cubillage, etc.

One way to study the Kronecker coefficients is to focus on the Kronecker cone, which is generated by the triples of partitions corresponding to non-zero Kronecker coefficients. In this article we are interested in producing particular faces of this cone, formed of stable triples (a notion defined by J. Stembridge in 2014), using some geometric notions—principally those of dominant and well-covering pairs—and results of N. Ressayre. This extends a result obtained independently by L. Manivel and E. Vallejo in 2014 or 2015, expressed in terms of additive matrices. To illustrate the fact that it allows to produce quite a few new faces of the Kronecker cone, we give at the end of the article details about what our results yield for “small dimensions”.

COVID19 is the most impactful pandemic of recent times worldwide. It is a highly infectious disease that is caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2 virus), To date there is specific drug nor vaccination against COVID19. Therefor the need for novel and pioneering anti-COVID19 is of paramount importance. In this direction, computer-aided drug design constitutes a very promising antiviral approach for the discovery and analysis of drugs and molecules with biological activity against SARS-CoV2. In silico modelling takes advantage of the massive amounts of biological and chemical data available on the nature of the interactions between the targeted systems and molecules, as well as the rapid progress of computational tools and software. Herein, we describe the potential of the merging of mathematical modelling, artificial intelligence and learning techniques into seamless computational pipelines for the rapid and efficient discovery and design of potent anti- SARS-CoV-2 modulators.

Formalism in the philosophy of mathematics has taken a variety of forms and has been advocated for widely divergent reasons. In Sects. 1 and 2, I briefly introduce the major formalist doctrines of the late nineteenth and early twentieth centuries. These are what I call empirico-semantic formalism (advocated by Heine), game formalism (advocated by Thomae) and instrumental formalism (advocated by Hilbert). After describing these views, I note some basic points of similarity and difference between them. In the remainder of the paper, I turn my attention to Hilbert’s instrumental formalism. My primary aim there will be to develop its formalist elements more fully. These are, in the main, (i) its rejection of the axiom-centric focus of traditional model-construction approaches to consistency problems, (ii) its departure from the traditional understanding of the basic nature of proof and (iii) its distinctively descriptive or observational orientation with regard to the consistency problem for arithmetic. More specifically, I will highlight what I see as the salient points of connection between Hilbert’s formalist attitude and his finitist standard for the consistency proof for arithmetic. I will also note what I see as a significant tension between Hilbert’s observational approach to the consistency problem for arithmetic and his expressed hope that his solution of that problem would dispense with certain epistemological concerns regarding arithmetic once and for all.

This is a follow-up paper of arXiv:1805.00115, where rational curves in surfaces that satisfy general positioned point and cross-ratio conditions were enumerated. A suitable correspondence theorem provided in arXiv:1509.07453 allowed us to use tropical geometry, and, in particular, a degeneration technique called floor diagrams. This correspondence theorem also holds in higher dimension. In the current paper, we introduce so-called cross-ratio floor diagrams and show that they allow us to determine the number of rational space curves that satisfy general positioned point and cross-ratio conditions. Moreover, graphical contributions are introduced which provide a novel and structured way of understanding multiplicities of floor decomposed curves in $\mathbb{R}^3$. Additionally, so-called condition flows on a tropical curve are used to reflect how conditions imposed on a tropical curve yield different types of edges. This concept is applicable in arbitrary dimension., 36 pages, 15 figures; fixed minor issues, added references

Motivated by the works on truncated theta series of Andrews–Merca and Guo–Zeng, the authors of this paper investigated some Hecke–Rogers type double series in their earlier paper. As a continuation of their study, in this paper, a further investigation on double series will be presented.

Recently, Mc Laughlin proved some results on vanishing coefficients in the series expansions of certain infinite q-products for arithmetic progressions modulo 5, modulo 7 and modulo 11 by grouping the results into several families. In this paper, we prove some new results on vanishing coefficients for arithmetic progressions modulo 7, which are not listed by Mc Laughlin. For example, we prove that if $$t \in \{1,2,3\}$$ and the sequence $$\{A_n\}$$ is defined by $$\sum _{n=0}^{\infty }A_nq^n := (-q^t,-q^{7-t};q^7)_{\infty }(q^{7-2t},q^{7+2t};q^{14})^3_{\infty },$$ then $$A_{7n+4t}=A_{7n+6t^2+4t}=0$$ for all n. Also, we prove four families of results with negative signs for arithmetic progressions modulo 7 classified by Mc Laughlin.

We study several special functions in Ramanujan’s generalized modular equation with signature 3. Some sharp inequalities for these functions, including the estimates for the solution of Ramanujan’s generalized modular equation with signature 3 and triplication inequality for the generalized Grotzsch ring function with two parameters, are derived.

The algebraic monoid structure of an incidence algebra is investigated. We show that the multiplicative structure alone determines the algebra automorphisms of the incidence algebra. We present a formula that expresses the complexity of the incidence monoid with respect to the two sided action of its maximal torus in terms of the zeta polynomial of the poset. In addition, we characterize the finite (connected) posets whose incidence monoids have complexity $\leq 1$. Finally, we determine the covering relations of the adherence order on the incidence monoid of a star poset., Comment: The final version of this article will appear in the Semigroup Forum

Let $$P(x)=a_0x^d+a_1x^{d-1}+\cdots +a_d \in {{\mathbb {Q}}}[x]$$ be a polynomial of degree $$d \ge 2$$ , and let $$x_n$$ , $$n=0,1,2,\ldots $$ , be a sequence of integers satisfying $$x_{n+1}=P(x_n)$$ for $$n \ge 0$$ and $$x_n \rightarrow \infty $$ as $$n \rightarrow \infty $$ . Then, by a recent result of Wagner and Ziegler, $$\alpha =\lim _{n\rightarrow \infty } x_n^{d^{-n}}>1$$ is either an integer or an irrational number, and $$x_n$$ is approximately $$a_0^{-1/(d-1)} \alpha ^{d^n}-a_1/(da_0)$$ . Under assumption $$a_0^{1/(d-1)} \in {{\mathbb {Q}}}$$ on the leading coefficient $$a_0$$ of P, we completely characterize all the cases when the limit $$\alpha $$ is an algebraic number. Our results imply that $$\alpha $$ can be an integer, a quadratic Pisot unit with $$\alpha ^{-1}$$ being its conjugate over $${{\mathbb {Q}}}$$ , or a transcendental number. In most cases $$\alpha $$ is transcendental. For each $$d \ge 2$$ all the polynomials P of degree d for which $$\alpha $$ is an integer or a quadratic Pisot unit are described explicitly. The main theorem implies that several constants related to sequences that appear in a paper of Aho and Sloane and in the online Encyclopedia of Integer Sequences are transcendental.

A set S of vertices of a connected graph G is a doubly connected dominating set (DCDS) if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and $$V-S$$ are connected. The doubly connected domination number $$\gamma _{cc}(G)$$ is the minimum size of such a set. The doubly connected domination subdivision number $$\hbox {sd}_{\gamma _{cc}}(G)$$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) to increase the doubly connected domination number. It was conjectured (Karami et al. in Mat Vesnic 64:232–239, 2012) that the doubly connected domination subdivision number of a connected planar graph is at most two. In this paper, we disprove this conjecture by showing that the doubly connected domination subdivision number of the regular icosahedron graph is three.

The graph Cheeger constant and Cheeger inequalities are generalized to the case of hypergraphs whose edges have the same cardinality. In particular, it is shown that the second largest eigenvalue of the generalized normalized Laplacian is bounded both above and below by the generalized Cheeger constant, and the corresponding eigenfunctions can be used to approximate the Cheeger cut.

The problem of classifying linear systems of conics in projective planes dates back at least to Jordan, who classified pencils (one-dimensional systems) of conics over $${\mathbb {C}}$$ C and $$\mathbb {R}$$ R in 1906–1907. The analogous problem for finite fields $$\mathbb {F}_q$$ F q with q odd was solved by Dickson in 1908. In 1914, Wilson attempted to classify nets (two-dimensional systems) of conics over finite fields of odd characteristic, but his classification was incomplete and contained some inaccuracies. In a recent article, we completed Wilson’s classification (for q odd) of nets of rank one, namely those containing a repeated line. The aim of the present paper is to introduce and calculate certain combinatorial invariants of these nets, which we expect will be of use in various applications. Our approach is geometric in the sense that we view a net of rank one as a plane in $$\mathrm {PG}(5,q)$$ PG ( 5 , q ) , q odd, that meets the quadric Veronesean in at least one point; two such nets are then equivalent if and only if the corresponding planes belong to the same orbit under the induced action of $$\mathrm {PGL}(3,q)$$ PGL ( 3 , q ) viewed as a subgroup of $$\mathrm {PGL}(6,q)$$ PGL ( 6 , q ) . Since q is odd, the orbits of lines in $$\mathrm {PG}(5,q)$$ PG ( 5 , q ) under this action correspond to the aforementioned pencils of conics in $$\mathrm {PG}(2,q)$$ PG ( 2 , q ) . The main contribution of this paper is to determine the line-orbit distribution of a plane $$\pi $$ π corresponding to a net of rank one, namely, the number of lines in $$\pi $$ π belonging to each line orbit. It turns out that this list of invariants completely determines the orbit of $$\pi $$ π , and we will use this fact in forthcoming work to develop an efficient algorithm for calculating the orbit of a given net of rank one. As a more immediate application, we also determine the stabilisers of nets of rank one in $$\mathrm {PGL}(3,q)$$ PGL ( 3 , q ) , and hence the orbit sizes.

In this paper we study the variety of order Hilbert algebras, which is the equivalent algebraic semantics of the order implicational calculus of Bull (J Symb Logic, 29:33–34, 1964).

A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete problem. In this paper, we present two methods to show Hamilton-connectivity in graphs. The first method uses the vertex connectivity and Hamiltoniancity of graphs, and, the second is the definition-based constructive method which constructs Hamiltonian paths between every pair of vertices. By employing these proof techniques, we show that the line graphs of the generalized Petersen, anti-prism and wheel graphs are Hamilton-connected. Combining it with some existing results, it shows that some of these families of Hamilton-connected line graphs have their underlying graph families non-Hamilton-connected. This, in turn, shows that the underlying graph of a Hamilton-connected line graph is not necessarily Hamilton-connected. As side results, the detour index being also an NP-complete problem, has been calculated for the families of Hamilton-connected line graphs. Finally, by computer we generate all the Hamilton-connected graphs on $$\le 7$$ vertices and all the Hamilton-laceable graphs on $$\le 10$$ vertices. Our research contributes towards our proposed conjecture that almost all graphs are Hamilton-connected.

We study games of length ω2 with moves in ℕ and Borel payoff. These are, e.g., games in which two players alternate turns playing digits to produce a real number in [0, 1] infinitely many times, after which the winner is decided in terms of the sequence belonging to a Borel set in the product space [0,1]ℕ. The main theorem is that Borel games of length ω2 are determined if, and only if, for every countable ordinal α, there is a fine-structural, countably iterable model of Zermelo set theory with α-many iterated powersets above a limit of Woodin cardinals.

The aim of this article is to obtain a better understanding and classification of strictly ergodic topological dynamical systems with (measurable) discrete spectrum. To that end, we first determine when an isomorphic maximal equicontinuous factor map of a minimal topological dynamical system has trivial (one point) fibers. In other words, we characterize when minimal mean equicontinuous systems are almost automorphic. Furthermore, we investigate another natural subclass of mean equicontinuous systems, so-called diam-mean equicontinuous systems, and show that a minimal system is diam-mean equicontinuous if and only if the maximal equicontinuous factor is regular (the points with trivial fibers have full Haar measure). Combined with previous results in the field, this provides a natural characterization for every step of a natural hierarchy for strictly ergodic topological models of ergodic systems with discrete spectrum. We also construct an example of a transitive almost diam-mean equicontinuous system with positive topological entropy, and we give a partial answer to a question of Furstenberg related to multiple recurrence.

We continue the study of Rosenthal families initiated by Damian Sobota. We show that every Rosenthal filter is the intersection of a finite family of ultrafilters that are pairwise incomparable in the Rudin-Keisler partial ordering of ultrafilters. We introduce a property of filters, called an $$r$$ -filter, properly between a selective filter and a $$p$$ -filter. We prove that every $$r$$ -ultrafilter is a Rosenthal family. We prove that it is consistent with ZFC to have uncountably many $$r$$ -ultrafilters such that any intersection of finitely many of them is a Rosenthal filter.

Let $\Gamma$ be an amenable countable discrete group. Fix an ergodic free nonsingular action of $\Gamma$ on a nonatomic standard probability space. Let $G$ be a compactly generated locally compact second countable group such that the closure of the group of inner automorphisms of $G$ is compact in the natural topology. It is shown that there exists a {\it bounded} ergodic $G$-valued cocycle of $\Gamma$.

The tetravalent modal logic ( $${\mathcal {TML}}$$ ) is one of the two logics defined by Font and Rius (J Symb Log 65(2):481–518, 2000) (the other is the normal tetravalent modal logic $${{\mathcal {TML}}}^N$$ ) in connection with Monteiro’s tetravalent modal algebras. These logics are expansions of the well-known Belnap–Dunn’s four-valued logic that combine a many-valued character (tetravalence) with a modal character. In fact, $${\mathcal {TML}}$$ is the logic that preserves degrees of truth with respect to tetravalent modal algebras. As Font and Rius observed, the connection between the logic $${\mathcal {TML}}$$ and the algebras is not so good as in $${{\mathcal {TML}}}^N$$ , but, as a compensation, it has a better proof-theoretic behavior, since it has a strongly adequate Gentzen calculus (see Font and Rius in J Symb Log 65(2):481–518, 2000). In this work, we prove that the sequent calculus given by Font and Rius does not enjoy the cut-elimination property. Then, using a general method proposed by Avron et al. (Log Univ 1:41–69, 2006), we provide a sequent calculus for $${\mathcal {TML}}$$ with the cut-elimination property. Finally, inspired by the latter, we present a natural deduction system, sound and complete with respect to the tetravalent modal logic.

We show that the tree property, stationary reflection and the failure of approachability at $$\kappa ^{++}$$ are consistent with $$\mathfrak {u}(\kappa )= \kappa ^+ < 2^\kappa $$ , where $$\kappa $$ is a singular strong limit cardinal with the countable or uncountable cofinality. As a by-product, we show that if $$\lambda $$ is a regular cardinal, then stationary reflection at $$\lambda ^+$$ is indestructible under all $$\lambda $$ -cc forcings (out of general interest, we also state a related result for the preservation of club stationary reflection).

We show: (1) for every noncomputable c.e. incomplete c-degree, there exists a nonspeedable c-degree incomparable with it; (2) The c-degree of a hypersimple set includes an infinite collection of $$c_1$$ -degrees linearly ordered under $$\le _{c_1}$$ with order type of the integers and consisting entirely of hypersimple sets; (3) there exist two c.e. sets having no c.e. least upper bound in the $$c_1$$ -reducibility ordering; (4) the c.e. $$c_1$$ -degrees are not dense.

In this note, we give a detailed proof of an asymptotic for averages of coefficients of a class of degree three $L$-functions which can be factorized as a product of a degree one and a degree two $L$-functions. We emphasize that we can break the $1/2$-barrier in the error term, and we get an explicit exponent., Comment: 10 pages

We extend the concept of Grobner bases to relative Grobner bases for ideals in and modules over quotient rings of a polynomial ring over a field. We develop a “relative” variant of both Buchberger’s criteria for avoiding reductions to zero and Schreyer’s theorem for a Grobner basis of the syzygy module. As main contribution, we then introduce the novel notion of relative involutive bases and present an algorithm for their explicit construction. Finally, we define the new notion of relatively quasi-stable ideals and exploit it for the algorithmic determination of coordinates in which finite relative Pommaret bases exist.

We provide a new method to compute the Balmer spectra of the bounded derived category and the singularity category of the category algebra of a finite EI category by a decomposition trick due to Stevenson. In particular, we reobtain the result on the singularity category given by Wang under a weaker condition.

We construct examples and families of locally Hermitian ovoids of the generalized quadrangle $$H(3,q^2)$$ . We also obtain a computer classification of all locally Hermitian ovoids of $$H(3,q^2)$$ for $$q \le 4$$ , and compare the obtained classification for $$q=3$$ with the classification of all ovoids of H(3, 9) which is also obtained by computer.