On a problem of Erdős and Moser

A set A of vertices in an r-uniform hypergraph \(\mathcal H\) is covered in \(\mathcal H\) if there is some vertex \(u\not \in A\) such that every edge of the form \(\{u\}\cup B\), \(B\in A^{(r-1)}\) is in \(\mathcal H\). Erd?s and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.     

On a conjecture of differentially 8-uniform power functions

Let \(m \ge 5\) be an odd integer. For \(d=2^m+2^{(m+1)/2}+1\) or \(d=2^{m+1}+3\), Blondeau et al. conjectured that the power function \(F_d=x^d\) over \(\mathrm {GF}(2^{2m})\) is differentially 8-uniform in which all values \(0, \, 2, \, 4,\, 6,\, 8\) appear. In this paper, we confirm this conjecture and compute the differential spectrum of \(F_d\) for both values of d.     

Counterexamples to the B-spline Conjecture for Gabor Frames

The frame set conjecture for B-splines \(B_n\), \(n \ge 2\), states that the frame set is the maximal set that avoids the known obstructions. We show that any hyperbola of the form \(ab=r\), where r is a rational number smaller than one and a and b denote the sampling and modulation rates, respectively, has infinitely many pieces, located around \(b=2,3,\dots \), not belonging to the frame set of the nth order B-spline. This, in turn, disproves the frame set conjecture for B-splines. On the other hand, we uncover a new region belonging to the frame set for B-splines \(B_n\), \(n \ge 2\).     

A new theorem on the prime-counting function

For \(x>0\), let \(\pi (x)\) denote the number of primes not exceeding x. For integers a and \(m>0\), we determine when there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). In particular, we show that, for any integers \(m>2\) and \(a\leqslant \lceil e^{m-1}/(m-1)\rceil \), there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). Consequently, for any integer \(m>4\), there is a positive integer n with \(\pi (mn)=m+n\). We also pose several conjectures for further research; for example, we conjecture that, for each \(m=1,2,3,\ldots \), there is a positive integer n such that \(m+n\) divides \(p_m+p_n\), where \(p_k\) denotes the k-th prime.     

Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

On Star–Wheel Ramsey Numbers

For two given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the least integer r such that for every graph G on r vertices, either G contains a \(G_1\) or \(\overline{G}\) contains a \(G_2\). In this note, we determined the Ramsey number \(R(K_{1,n},W_m)\) for even m with \(n+2\le m\le 2n-2\), where \(W_m\) is the wheel on \(m+1\) vertices, i.e., the graph obtained from a cycle \(C_m\) by adding a vertex v adjacent to all vertices of the \(C_m\).     

Distance Magic Labeling in Complete 4-partite Graphs

Let G be a complete k-partite simple undirected graph with parts of sizes \(p_1\le p_2\cdots \le p_k\). Let \(P_j=\sum _{i=1}^jp_i\) for \(j=1,\ldots ,k\). It is conjectured that G has distance magic labeling if and only if \(\sum _{i=1}^{P_j} (n-i+1)\ge j{{n+1}\atopwithdelims (){2}}/k\) for all \(j=1,\ldots ,k\). The conjecture is proved for \(k=4\), extending earlier results for \(k=2,3\).     

A note on linear Sperner families

In an earlier work we described Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characteristic vectors \(\mathbf {v}\in \{0,1\}^n\) of the complete d uniform set family over the ground set [n]. In particular, it turns out that the standard monomials of the above ideal are ballot monomials. We give here a partial extension of this fact. A set family is a linear Sperner system if the characteristic vectors satisfy a linear equation \(a_1v_1+\cdots +a_nv_n=k\), where the \(a_i\) and k are positive integers. We prove that the lexicographic standard monomials for linear Sperner systems are also ballot monomials, provided that \(0<a_1\le a_2\le \cdots \le a_n\). As an application, we confirm a conjecture of Frankl in the special case of linear Sperner systems.     

On vanishing patterns in <Emphasis Type="Italic">j</Emphasis>-strands of edge ideals

We consider two problems regarding vanishing patterns in the Betti table of edge ideals I over any fixed field. First, we show that the j-strand is connected if \(j=3\) (for \(j=2\) this is easy and known), and give examples where the j-strand is not connected for any \(j>3\). Next, we apply our result on strand connectivity to establish the subadditivity conjecture for edge ideals, \(t_{a+b}(I)\le t_a(I)+t_b(I)\), in case \(b=2,3\) (the case \(b=1\) is known). Here \(t_i(I)\) denote the maximal shifts in the minimal free resolution of S / I over its polynomial algebra.     

On the family of elliptic curves $$\varvec{y^2=x^3-m^2x+p^2}$$

In this paper, we study the torsion subgroup and rank of elliptic curves for the subfamilies of \(E_{m,p} : y^2=x^3-m^2x+p^2\), where m is a positive integer and p is a prime. We prove that for any prime p, the torsion subgroup of \(E_{m,p}(\mathbb {Q})\) is trivial for both the cases {\(m\ge 1\), \(m\not \equiv 0\pmod 3\)} and {\(m\ge 1\), \(m \equiv 0 \pmod 3\), with \(gcd(m,p)=1\)}. We also show that given any odd prime p and for any positive integer m with \(m\not \equiv 0\pmod 3\) and \(m\equiv 2\pmod {32}\), the lower bound for the rank of \(E_{m,p}(\mathbb {Q})\) is 2. Finally, we find curves of rank 9 in this family.     

The distortion dimension of $$\mathbb $$-rank 1 lattices

Let \(X=G/K\) be a symmetric space of noncompact type and rank \(k\ge 2\). We prove that horospheres in X are Lipschitz \((k-2)\)-connected if their centers are not contained in a proper join factor of the spherical building of X at infinity. As a consequence, the distortion dimension of an irreducible \(\mathbb {Q}\)-rank-1 lattice \(\Gamma \) in a linear, semisimple Lie group G of \(\mathbb R\)-rank k is \(k-1\). That is, given \(m< k-1\), a Lipschitz m-sphere S in (a polyhedral complex quasi-isometric to) \(\Gamma \), and a \((m+1)\)-ball B in X (or G) filling S, there is a \((m+1)\)-ball \(B'\) in \(\Gamma \) filling S such that \({{\mathrm{vol}}}B'\sim {{\mathrm{vol}}}B\). In particular, such arithmetic lattices satisfy Euclidean isoperimetric inequalities up to dimension \(k-1\).     

Fredholmness of fringe operators over the bidisk

Let M be an invariant subspace of \(H^2\) over the bidisk. Associated with M, we have the fringe operator \(F^M_z\) on \(M\ominus w M\). For \(A\subset H^2\), let [A] denote the smallest invariant subspace containing A. Assume that \(F^M_z\) is Fredholm. If h is a bounded analytic function on \(\mathbb {D}^2\) satisfying \(h(0,0)\not =0\), then \(F^{[h M]}_z\) is Fredholm and \(\mathrm{ind}\,F^{[h M]}_z=\mathrm{ind}\,F^M_z\).     

The non-abelian tensor square of residually finite groups

Let m, n be positive integers and p a prime. We denote by \(\nu (G)\) an extension of the non-abelian tensor square \(G \otimes G\) by \(G \times G\). We prove that if G is a residually finite group satisfying some non-trivial identity \(f \equiv ~1\) and for every \(x,y \in G\) there exists a p-power \(q=q(x,y)\) such that \([x,y^{\varphi }]^q = 1\), then the derived subgroup \(\nu (G)'\) is locally finite (Theorem A). Moreover, we show that if G is a residually finite group in which for every \(x,y \in G\) there exists a p-power \(q=q(x,y)\) dividing \(p^m\) such that \([x,y^{\varphi }]^q\) is left n-Engel, then the non-abelian tensor square \(G \otimes G\) is locally virtually nilpotent (Theorem B).     

Toy Teichmüller spaces of real dimension 2: the pentagon and the punctured triangle

Let \(f: S\longrightarrow B\) be a non-trivial fibration from a complex projective smooth surface S to a smooth curve B of genus b. Let \(c_f\) the Clifford index of the general fibre F of f. In Barja et al. (Journal für die reine und angewandte Mathematik, 2016) it is proved that the relative irregularity of f, \(q_f=h^{1,0}(S)-b\) is less or equal than or equal to \(g(F)-c_f\). In particular this proves the (modified) Xiao’s conjecture: \(q_f\le \frac{g(F)}{2} +1\) for fibrations of general Clifford index. In this short note we assume that the general fiber of f is a plane curve of degree \(d\ge 5\) and we prove that \(q_f\le g(F)-c_f-1\). In particular we obtain the conjecture for families of quintic plane curves. This theorem is implied for the following result on infinitesimal deformations: let F a smooth plane curve of degree \(d\ge 5\) and let \(\xi \) be an infinitesimal deformation of F preserving the planarity of the curve. Then the rank of the cup-product map \(H^0(F,\omega _F) {\overset{ \cdot \xi }{\longrightarrow }} H^1(F,O_F)\) is at least \(d-3\). We also show that this bound is sharp.     

Sets of minimal distances and characterizations of class groups of Krull monoids

Let H be a Krull monoid with finite class group G such that every class contains a prime divisor. Then every non-unit \(a \in H\) can be written as a finite product of atoms, say \(a=u_1 \cdot \ldots \cdot u_k\). The set \(\mathsf L (a)\) of all possible factorization lengths k is called the set of lengths of a. There is a constant \(M \in \mathbb N\) such that all sets of lengths are almost arithmetical multiprogressions with bound M and with difference \(d \in \Delta ^* (H)\), where \(\Delta ^* (H)\) denotes the set of minimal distances of H. We study the structure of \(\Delta ^* (H)\) and establish a characterization when \(\Delta ^*(H)\) is an interval. The system \(\mathcal L (H) = \{ \mathsf L (a) \mid a \in H \}\) of all sets of lengths depends only on the class group G, and a standing conjecture states that conversely the system \(\mathcal L (H)\) is characteristic for the class group. We confirm this conjecture (among others) if the class group is isomorphic to \(C_n^r\) with \(r,n \in \mathbb N\) and \(\Delta ^*(H)\) is not an interval.     

Regulating Hartshorne’s connectedness theorem

The tensor square conjecture states that for \(n \ge 10\), there is an irreducible representation V of the symmetric group \(S_n\) such that \(V \otimes V\) contains every irreducible representation of \(S_n\). Our main result is that for large enough n, there exists an irreducible representation V such that \(V^{\otimes 4}\) contains every irreducible representation. We also show that tensor squares of certain irreducible representations contain \((1-o(1))\)-fraction of irreducible representations with respect to two natural probability distributions. Our main tool is the semigroup property, which allows us to break partitions down into smaller ones.     

Newforms with rational coefficients

We consider the set of classical newforms with rational coefficients and no complex multiplication. We study the distribution of quadratic twist-classes of these forms with respect to weight k and minimal level N. We conjecture that for each weight \(k \ge 6\), there are only finitely many classes. In large weights, we make this conjecture effective: in weights \(18 \le k \le 24\), all classes have \(N \le 30\); in weights \(26 \le k \le 50\), all classes have \(N \in \{2,6\}\); and in weights \(k \ge 52\), there are no classes at all. We study some of the newforms appearing on our conjecturally complete list in more detail, especially in the cases \(N=2\), 3, 4, 6, and 8, where formulas can be kept nearly as simple as those for the classical case \(N=1\).     

Triviality of Iwasawa module associated to some abelian fields of prime conductors

Let p be an odd prime number and \(\ell \) an odd prime number dividing \(p-1\). We denote by \(F=F_{p,\ell }\) the real abelian field of conductor p and degree \(\ell \), and by \(h_F\) the class number of F. For a prime number \(r \ne p,\,\ell \), let \(F_{\infty }\) be the cyclotomic \(\mathbb {Z}_r\)-extension over F, and \(M_{\infty }/F_{\infty }\) the maximal pro-r abelian extension unramified outside r. We prove that \(M_{\infty }\) coincides with \(F_{\infty }\) and consequently \(h_F\) is not divisible by r when r is a primitive root modulo \(\ell \) and r is smaller than an explicit constant depending on p.     

On eigenvalues of Seidel matrices and Haemers’ conjecture

For a graph G, let S(G) be the Seidel matrix of G and \({\theta }_1(G),\ldots ,{\theta }_n(G)\) be the eigenvalues of S(G). The Seidel energy of G is defined as \(|{\theta }_1(G)|+\cdots +|{\theta }_n(G)|\). Willem Haemers conjectured that the Seidel energy of any graph with n vertices is at least \(2n-2\), the Seidel energy of the complete graph with n vertices. Motivated by this conjecture, we prove that for any \(\alpha \) with \(0<\alpha <2,|{\theta }_1(G)|^\alpha +\cdots +|{\theta }_n(G)|^\alpha \geqslant (n-1)^\alpha +n-1\) if and only if \(|\hbox {det}\,S(G)|\geqslant n-1\). This, in particular, implies the Haemers’ conjecture for all graphs G with \(|\hbox {det}\,S(G)|\geqslant n-1\). A computation on the fraction of graphs with \(|\hbox {det}\,S(G)|<n-1\) is reported. Motivated by that, we conjecture that almost all graphs G of order n satisfy \(|\hbox {det}\,S(G)|\geqslant n-1\). In connection with this conjecture, we note that almost all graphs of order n have a Seidel energy of order \(\Theta (n^{3/2})\). Finally, we prove that self-complementary graphs G of order \(n\equiv 1\pmod 4\) have \(\det S(G)=0\).     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.