On some d-dimensional dual hyperovals in

Let d≥3. Let H be a d+1-dimensional vector space over GF(2) and {e₀,…,e_d} be a specified basis of H. We define Supp(t){e_t1,…,e_tl}, a subset of a specified base for a non-zero vector t=e_t1++e_tl of H, and Supp(0)0/. We also define J(t)Supp(t) if |Supp(t)| is odd, and J(t)Supp(t){0} if |Supp(t)| is even.For s,tH, let {a(s,t)} be elements of H(HH) which satisfy the following conditions: (1) a(s,s)=(0,0), (2) a(s,t)=a(t,s), (3) a(s,t)≠(0,0) if s≠t, (4) a(s,t)=a(s^′,t^′) if and only if {s,t}={s^′,t^′}, (5) {a(s,t)|tH} is a vector space over GF(2), (6) {a(s,t)|s,tH} generate H(HH). Then, it is known that S{X(s)|sH}, where X(s){a(s,t)|tH{s}}, is a dual hyperoval in PG(d(d+3)/2,2)=(H(HH)){(0,0)}.In this note, we assume that, for s,tH, there exists some x_s,t in GF(2) such that a(s,t) satisfies the following equation: Then, we prove that the dual hyperoval constructed by {a(s,t)} is isomorphic to either the Huybrechts’ dual hyperoval, or the Buratti and Del Fra’s dual hyperoval.     

About equivalent interval colorings of weighted graphs

Given a graph G=(V,E) with strictly positive integer weights ω_i on the vertices iV, a k-interval coloring of G is a function I that assigns an interval I(i){1,…,k} of ω_i consecutive integers (called colors) to each vertex iV. If two adjacent vertices x and y have common colors, i.e. I(i)∩I(j)≠0/ for an edge [i,j] in G, then the edge [i,j] is said conflicting. A k-interval coloring without conflicting edges is said legal. The interval coloring problem (ICP) is to determine the smallest integer k, called interval chromatic number of G and denoted χ_int(G), such that there exists a legal k-interval coloring of G. For a fixed integer k, the k-interval graph coloring problem (k-ICP) is to determine a k-interval coloring of G with a minimum number of conflicting edges. The ICP and k-ICP generalize classical vertex coloring problems where a single color has to be assigned to each vertex (i.e., ω_i=1 for all vertices iV).Two k-interval colorings I₁ and I₂ are said equivalent if there is a permutation π of the integers 1,…,k such that ℓI₁(i) if and only if π(ℓ)I₂(i) for all vertices iV. As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the k-ICP can be increased by avoiding considering equivalent k-interval colorings, assuming that they can be identified very quickly. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two k-interval colorings. We then show how a simple tabu search algorithm for the k-ICP can possibly be improved by forbidding the visit of equivalent solutions.     

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

On the similarity of dual operators

Let k be a field with an involution σ and a non-degenerate sesquilinear form, where V,W are n-dimensional k-spaces. Assume that ΛEnd(V) and Λ^*End(W) are dual operators. We show that if Λ and Λ^* are similar, then Λ^*=Λ^-1, where :V→W is Hermitian.     

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

Given a graph G = (V, E), a weight function w: E → R⁺, and a parameter k, we consider the problem of finding a subset U  V of size k that maximizes: Max-Vertex Cover_k: the weight of edges incident with vertices in U,Max-Dense Subgraph_k: the weight of edges in the subgraph induced by U,Max-Cut_k: the weight of edges cut by the partition (U, V\U),Max-Uncut_k: the weight of edges not cut by the partition (U, V\U).For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80% of the edges.     

Sparse hypergraphs and pebble game algorithms

A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V^′V spans more than k|V^′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.     

LOWER BOUNDS FOR SUP＋INF AND SUP＊INF AND AN EXTENSION OF CHEN-LIN RESULT IN DIMENSION 3

We give two results about Harnack type inequalities. First, on Riemannian surfaces, we have an estimate of type sup ＋ inf. The second result concern the solutions of prescribed scalar curvature equation on the unit ball of Rn with Dirichlet condition. Next, we give an inequality of type （supK ^u）^2s-1 × infπu ≤ c for positive solutions of △u = V u^5 on Ω belong toR^3, where K is a compact set of Ω and V is s-Holderian, s ∈] - 1/2, 1]. For the case s = 1/2 and Ω = S3, we prove that, if minΩ u 〉 m 〉 0 （for some particular constant m 〉 0）, and the H¨olderian constant A of V tends to 0 （in certain meaning）, we have the uniform boundedness of the supremum of the solutions of the previous equation on any compact set of Ω.     

A pointwise convergence for Sobolev space functions

Let 1<p<∞, and k,m be positive integers such that 0(k−2m)pn. Suppose ΩRⁿ is an open set, and Δ is the Laplacian operator. We will show that there is a sequence of positive constants c_j such that for every f in the Sobolev space W^k,p(Ω), for all xΩ except on a set whose Bessel capacity B_k−2m,p is zero.     

A Pair in a Crowd of Unit Balls

Let F be a family of mutually nonoverlapping unit balls in the n -dimensional Euclidean space Rⁿ. The distance between the centres of A,B   F is denoted by d(A, B). We prove, among others, that if d(A, B)  <  4 and n ≥  5, then A andB are always visible from each other, that is, a light ray emanating from the surface of A reaches B without being blocked by other unit balls. Furthermore, if d(A, B)  < 2n / 2, then any small “shake’ of F can make A, B visible from each other.     

On value sets of polynomials over a field

Let F be any field. Let p(F) be the characteristic of F if F is not of characteristic zero, and let p(F)=+∞ otherwise. Let A₁,…,A_n be finite nonempty subsets of F, and let

with k{1,2,3,…}, a₁,…,a_nF{0} and degg<k. We show that

When kn and |A_i|i for i=1,…,n, we also have

consequently, if nk then for any finite subset A of F we have

In the case n>k, we propose a further conjecture which extends the Erdős–Heilbronn conjecture in a new direction.     

Density of Gabor Frames

A Gabor system is a set of time-frequency shifts S(g, Λ) ={e^{2 π ibx}g(x − a)}_{(a, b) Λ} of a function g L²(R^d). We prove that if a finite union of Gabor systems _{k = 1}^rS(g_k, Λ_k) forms a frame for L²(R^d) then the lower and upper Beurling densities of Λ = _{k = 1}^r Λ_k satisfy D⁻(Λ) ≥ 1 and D ⁺ (Λ) < ∞. This extends recent work of Ramanathan and Steger. Additionally, we prove the conjecture that no collection _{k = 1}^r{g_k(x − a)}_{a Γk} of pure translates can form a frame for L²(R^d).     

Optimal Recovery of the Derivative of Periodic Analytic Functions from Hardy Classes

LetS_β{z : |Im z|<β}. For 2π-periodic functions which are analytic inS_βwithp-integrable boundary values, we construct an optimal method of recovery off′(ξ), ξS_β, using information about the valuesf(x₁), mldr;, f(x_n), x_j[0, 2π).     

Irredundant intersections of valuation overrings of two-dimensional Noetherian domains

Let D be a two-dimensional Noetherian domain, let R be an overring of D, and let Σ and Γ be collections of valuation overrings of D. We consider circumstances under which (_VΣV)∩R=(_WΓW)∩R implies that Σ=Γ. We show that if R is integrally closed, these representations are “strongly” irredundant, and every member of ΣΓ has Krull dimension 2, then Σ=Γ. If in addition Σ and Γ are Noetherian subspaces of the Zariski–Riemann space of the quotient field of D (e.g. if Σ and Γ have finite character), then the restriction that the members of ΣΓ have Krull dimension 2 can be omitted. An example shows that these results do not extend to overrings of three-dimensional Noetherian domains.     

Linking and Multiplicity Results for the p-Laplacian on Unbounded Cylinders

We consider the p-Laplacian problem[formula]on unbounded cylinders Ω = Ω̃ × R^N − m  R^N, N − m ≥ 2, where Δ_pu = div(|u|^p − 2u), λ is a constant in a certain range, and a  L^N/p(Ω) ∩ L^∞(Ω) is nonnegative, a  0. Using the principle of symmetric criticality, existence and multiplicity are proved under suitable conditions on a and f.     

On Equivalence of Moduli of Smoothness

It is known that iffW^k_p, thenω_m(f, t)_ptω_m−1(f′, t)_p…. Its inverse with any constants independent offis not true in general. Hu and Yu proved that the inverse holds true for splinesSwith equally spaced knots, thusω_m(S, t)_ptω_m−1(S′, t)_pt²ω_m−2(S″, t)_p…. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.     

Density and invariant means in left amenable semigroups

A left cancellative and left amenable semigroup S satisfies the Strong Følner Condition. That is, given any finite subset H of S and any >0, there is a finite nonempty subset F of S such that for each sH, |sFF|<|F|. This condition is useful in defining a very well behaved notion of density, which we call Følner density, via the notion of a left Følner net, that is a net F_ααD of finite nonempty subsets of S such that for each sS, (|sF_αF_α|)/|F_α| converges to 0. Motivated by a desire to show that this density behaves as it should on cartesian products, we were led to consider the set LIM₀(S) which is the set of left invariant means which are weak^* limits in l_∞(S)^* of left Følner nets. We show that the set of all left invariant means is the weak^* closure of the convex hull of LIM₀(S). (If S is a left amenable group, this is a relatively old result of C. Chou.) We obtain our desired density result as a corollary. We also show that the set of left invariant means on is actually equal to . We also derive some properties of the extreme points of the set of left invariant means on S, regarded as measures on βS, and investigate the algebraic implications of the assumption that there is a left invariant mean on S which is non-zero on some singleton subset of βS.     

Sharp estimates of bounded solutions to some semilinear second order dissipative equations

Let H, V be two real Hilbert spaces such that VH with continuous and dense imbedding, and let FC¹(V) be convex. By using differential inequalities, a close-to-optimal ultimate bound of the energy is obtained for solutions in to u^″+cu^′+bu+F(u)=f(t) whenever .