Identifying codes and locating-dominating sets on paths and cycles

Let G=(V,E) be a graph and let r≥1 be an integer. For a set D⊆V, define N_r[x]={y∈V:d(x,y)≤r} and D_r(x)=N_r[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x∈V (x∈V?D, respectively), D_r(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72-82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987].     

Wallman compactification and matrices of zeroes and ones

Let M be an m by n matrix (where m and n are any finite or infinite cardinals) such that the entries of M are 0's or 1's and M contains the zero row $\text{0}$ and the rows of M are closed under coordinatewise multiplication. We prove that M can be extended to an m by n′ ? n matrix M′ such that the entries of M′ are 0's or 1's and M′ contains the zero row 0?′ and the extension preserves the zero products. Moreover, the newly introduced columns (if any) are pairwise distinct. Furthermore, if E′ is any set of rows of M′ with the property that for every finite subset of rows r′_i of E′ there exists j < n′ such that r′_ij = 1, then every subset of rows of E′ has the same property. We rephrase this by saying that if E′ has the finite intersection property then E′ has a nonempty intersection. We also show (this time by Zorn's lemma) that there exists an extension of M with all the abovementioned properties such that the extension preserves products sums, complements and the newly introduced columns (if any) are pairwise distinct in a stricter sense. In effect, our result shows that the classical Wallman compactification theorem can be formulated purely combinatorially requiring no introduction of any topology on n.     

Superlocalization of waves and electrons and hopping conductivity on classical and superconductive fractals

We have found an unexpected paradoxical situation in the percolation transition: the superconductive behavior below and above the threshold. We have found also the two different density of states d_s=4/3 and d_v=1.05 and the inverse localization lengths for fractons with the scalar and vector interactions, respectively. In this concept the wave functions of electrons or waves on an incipient percolation cluster and fractal dilute structure exhibit superlocalization behavior of the form ψ(r)∝exp[−r^d_φ] with values of d_φ1=1.73 and d_φ2=2.4 for the former and the latter. Applications of these results for thermally activated hopping conductivity σ(t)∝exp[−(T₀/T)^β] between impurities on a random fractal structure give the values of β=2/5 for the scalar and β=1/2 (Mott's law) for the vector interactions, respectively. Band states are localized in classical and superlocalized in superconductive percolations.     

Weak regularity and consecutive topologizations and regularizations of pretopologies

L. Foged proved that a weakly regular topology on a countable set is regular. In terms of convergence theory, this means that the topological reflection Tξ of a regular pretopology ξ on a countable set is regular. It is proved that this still holds if ξ is a regular σ-compact pretopology. On the other hand, it is proved that for each n<ω there is a (regular) pretopology ρ (on a set of cardinality c) such that k(RT)ρ>n(RT)ρ for each k<n and n(RT)ρ is a Hausdorff compact topology, where R is the reflector to regular pretopologies. It is also shown that there exists a regular pretopology of Hausdorff RT-order ?ω₀. Moreover, all these pretopologies have the property that all the points except one are topological and regular.     

Cubicity and Bandwidth

A unit cube in ${\mathbb{R}^k}$ (or a k-cube in short) is defined as the Cartesian product R ₁ × R ₂?× ... × R _k where R _i (for 1??? i??? k) is a closed interval of the form [a _i , a _i + 1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G is the minimum k such that G has a k-cube representation. From a geometric embedding point of view, a k-cube representation of G?=?(V, E) yields an embedding ${f: V(G) \rightarrow \mathbb{R}^k}$ such that for any two vertices u and v, ||f(u) ? f(v)||_?? ?? 1 if and only if ${(u, v) \in E(G)}$ . We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree ?? in O(?? ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(?? ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b ?? n and b is much smaller than n for many well-known graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree ?? and bandwidth b, the cubicity is O(min{b, ?? ln b}). The upper bound of b?+ 1 is used to derive upper bounds for the cubicity of circular-arc graphs, cocomparability graphs and AT-free graphs in terms of the maximum degree ??.     

Radius-edge-invariant and diameter-edge-invariant graphs

The eccentricity e(v) of v is the distance to a farthest vertex from v. The radius r(G) is the minimum eccentricity among the vertices of G and the diameter d(G) is the maximum eccentricity. For graph G−e obtained by deleting edge e in G, we have r(G−e)?r(G) and d(G−e)?d(G). If for all e in G, r(G−e)=r(G), then G is radius-edge-invariant. Similarly, if for all e in G, d(G−e)=d(G), then G is diameter-edge-invariant. In this paper, we study radius-edge-invariant and diameter-edge-invariant graphs and obtain characterizations of radius-edge-invariant graphs and diameter-edge-invariant graphs of diameter two.     

Curvature and mechanics

Classical or Newtonian Mechanics is put in the setting of Riemannian Geometry as a simple mechanical system (M, K, V), where M is a manifold which represents a configuration space, K and V are the kinetic and potential energies respectively of the system. To study the geometry of a simple mechanical system, we study the curvatures of the mechanical manifold (M_h, g_h) relative to a total energy value h, where M_h is an admissible configuration space and g_h the Jacobi metric relative to the energy value h. We call these curvatures h-mechanical curvatures of the simple mechanical system.Results are obtained on the signs of h-mechanical curvature for a general simple mechanical system in a neighborhood of the boundary ?M_h = {xεM: V(x) = h} and in a neighborhood of a critical point of the potential function V. Also we construct $\text{m = (}\text{n}\text{2}\text{) (n =}\text{dim}\text{M)}$ functions defined globally on M_h, called curvature functions which characterize the sign of the h-mechanical curvature. Applications are made to the Kepler problem and the three-body problem.     

Continued fractions and Dedekind sums: Three-term relations and distribution

Let 0?m<N be coprime integers and T(m,N) the sum of the digits of the continued fraction expansion of m/N. We study the distribution of large values of T(m,N) (“large” means T(m,N)?Nα for some fixed exponent α when N tends to infinity), which seems to be quite similar to that of the absolute values of the corresponding Dedekind sums S(m,N). This similarity is (partially, at least) due to analogous three-term relations holding for both kinds of sums. We show, e.g.,

     

Conics and caps

In this article, we begin with arcs in PG(2, q ⁿ ) and show that they correspond to caps in PG(2n, q) via the André/Bruck?CBose representation of PG(2, q ⁿ ) in PG(2n, q). In particular, we show that a conic of PG(2, q ⁿ ) that meets ?_?? in x points corresponds to a (q ⁿ ?+?1 ? x)-cap in PG(2n, q). If x?=?0, this cap is the intersection of n quadrics. If x?=?1 or 2, this cap is contained in the intersection of n quadrics and we discuss ways of extending these caps. We also investigate the structure of the n quadrics.     

Extensions of convex and semiconvex functions and intervally thin sets

We call A⊂RNintervally thin if for all x,y∈RN and ε>0 there exist x^′∈B(x,ε), y^′∈B(y,ε) such that [x^′,y^′]∩A=∅. Closed intervally thin sets behave like sets with measure zero (for example such a set cannot “disconnect” an open connected set). Let us also mention that if the (N−1)-dimensional Hausdorff measure of A is zero, then A is intervally thin. A function f is preconvex if it is convex on every convex subset of its domain. The consequence of our main theorem is the following: Let U be an open subset ofRNand let A be a closed intervally thin subset of U. Then every preconvex functioncan be uniquely extended (with preservation of preconvexity) onto U. In fact we show that a more general version of this result holds for semiconvex functions.     

Sojourns and extremes of Fourier sums and series with random coefficients

Let X(t) be the trigonometric polynomial Σ^k_j=0a_j(U_tcosjt+V_jsinjt), –∞< t<∞, where the coefficients U_t and V_t are random variables and a_j is real. Suppose that these random variables have a joint distribution which is invariant under all orthogonal transformations of R^2k–2. Then X(t) is stationary but not necessarily Gaussian. Put L_t(u) = Lebesgue measure {s: 0?s?t, X(s) > u}, and M(t) = max{X(s): 0?s?t}. Limit theorems for L_t(u) and $\text{P}\text{(M(t) > u)}$ for u→∞ are obtained under the hypothesis that the distribution of the random norm (Σ^k_j=0(U²_j+V²_j))^{1 2} belongs to the domain of attraction of the extreme value distribution exp{ e^–2}. The results are also extended to the random Fourier series (k=∞).     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

The Hilbert-Chow morphism and the incidence divisor: Zero-cycles and divisors

For a smooth projective variety X of dimension n, on the product of Chow varieties C_a(X)×C_n−a−1(X) parameterizing pairs (A,B) of an a-cycle A and an (n−a−1)-cycle B in X, Barry Mazur raised the problem of constructing a Cartier divisor supported on the locus of pairs with A∩B≠0?. We introduce a new approach to this problem, and new techniques supporting this approach.     

Rigidity and stability of the Leibniz and the chain rule

We study rigidity and stability properties of the Leibniz and chain rule operator equations. We describe which non-degenerate operators V, T ₁, T ₂,A: C ^k (?) → C(?) satisfy equations of the generalized Leibniz and chain rule type for f, g ∈ C ^k (?), namely, V (f · g) = (T ₁ f) · g + f · (T ₂ g) for k = 1, V (f · g) = (T ₁ f) · g + f · (T ₂ g) + (Af) · (Ag) for k = 2, and V (f ○ g) = (T ₁ f) ○ g · (T ₂ g) for k = 1. Moreover, for multiplicative maps A, we consider a more general version of the first equation, V (f · g) = (T ₁ f) · (Ag) + (Af) · (T ₂ g) for k = 1. In all these cases, we completely determine all solutions. It turns out that, in any of the equations, the operators V, T ₁ and T ₂ must be essentially equal. We also consider perturbations of the chain and the Leibniz rule, T (f ○ g) = Tf ○ g · Tg + B(f ○ g, g) and T (f · g) = Tf · g + f · Tg + B(f, g), and show under suitable conditions on B in the first case that B = 0 and in the second case that the solution is a perturbation of the solution of the standard Leibniz rule equation.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Hyperreflexivity and operator ideals

Suppose (B,β) is an operator ideal, and A is a linear space of operators between Banach spaces X and Y. Modifying the classical notion of hyperreflexivity, we say that A is called B-hyperreflexive if there exists a constant C such that, for any T∈B(X,Y) with α=supβ(qTi)<∞ (the supremum runs over all isometric embeddings i into X, and all quotient maps of Y, satisfying qAi=0), there exists a∈A, for which β(T−a)?Cα. In this paper, we give examples of B-hyperreflexive spaces, as well as of spaces failing this property. In the last section, we apply SE-hyperreflexivity of operator algebras (SE is a regular symmetrically normed operator ideal) to constructing operator spaces with prescribed families of completely bounded maps.     

Taylor series and divisibility

LetA be an augmentedK-algebra; defineT:A →A ?k _kA byT(a)=1?a ?a?1,a ∈A. We prove, under some conditions, thatg is in the subalgebraK[f] ofA generated byf if and only ifT(g) is in the principal ideal generated byT(f) inA?k _kA. WhenA=K[[X]],T(f) is a multiple ofT(X) if and only iff belongs to the ringL obtained by localizingK[X] at (X).     

New results on value functions and applications to MaxSup and MaxInf problems

In this paper, in the setting of sequential spaces, we consider the value functions v_S and v_I defined by v_S(x)=sup_y∈K(x)f(x,y) and v_I(x)=inf_y∈K(x)f(x,y), and we introduce sufficient conditions on the value functions and on the data, weaker than upper semicontinuity, which guarantee the existence of maximum for such functions. Various examples illustrate the results and the connections with previous results.