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.     

Subgroups of cyclic groups and values of the Riemann zeta function

Let k be a positive integer, x a large real number, and let \(C_n\) be the cyclic group of order n. For \(k\le n\le x\) we determine the mean average order of the subgroups of \(C_n\) generated by k distinct elements and we give asymptotic results of related averaging functions of the orders of subgroups of cyclic groups. The average order is expressed in terms of Jordan’s totient functions and Stirling numbers of the second kind. We have the following consequence. Let k and x be as above. For \(k\le n\le x\), the mean average proportion of \(C_n\) generated by k distinct elements approaches \(\zeta (k+2)/\zeta (k+1)\) as x grows, where \(\zeta (s)\) is the Riemann zeta function.     

Asymptotic Dirichlet Problem for $\mathcal {A}$-Harmonic Functions on Manifolds with Pinched Curvature

We study the asymptotic Dirichlet problem for \(\mathcal {A}\)-harmonic functions on a Cartan-Hadamard manifold whose radial sectional curvatures outside a compact set satisfy an upper bound \( K(P)\le - \frac {1+\varepsilon }{r(x)^{2} \log r(x)} \) and a pointwise pinching condition \( | K(P) |\le C_{K}| K(P^{\prime }) | \) for some constants ε > 0 and C _K ≥ 1, where P and \(P^{\prime }\) are any 2-dimensional subspaces of T _x M containing the (radial) vector ?r(x) and r(x) = d(o, x) is the distance to a fixed point o ∈ M. We solve the asymptotic Dirichlet problem with any continuous boundary data \(f\in C(\partial _{\infty } M)\). The results apply also to the Laplacian and p-Laplacian, \(1<p<\infty ,\) as special cases.     

On Expanding Neighborhoods of Local Universality of Gaussian Unitary Ensembles

The classical universality theorem states that the Christoffel–Darboux kernel of the Hermite polynomials scaled by a factor of \(1/\sqrt n\) tends to the sine kernel in local variables \(\tilde x,\tilde y\) in a neighborhood of a point \(x^*\in(-\sqrt 2,\sqrt 2)\)). This classical result is well known for \(\tilde x,\tilde y\in{K}\Subset\mathbb{R}\). In this paper, we show that this classical result remains valid for expanding compact sets K = K(n). An interesting phenomenon of admissible dependence of the expansion rate of compact sets K(n) on x* is established. For \(x^*\in(-\sqrt 2,\sqrt 2)\backslash\left\{0\right\}\)) and for x* = 0, there are different growth regimes of compact sets K(n). A transient regime is found.     

A group of continuous self-maps on a topological groupoid

The group of bisections of groupoids plays an important role in the study of Lie groupoids. In this paper another construction is introduced. Indeed, for a topological groupoid G, the set of all continuous self-maps f on G such that (x, f(x)) is a composable pair for every \(x\in G\), is denoted by \(S_G\). We show that \(S_G\) by a natural binary operation is a monoid. \(S_G(\alpha )\), the group of units in \(S_G\) precisely consists of those \(f\in S_G\) such that the map \(x\mapsto xf(x)\) is a bijection on G. Similar to the group of bisections, \(S_G(\alpha )\) acts on G from the right and on the space of continuous self-maps on G from the left. It is proved that \(S_G(\alpha )\) with the compact- open topology inherited from C(G, G) is a left topological group. For a compact Hausdorff groupoid G it is proved that the group of bisections of \(G^2\) is isomorphic to the group \(S_G(\alpha )\) and the group of transitive bisections of G, \(Bis_T(G)\), is embedded in \(S_G(\alpha )\), where \(G^2\) is the groupoid of all composable pairs.     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

Some inequalities for <Emphasis Type="Italic">k</Emphasis>-colored partition functions

Motivated by a partition inequality of Bessenrodt and Ono, we obtain analogous inequalities for k-colored partition functions \(p_{-k}(n)\) for all \(k\ge 2\). This enables us to extend the k-colored partition function multiplicatively to a function on k-colored partitions and characterize when it has a unique maximum. We conclude with one conjectural inequality that strengthens our results.     

Sums of powers of primes

Let \(k>-1\). The sum of the kth powers of the primes less than x is asymptotic to \(\pi (x^{k+1})\). We show that the sum is less than \(\pi (x^{k+1})\) for arbitrarily large x, and the reverse inequality also holds for arbitrarily large x. When \(k>0\), there is a bias toward the first inequality, and we explain why this should be true and why the reverse bias holds when \(-1<k<0\).     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

Asymptotic Behaviour of a Random Walk Killed on a Finite Set

We study asymptotic behavior, for large time n, of the transition probability of a two-dimensional random walk killed when entering into a non-empty finite subset A. We show that it behaves like \(4 \tilde u_{A}(x) \tilde u_{-A}(-y) (\lg n)^{-2} p^{n}(y- x)\) for large n, uniformly in the parabolic regime \(|x|\vee |y| =O(\sqrt n)\), where p ⁿ (y-x) is the transition kernel of the random walk (without killing) and \(\tilde u_{A}\) is the unique harmonic function in the ‘exterior of A’ satisfying the boundary condition \(\tilde u_{A}(x) \sim \lg |x|\) at infinity.     

Cyclic compositions and cycles of the hypercube

The partition graph of a positive integer n, \(P_n\), is the graph whose vertices are the cyclic compositions of n and two vertices are adjacent if one composition is obtained from the other one by replacing two cyclically consecutive parts by their sum. In this paper we introduce and investigate the notions of singular cyclic composition and singular edge of \(P_n\). We associate with every singular edge and every cycle of \(P_n\), whose vertices are aperiodic cyclic compositions of n, a cycle or a set of disjoint cycles of equal length of the hypercube \(Q_n\).     

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.     

Most small $${\varvec{}}$$-grous have an automorhism of order 2

Let f(p, n) be the number of pairwise nonisomorphic p-groups of order \(p^n\), and let g(p, n) be the number of groups of order \(p^n\) whose automorphism group is a p-group. We prove that the limit, as p grows to infinity, of the ratio g(p, n) / f(p, n) equals 1/3 for \(n=6,7\).     

Some results on a special case of a general continued fraction of Ramanujan

We derive a new special case C(q) of a general continued fraction recorded by Ramanujan in his Lost Notebook. We give a representation of the continued fraction C(q) as a quotient of Dedekind eta-function and then use it to prove modular identities connecting C(q) with each of the continued fractions \(C(-q)\), \(C(q^{2})\), \(C(q^{3})\), \(C(q^{5})\), \(C(q^{7})\), \(C(q^{11})\), \(C(q^{13})\) and \(C(q^{17})\). We also prove general theorems for the explicit evaluation of the continued fraction C(q) by using Ramanujan’s class invariants.     

Some Estimates of Higher Order Riesz Transform Related to Schrödinger Type Operators

In this paper we consider the Schrödinger type operators \(H_2=(-\Delta)^2 +V^2\), where the nonnegative potential V belongs to the reverse Hölder class \(B_{q_{_1}}\) for \(q_{_1}\geq \frac{n}{2}, n\geq 5\). The L ^p and weak type (1, 1) estimates of higher order Riesz transform \(\nabla^2H^{-\frac{1}{2}}_2 \) related to Schrödinger type operators H ₂ are obtained. In particular, \(\nabla^2H^{-\frac{1}{2}}_2 \) is a Calderón-Zygmund operator if V?∈?B _2n or \(V\in B_\frac{n}{2}\) and there exists a constant C such that V(x)?≤?Cm(x,V)².     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

A Completion of the Spectrum for the Overlarge Sets of Pure Mendelsohn Triple Systems

A pure Mendelsohn triple system of order v, denoted by PMTS(v), is a pair \((X,\mathcal {B})\) where X is a v-set and \(\mathcal {B}\) is a collection of cyclic triples on X such that every ordered pair of X belongs to exactly one triple of \(\mathcal {B}\) and if \(\langle a,b,c\rangle \in \mathcal {B}\) implies \(\langle c,b,a\rangle \notin \mathcal {B}\). An overlarge set of PMTS(v), denoted by OLPMTS(v), is a collection \(\{(Y{\setminus }\{y_i\},{\mathcal {A}}_i)\}_i\), where Y is a \((v+1)\)-set, \(y_i\in Y\), each \((Y{\setminus }\{y_i\},{\mathcal {A}}_i)\) is a PMTS(v) and these \({\mathcal {A}}_i\)s form a partition of all cyclic triples on Y. It is shown in [3] that there exists an OLPMTS(v) for \(v\equiv 1,3\) (mod 6), \(v>3\), or \(v \equiv 0,4\) (mod 12). In this paper, we shall discuss the existence problem of OLPMTS(v)s for \(v\equiv 6,10\) (mod 12) and get the following conclusion: there exists an OLPMTS(v) if and only if \(v\equiv 0,1\) (mod 3), \(v>3\) and \(v\ne 6\).     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.     

Lie n-derivatio ns o n $ {\mathcal {}}$-subspace lattice algebras

Let \(\mathcal {L}\) be a \(\mathcal {J}\)-subspace lattice on a Banach space X over the real or complex field \(\mathbb {F}\) with dimX ≥ 3 and let n ≥ 2 be an integer. Suppose that dimK ≠ 2 for every \(K\in \mathcal {J}{(\mathcal L)}\) and \(L: \text {Alg}\, \mathcal {L}\rightarrow \text {Alg}\,\mathcal {L}\) is a linear map. It is shown that L satisfies \({\sum }_{i=1}^{n}p_{n} (A_{1}, \ldots , A_{i-1}, L(A_{i}), A_{i+1}, \ldots , A_{n})=0\) whenever p _n (A ₁,A ₂,…,A _n ) = 0 for \(A_{1},A_{2},\ldots ,A_{n}\in \text {Alg}\,\mathcal {L}\) if and only if for each \(K\in \mathcal {J}(\mathcal {L})\), there exists a bounded linear operator \(T_{K}\in \mathcal {B}(K)\), a scalar λ _K and a linear functional \(h_{K}: \text {Alg}\,\mathcal {L}\rightarrow \mathbb {F}\) such that L(A)x = (T _K A ? A T _K + λ _K A + h _K (A)I)x for all x ∈ K and all \(A\in \text {Alg}\,\mathcal {L}\). Based on this result, a complete characterization of linear n-Lie derivations on \(\text {Alg}\,\mathcal {L}\) is obtained.