Short propositional refutations for dense random 3CNF formulas

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notable are the exponential-size resolution refutation lower bounds for random 3CNF formulas with Ω(n^1.5−ε)$\mathrm{\Omega }(n^{1.5-\epsilon })$ clauses (Chvátal and Szemerédi [14], Ben-Sasson and Wigderson [10]). On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with Ω(n²/log?n)$\mathrm{\Omega }(n^2/\log ?n)$ clauses, shown by Beame et al. [6]. In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are TC⁰${\mathit{T}\mathit{C}}^0$ formulas (i.e., TC⁰${\mathit{T}\mathit{C}}^0$-Frege proofs) for random 3CNF formulas with n   variables and Ω(n^1.4)$\mathrm{\Omega }(n^{1.4})$ clauses.     

The topological structure of fuzzy sets with sendograph metric

For a non-degenerate convex subset Y of the n  -dimensional Euclidean space Rⁿ${\mathbb{R}}^n$, let F(Y)$\mathbb{F}(Y)$ be the family of all fuzzy sets of Rⁿ${\mathbb{R}}^n$ which are upper semicontinuous, fuzzy convex and normal with compact supports contained in Y  . We show that the space F(Y)$\mathbb{F}(Y)$ with the topology of sendograph metric is homeomorphic to the separable Hilbert space ?²${?}^2$ if Y   is compact; and the space F(Rⁿ)$\mathbb{F}({\mathbb{R}}^n)$ is also homeomorphic to ?²${?}^2$.     

Dimension spectra of random subfractals of self-similar fractals

The dimension of a point x   in Euclidean space (meaning the constructive Hausdorff dimension of the singleton set {x}$\{x\}$) is the algorithmic information density of x  . Roughly speaking, this is the least real number dim(x)$\dim (x)$ such that r×dim(x)$r\times \dim (x)$ bits suffice to specify x   on a general-purpose computer with arbitrarily high precision 2^−r$2^{-r}$. The dimension spectrum of a set X   in Euclidean space is the subset of [0,n]$[0,n]$ consisting of the dimensions of all points in X.     

On oriented graphs whose skew spectral radii do not exceed 2

Let S(G^σ)$S(G^{\sigma })$ be the skew adjacency matrix of the oriented graph G^σ$G^{\sigma }$ of order n   and _λ1,_λ2,…,_λn${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be all eigenvalues of S(G^σ)$S(G^{\sigma })$. The skew spectral radius _ρs(G^σ)${\rho }_s(G^{\sigma })$ of G^σ$G^{\sigma }$ is defined as max{|_λ1|,|_λ2|,…,|_λn|}$\max \{|{\lambda }_1|,|{\lambda }_2|,\dots ,|{\lambda }_n|\}$. In this paper, we investigate oriented graphs whose skew spectral radii do not exceed 2.     

The Dirichlet problem for the fractional Laplacian: Regularity up to the boundary

We study the regularity up to the boundary of solutions to the Dirichlet problem for the fractional Laplacian. We prove that if u   is a solution of (−Δ)^su=g${(-\mathrm{\Delta })}^{s}u=g$ in Ω  , u≡0$u\equiv 0$ in Rⁿ\Ω${\mathbb{R}}^n\backslash \Omega$, for some s∈(0,1)$s\in (0,1)$ and g∈L^∞(Ω)$g\in L^{\infty }(\Omega )$, then u   is C^s(Rⁿ)$C^s({\mathbb{R}}^n)$ and u/δ^s_|Ω$u/{\delta }^s{|}_{\Omega }$ is C^α$C^{\alpha }$ up to the boundary ∂Ω   for some α∈(0,1)$\alpha \in (0,1)$, where δ(x)=dist(x,∂Ω)$\delta (x)=\mathrm{dist}(x,\partial \Omega )$. For this, we develop a fractional analog of the Krylov boundary Harnack method.     

Orthogonally additive polynomials on Fourier algebras

We show that an n-homogeneous polynomial P   on the Fourier algebra A(G)$A(G)$ of a locally compact group G   can be represented in the form P(f)=〈T,fⁿ〉$P(f)=〈T,f^n〉$(f∈A(G))$(f\in A(G))$ for some T   in the group von Neumann algebra VN(G)$\mathit{VN}(G)$ of G if and only if it is orthogonally additive and completely bounded.     

Completeness,precompactness and compactness in finite-dimensional asymmetrically normed lattices

If (X,‖⋅‖)$(X,\Vert \cdot \Vert )$ is a real normed lattice, then p(x)=‖x⁺‖$p(x)=\Vert x^{+}\Vert$ defines an asymmetric norm on X. We characterise the left-K   sequentially complete, precompact and compact subsets of (R^m,p)$({\mathbb{R}}^m,p)$.     

Foundational aspects of singular integrals

We investigate integration of classes of real-valued continuous functions on (0,1]$(0,1]$. Of course difficulties arise if there is a non-L¹$L^1$ element in the class, and the Hadamard finite part integral (p.f.) does not apply. Such singular integrals arise naturally in many contexts including PDEs and singular ODEs.     

A new approach to fixed point theorems on G-metric spaces

In this paper, we introduce the metric d^G$d^G$ on a G  -metric space (X,G)$(X,G)$ and use this notion to show that many contraction conditions for maps on the G  -metric space (X,G)$(X,G)$ reduce to certain contraction conditions for maps on the metric space (X,d^G)$(X,d^G)$. As applications, the proofs of many fixed point theorems for maps on the G  -metric space (X,G)$(X,G)$ may be simplified, and many fixed point theorems for maps on the G  -metric space (X,G)$(X,G)$ are direct consequences of preceding results for maps on the metric space (X,d^G)$(X,d^G)$.     

ZL-amenability and characters for the restricted direct products of finite groups

Let G   be a restricted direct product of finite groups _{Gi}i∈I${\{G_i\}}_{i\in I}$, and let Z?¹(G)${\mathrm{Z}?}^1(G)$ denote the centre of its group algebra. We show that Z?¹(G)${\mathrm{Z}?}^1(G)$ is amenable if and only if _Gi$G_i$ is abelian for all but finitely many i  , and characterize the maximal ideals of Z?¹(G)${\mathrm{Z}?}^1(G)$ which have bounded approximate identities. We also study when an algebra character of Z?¹(G)${\mathrm{Z}?}^1(G)$ belongs to _c0$c_0$ or ?^p${?}^p$ and provide a variety of examples.     

Posets of copies of countable scattered linear orders

We show that the separative quotient of the poset 〈P(L),⊂〉$〈\mathbb{P}(L),\subset 〉$ of isomorphic suborders of a countable scattered linear order L is σ  -closed and atomless. So, under the CH, all these posets are forcing-equivalent (to (P(ω)/Fin)⁺${(P(\omega )/\mathrm{Fin})}^{+}$).     

Regularity of Hölder continuous solutions of the supercritical quasi-geostrophic equation

We present a regularity result for weak solutions of the 2D quasi-geostrophic equation with supercritical (α<1/2$\alpha <1/2$) dissipation α(−Δ)${(-\mathrm{\Delta })}^{\alpha }$: If a Leray–Hopf weak solution is Hölder continuous θ∈Cδ(R²)$\theta \in C^{\delta }({\mathbb{R}}^2)$ with δ>1−2α$\delta >1-2\alpha$ on the time interval [t₀,t]$[t_0,t]$, then it is actually a classical solution on (t₀,t]$(t_0,t]$.     

Two-colorings with many monochromatic cliques in both colors

Color the edges of the n-vertex complete graph in red and blue, and suppose that red k-cliques are fewer than blue k-cliques. We show that the number of red k  -cliques is always less than _ckn^k$c_k{n}^k$, where _ck∈(0,1)$c_k\in (0,1)$ is the unique root of the equation z^k=(1−z)^k+kz(1−z)^k−1$z^k={(1-z)}^k+kz{(1-z)}^{k-1}$. On the other hand, we construct a coloring in which there are at least _ckn^k−O(n^k−1)$c_k{n}^k-O(n^{k-1})$ red k-cliques and at least the same number of blue k-cliques.