Judicious bisection of hypergraphs

Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously.In this paper,we prove that if G is a hypergraph with n vertices and m_i edges of size i for i=1,2,...,k,then G admits a bisection in which each vertex class spans at most(m_1)/2+1/4m_2+…+(1/(2~k)+m_k+o(m_1+…+m_k) edges,where G is dense enough or △(G)= o(n) but has no isolated vertex,which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.     

On the derivative of the Minkowski question mark function ?(<Emphasis Type="Italic">x</Emphasis>)

Let x?=?[0; a ₁ , a ₂ , …] be the regular continued fraction expansion of an irrational number x ∈ [0, 1]. For the derivative of the Minkowski function ?(x) we prove that ?′(x)?=?+∞, provided that \( \mathop {{\lim \sup }}\limits_{t \to \infty } \frac{{{a_1} + \cdots + {a_t}}}{t} < {\kappa_1} = \frac{{2\log {\lambda_1}}}{{\log 2}} = {1.388^{+} } \), and ?′(x)?=?0, provided that \( \mathop {{\lim \inf }}\limits_{t \to \infty } \frac{{{a_1} + \cdots + {a_t}}}{t} > {\kappa_2} = \frac{{4{L_5} - 5{L_4}}}{{{L_5} - {L_4}}} = {4.401^{+} } \), where \( {L_j} = \log \left( {\frac{{j + \sqrt {{{j^2} + 4}} }}{2}} \right) - j \cdot \frac{{\log 2}}{2} \). Constants κ₁, κ₂ are the best possible. It is also shown that ?′(x)?=?+∞ for all x with partial quotients bounded by 4.     

On the application of linear positive operators for approximation of functions

For the linear positive Korovkin operator \(f\left( x \right) \to {t_n}\left( {f;x} \right) = \frac{1}{\pi }\int_{ - \pi }^\pi {f\left( {x + t} \right)E\left( t \right)dt} \), where E(x) is the Egervary–Szász polynomial and the corresponding interpolation mean \({t_{n,N}}\left( {f;x} \right) = \frac{1}{N}\sum\limits_{k = - N}^{N - 1} {{E_n}\left( {x - \frac{{\pi k}}{N}} \right)f\left( {\frac{{\pi k}}{N}} \right)} \), the Jackson-type inequalities \(\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant \left( {1 + \pi } \right){\omega _f}\left( {\frac{1}{n}} \right),\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant 2{\omega _f}\left( {\frac{\pi }{{n + 1}}} \right)\), where ωf (x) denotes the modulus of continuity, are proved for N > n/2. For ωf (x) ≤ Mx, the inequality \(\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant \frac{{\pi M}}{{n + 1}}\). is established. As a consequence, an elementary derivation of an asymptotically sharp estimate of the Kolmogorov width of a compact set of functions satisfying the Lipschitz condition is obtained.     

Sharp Estimates for Mean Square Approximations of Classes of Differentiable Periodic Functions by Shift Spaces

Let L₂ be the space of 2π-periodic square-summable functions and E(f, X)₂ be the best approximation of f by the space X in L₂. For n ∈ ? and B ∈ L₂, let \({{\Bbb S}_{B,n}}\) be the space of functions s of the form \(s\left( x \right) = \sum\limits_{j = 0}^{2n - 1} {{\beta _j}B\left( {x - \frac{{j\pi }}{n}} \right)} \). This paper describes all spaces \({{\Bbb S}_{B,n}}\) that satisfy the exact inequality \(E{\left( {f,{S_{B,n}}} \right)_2} \leqslant \frac{1}{{^{{n^r}}}}\parallel {f^{\left( r \right)}}{\parallel _2}\). (2n–1)-dimensional subspaces fulfilling the same estimate are specified. Well-known inequalities are for approximation by trigonometric polynomials and splines obtained as special cases.     

Hrmander Type Theorem for Fourier Multipliers with Optimal Smoothness on Hardy Spaces of Arbitrary Number of Parameters

The main purpose of this paper is to establish the Hormander-Mihlin type theorem for Fourier multipliers with optimal smoothness on k-parameter Hardy spaces for k≥ 3 using the multiparameter Littlewood-Paley theory. For the sake of convenience and simplicity, we only consider the case k = 3, and the method works for all the cases k≥ 3:■where x =(x_1,x_2,x_3)∈R~(n_1)×R~(n_2)×R~(n_3) and ξ =(ξ_1,ξ_2,ξ_3)∈R~(n_1)×R~(n_2)×R~(n_3). One of our main results is the following:Assume that m(ξ) is a function on R~(n_1+n_2+n_3) satisfying ■ with s_i n_i(1/p-1/2) for 1≤i≤3. Then T_m is bounded from H~p(R~(n_1)×R~(n_2)×R~(n_3) to H~p(R~(n_1)×R~(n_2)×R~(n_3)for all 0 p≤1 and ■ Moreover, the smoothness assumption on s_i for 1≤i≤3 is optimal. Here we have used the notations m_(j,k,l)(ξ)=m(2~jξ_1,2~kξ_2,2~lξ_3)Ψ(ξ_1)Ψ(ξ_2)Ψ(ξ_3) and Ψ(ξ_i) is a suitable cut-off function on R~(n_i) for1≤i≤3, and W~(s_1,s_2,s_3) is a three-parameter Sobolev space on R~(n_1)×R~(n_2)× R~(n_3).Because the Fefferman criterion breaks down in three parameters or more, we consider the L~p boundedness of the Littlewood-Paley square function of T_mf to establish its boundedness on the multi-parameter Hardy spaces.     

Complementary inequalities to improved AM-GM inequality

Following an idea of Lin, we prove that if A and B are two positive operators such that 0 mI ≤ A ≤m'I≤ M'I ≤ B ≤ MI, then Φ~2(A+B/2)≤K~2(h)/(1+(logM'/m'/g))~2Φ~2(A≠B) and Φ~2(A+B/2)≤K~2(h)/(1+(logM'/m'/g))~2(Φ(A)≠Φ(B))~2 where K(h)=(h+1)~2/4 and h = M/m and Φ is a positive unital linear map.     

On judicious bipartitions of graphs

For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V ₁?V ₂ such that G has at most s edges with both incident vertices in V _i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.     

Complexity of linear and majority functions in the basis of antichain functions

The complexity of realization of Boolean functions by circuits of functional elements in the basis consisting of all characteristic functions of antichains over a Boolean cube is studied. It is proved that the complexity of realization of an n-variable parity function is \(\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor \) and the complexity of its negation equals the complexity of the n-variable majority function which is \(\left\lceil {\frac{{n + 1}}{2}} \right\rceil \).     

Parity check matrices and product representations of squares

Let \(N_{\mathbb{F}} \)(n,k,r) denote the maximum number of columns in an n-row matrix with entries in a finite field \(\mathbb{F}\) in which each column has at most r nonzero entries and every k columns are linearly independent over \(\mathbb{F}\). We obtain near-optimal upper bounds for \(N_{\mathbb{F}} \)(n,k,r) in the case k > r. Namely, we show that \(N_\mathbb{F} (n,k,r) \ll n^{\frac{r}{2} + \frac{{cr}}{k}} \) where \(c \approx \frac{4}{3}\) for large k. Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependencies. We present additional applications of this method to a problem on hypergraphs and a problem in combinatorial number theory.     

The <Emphasis Type="Italic">p</Emphasis>-adic order of some fibonomial coefficients whose entries are powers of <Emphasis Type="Italic">p</Emphasis>

Let (F _n ) _n≥0 be the Fibonacci sequence. For 1 ≤ k ≤ m, the Fibonomial coefficient is defined as

$${\left[ {\begin{array}{*{20}{c}} m \\ k \end{array}} \right]_F} = \frac{{{F_{m - k + 1}} \cdots {F_{m - 1}}{F_m}}}{{{F_1} \cdots {F_k}}}$$

. In 2013, Marques, Sellers and Trojovský proved that if p is a prime number such that p ≡ ±2 (mod 5), then \(p{\left| {\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]} \right._F}\) for all integers a ≥ 1. In 2015, Marques and Trojovský worked on the p-adic order of \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all a ≥ 1 when p ≠ 5. In this paper, we shall provide the exact p-adic order of \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all integers a, b ≥ 1 and for all prime number p.

     

On a Congruence Involving Generalized Fibonomial Coefficients

Let (F_n)_n≥0 be the Fibonacci sequence. For 1 ≤ k ≤ m, the Fibonomial coefficient is defined as

$${\left[ {\begin{array}{*{20}{c}} n \\ k \end{array}} \right]_F} = \frac{{{F_{n - k + 1}} \cdots {F_{n - 1}}{F_n}}}{{{F_1} \cdots {F_k}}}$$

. In 2013, Marques, Sellers and Trojovský proved that if p is a prime number such that p ≡ ±1 (mod 5), then p?\({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all integers a ≥ 1. In 2010, in particular, Kilic generalized the Fibonomial coefficients for

$${\left[ {\begin{array}{*{20}{c}} n \\ k \end{array}} \right]_{F,m}} = \frac{{{F_{\left( {n - k + 1} \right)m}} \cdots {F_{\left( {n - 1} \right)m}}{F_{nm}}}}{{{F_m} \cdots {F_{km}}}}$$

. In this note, we generalize Marques, Sellers and Trojovský result to prove, in particular, that if p ≡ ±1 (mod 5), then \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_{F,m}} \equiv 1\) (mod p), for all a ≥ 0 and m ≥ 1.

     

Up-embeddability of graphs with new degree-sum

Let G be a k(k ≤ 2)-edge connected simple graph with minimal degree ≥ 3 and girth \(g,r = \left\lfloor {\frac{{g - 1}}{2}} \right\rfloor \). For any edge uv ∈ E(G), if

$${d_G}\left( u \right) + {d_G}\left( v \right) > \frac{{2v\left( G \right) - 2\left( {k + 1} \right)\left( {g - 2r} \right)}}{{\left( {k + 1} \right)\left( {{2^r} - 1} \right)\left( {g - 2r} \right)}} + 2\left( {g - 2r - 1} \right),$$

then G is up-embeddable. Furthermore, similar results for 3-edge connected simple graphs are also obtained.

     

Divergent solutions to the <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-supercritical NLS equations

We investigate the nonlinear Schrödinger equation iu _t +Δu+|u| ^p?1 u = 0with 1+ 4/N < p < 1+ 4/N?2 (when N = 1, 2, 1 + 4/N < p < ∞) in energy space H ¹ and study the divergent property of infinite-variance and nonradial solutions. If \(M{\left( u \right)^{\frac{{1 - {s_C}}}{{{s_C}}}}}E\left( u \right) \prec M{\left( Q \right)^{\frac{{1 - {s_C}}}{{{s_C}}}}}E\left( Q \right)\) and \(\left\| {{u_0}} \right\|_2^{\frac{{1 - {s_c}}}{{{s_c}}}}\left\| {\nabla {u_0}} \right\|_2^{\frac{{1 - {s_c}}}{{{s_c}}}}{\left\| {\nabla Q} \right\|_2}\), then either u(t) blows up in finite forward time or u(t) exists globally for positive time and there exists a time sequence t _n → +∞ such that \({\left\| {\nabla u\left( {{t_n}} \right)} \right\|_2} \to + \infty \). Here Q is the ground state solution of ?(1?s _c )Q+ΔQ+Q ^p?1 Q = 0. A similar result holds for negative time. This extend the result of the 3D cubic Schrödinger equation obtained by Holmer to the general mass-supercritical and energy-subcritical case.     

Two families of Niho sequences having four-valued cross correlation with <Emphasis Type="Italic">m</Emphasis>-sequences

For two odd integers m and s with 1 ≤ s < m and gcd(m ; s ) = 1, let h satisfy h (2^s ? 1) ≡ 1 (mod 2^m + 1) and d = (h + 1)(2^m ? 1) + 1. The cross correlation function between a binary m-sequence of period 2^2m ? 1 and its d-decimation sequence is proved to take four values, and the correlation distribution is completely determined. Let n be an even integer and k be an integer with \(1 \leqslant k \leqslant \frac{n}{2}\). For an odd prime p and a p-ary m-sequence {s(t)} of period pn ? 1, define u(t) = \(\sum \begin{array}{*{20}{c}}{\frac{{{p^k} - 1}}{2}} \\ {i = 0} \end{array}\) s(dit), where di = \(i{p^{\frac{n}{2}}} + {p^k} - i\) ? i and i = 0,1,..., \(\frac{{{p^k} - 1}}{2}\). It is proved that the cross correlation function between {u(t)} and {s(t)} is three-valued or four-valued depending on whether k is equal to \(\frac{n}{2}\) or not, and the distribution is also determined.     

How many matrices can be spectrally balanced simultaneously?

We prove that any ? positive definite d × d matrices, M₁,...,M_?, of full rank, can be simultaneously spectrally balanced in the following sense: for any k < d such that ? ≤ \(\ell \leqslant \left\lfloor {\frac{{d - 1}}{{k - 1}}} \right\rfloor \), there exists a matrix A satisfying \(\frac{{{\lambda _1}\left( {{A^T}{M_i}A} \right)}}{{Tr\left( {{A^T}{M_i}A} \right)}} < \frac{1}{k}\) 1/k for all i, where λ₁(M) denotes the largest eigenvalue of a matrix M. This answers a question posed by Peres, Popov and Sousi ([PPS13]) and completes the picture described in that paper regarding sufficient conditions for transience of self-interacting random walks. Furthermore, in some cases we give quantitative bounds on the transience of such walks.     

A Supplement to Hölder’s Inequality. The Resonance Case. I

Suppose that m ≥ 2, numbers p₁, …, p _m ∈ (1, +∞] satisfy the inequality \(\frac{1}{{{p_1}}} + ... + \frac{1}{{{p_m}}} < 1\), and functions γ₁ ∈ \({L^{{p_1}}}\)(?¹), …, γ _m ∈ \({L^{{p_m}}}\)(?¹) are given. It is proved that if the set of “resonance points” of each of these functions is nonempty and the so-called “resonance condition” holds, then there are arbitrarily small (in norm) perturbations Δγ_k ∈ \({L^{{p_k}}}\)(?¹) under which the resonance set of each function γ_k + Δγ_k coincides with that of γ_k for 1 ≤ k ≤ m, but \({\left\| {\int\limits_0^t {\prod\limits_{k = 0}^m {\left[ {{\gamma _k}\left( \tau \right) + \Delta {\gamma _k}\left( \tau \right)} \right]d\tau } } } \right\|_{{L^\infty }\left( {{\mathbb{R}^1}} \right)}} = \infty \). The notion of a resonance point and the resonance condition for functions in the spaces L ^p (?¹), p ∈ (1, +∞], were introduced by the author in his previous papers.     

On one complement to the Hölder inequality: I

Let m ≥ 2, the numbers p ₁,…, p _m ∈ (1, +∞] satisfy the inequality \(\frac{1}{{{p_1}}} + ...\frac{1}{{{p_m}}} < 1\), and γ₁ ∈ L ^p1(?¹), …, γ _m ∈ \({L^{{p_m}}}\)(?¹). We prove that, if the set of “resonance” points of each of these functions is nonempty and the “nonresonance” condition holds (both concepts have been introduced by the author for functions of spaces L ^p (?¹), p ∈ (1, +∞]), we have the inequality \(\mathop {\sup }\limits_{a,b \in {R^1}} \left| {\int\limits_a^b {\prod\limits_{k = 1}^m {\left[ {{\gamma _k}\left( \tau \right) + \Delta {\gamma _k}\left( \tau \right)} \right]} d\tau } } \right| \leqslant C{\prod\limits_{k = 1}^m {\left\| {{\gamma _k} + \Delta {\gamma _k}} \right\|} _{L_{{a_k}}^{{p_k}}}}\left( {{\mathbb{R}^1}} \right)\), where the constant C > 0 is independent of functions \(\Delta {\gamma _k} \in L_{{a_k}}^{{p_k}}\left( {{\mathbb{R}^1}} \right)\) and \(L_{{a_k}}^{{p_k}}\left( {{\mathbb{R}^1}} \right) \subset {L^{{p_k}}}\left( {{\mathbb{R}^1}} \right)\), 1 ≤ k ≤ m are some specially constructed normed spaces. In addition, we give a boundedness condition for the integral of the product of functions over a subset of ?¹.     

On a Composition Preserving Inequalities between Polynomials

The Schur-Szegö composition of two polynomials \(f\left( z \right) = \sum\nolimits_{j = 0}^n {{A_j}{z^j}} \) and \(g\left( z \right) = \sum\nolimits_{j = 0}^n {{B_j}{z^j}} \), both of degree n, is defined by \(f * g\left( z \right) = \sum\nolimits_{j = 0}^n {{A_j}{B_j}{{\left( {\begin{array}{*{20}{c}}n \\ j \end{array}} \right)}^{ - 1}}{z^j}} \). In this paper, we estimate the minimum and the maximum of the modulus of f * g(z) on z = 1 and thereby obtain results analogues to Bernstein type inequalities for polynomials.     

Determination of cusp forms by central values of Rankin–Selberg <Emphasis Type="BoldItalic">L</Emphasis>-functions<Superscript>*</Superscript>

Let f be a fixed holomorphic Hecke eigen cusp form of weight k for \( SL\left( {2,{\mathbb Z}} \right) \), and let \( {\mathcal U} = \left\{ {{u_j}:j \geqslant 1} \right\} \) be an orthonormal basis of Hecke–Maass cusp forms for \( SL\left( {2,{\mathbb Z}} \right) \). We prove an asymptotic formula for the twisted first moment of the Rankin–Selberg L-functions \( L\left( {s,f \otimes {u_j}} \right) \) at \( s = \frac{1}{2} \) as u _j runs over \( {\mathcal U} \). It follows that f is uniquely determined by the central values of the family of Rankin–Selberg L-functions \( \left\{ {L\left( {s,f \otimes {u_j}} \right):{u_j} \in {\mathcal U}} \right\} \).