The color space of a graph

If k is a prime power, and G is a graph with n vertices, then a k‐coloring of G may be considered as a vector in $\mathbb{GF}$(k)ⁿ. We prove that the subspace of $\mathbb{GF}$(3)ⁿ spanned by all 3‐colorings of a planar triangle‐free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3‐colorings, and the addition of any edge or any vertex of degree 3 results in a 3‐colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000     

Addendum to ‘avoiding a giant component’

We take this opportunity, which is kindly provided by the editors, to add a theorem and to correct the proof of one of the lemmas in the article ‘Avoiding a Giant Component’ [Bohman and Frieze, Avoiding a giant component, Random Struct Alg 19 (2001), 75–85]. The subject of the said article is the following guided random process. Let e₁, $e^{\prime}_{1}$; e₂, $e^{\prime}_{2}$;…;e_i, $e^{\prime}_{i}$;… be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K_n. This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from e_i, $e_{i}^{\prime}$ to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. In Bohman and Frieze [Avoiding a giant component, Random Struct Alg 19 (2001), 75–85], we proved that these choices can be made so that whp (A sequence of events ?_n is said to occur with high probability (whp) if lim_n→∞ Pr (?_n)=1.), the size of the largest component of the graph formed at stage. 535n, is polylogarithmic in n. Here, we make a correction to that proof and prove that the graph formed at stage cn for any constant c>1 will contain a component of size Ω(n) (regardless of how the edges are chosen at each stage). © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 126–130, 2002     

The multiplier conjecture for elementary abelian groups

Applying the method that we presented in [19], in this article we prove: “Let G be an elementary abelian p-group. Let n = dn₁. If d(≠ p) is a prime not dividing n₁, and the order w of d mod p satisfies $ w > \frac{{d^2}}{3} $, then the Second Multiplier Theorem holds without the assumption n₁ > λ, except that only one case is yet undecided: w ≤ d², and $ \frac{{p - 1}}{{2w}} \ge 3 $, and t is a quadratic residue mod p, and t is not congruent to $ x^{\frac{{p - 1}}{{2w}}j} $ (mod p) (1 ≤ j < 2w), where t is an integer meeting the conditions of Second Multiplier Theorem, and x is a primitive root of p.”. © 1994 John Wiley & Sons, Inc.     

Piercing random boxes

Consider a set of n random axis parallel boxes in the unit hypercube in ${\bf R}^{d}$ , where d is fixed and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least $\Omega_d(\sqrt{n}(\log n)^{d/2-1})$ and at most $O_d(\sqrt{n}(\log n)^{d/2-1}\log \log n)$ . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 365–380, 2011     

Inversion of the Radon transform with incomplete data

The Radon transform R(p, θ), θ∈S^n?1, p∈?¹, of a compactly supported function f(x) with support in a ball B_a of radius a centred at the origin is given for all $ \theta \in \mathop {S^{n - 1} }\limits^\tilde $, where $ \mathop {S^{n - 1} }\limits^\tilde $ is an open set on S^n?1, and all p∈(? ∞, ∞), n≥2. An approximate formula is given to calculate f(x) from the given data.     

On the Additive Group Structure of the Nonstandard Models of the Theory of Integers

Let $\hat \mathbb{Z}$ denote the inverse limit of all finite cyclic groups. Let F, G and H be abelian groups with H ≤ G. Let FβH denote the abelian group (F × H, +^β), where +^βis defined by (a, x) +^β (b, y) = (a + b, x + y + β(a) + β(b) — β(a + b)) for a certain β : F → G linear mod H meaning that β(0) = 0 and β(a) + β(b) — β(a + b) ∈ H for all a, b in F. In this paper we show that the following hold: (1) The additive group of any nonstandard model ℤ* of the ring ℤ is isomorphic to (ℤ*₊/H)βH for a certain β : ℤ*₊/H → $\hat \mathbb{Z}$ linear mod H. (2) $\hat \mathbb{Z}$ is isomorphic to (ℤ₊/H )βH for some β : $\hat \mathbb{Z}$/H →ℚ linear mod H, though $\hat \mathbb{Z}$ is not the additive group of any model of Th(ℤ, +, ×) and the exact sequence H → $\hat \mathbb{Z}$ → $\hat \mathbb{Z}$/H is not splitting.     

Increasing the output length of zero‐error dispersers

Let $\cal{C}$ be a class of probability distributions over a finite set Ω. A function $D : \Omega \mapsto\{0,1\}^{m}$ is a disperser for $\cal{C}$ with entropy threshold $k$ and error $\epsilon$ if for any distribution X in $\cal{C}$ such that X gives positive probability to at least $2^{k}$ elements we have that the distribution $D(X)$ gives positive probability to at least $(1-\epsilon)2^{m}$ elements. A long line of research is devoted to giving explicit (that is polynomial time computable) dispersers (and related objects called “extractors”) for various classes of distributions while trying to maximize m as a function of k. For several interesting classes of distributions there are explicit constructions in the literature of zero‐error dispersers with “small” output length m. In this paper we develop a general technique to improve the output length of zero‐error dispersers. This strategy works for several classes of sources and is inspired by a transformation that improves the output length of extractors (which was given by Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity, (2006) 46–60.) building on earlier work by Gabizon, Raz and Shaltiel (SIAM J Comput 36 (2006) 1072–1094). Our techniques are different than those of Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006) 46–60) and in particular give non‐trivial results in the errorless case. Using our approach we construct improved zero‐error 2‐source dispersers. More precisely, we show that for any constant $\delta >0$ there is a constant $\eta >0$ such that for sufficiently large n there is a poly‐time computable function $D :\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}^{\eta n}$ such that for every two independent distributions $X_1,X_2$ over $\{0,1\}^{n}$ each with support size at least $2^{\delta n}$ , the output distribution $D(X_1,X_2)$ has full support. This improves the output length of previous constructions by Barak, Kindler, Shaltiel, Sudakov and Wigderson (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 1–10) and has applications in Ramsey theory and in improved constructions of certain data structures from the work of Fiat and Naor [SIAM J Comput 22 (1993)]. We also use our techniques to give explicit constructions of zero‐error dispersers for bit‐fixing sources and affine sources over polynomially large fields. These constructions improve the best known explicit constructions due to Rao (unpublished data) and Gabizon and Raz [Combinatorica 28 (2008)] and achieve $m=\Omega(k)$ for bit‐fixing sources and $m=k-o(k)$ for affine sources over polynomial size fields. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Derived Functors of Hom Relative to Flat Covers

We study the derived functors of Hom that are computed by using flat resolutions of Hom. These are denoted ⁿ. We compare these with the usual Extⁿ's and show that ¹⊂ Ext¹and indicate (using MacLane's terminology) why the class of associated short exact sequences is a proper class. When the ring is a Dedekind domain we classify the N such that ⁿ(–, N) = 0 and show that unlike the situation for other classically defined right derived functors of Hom, Hom is not balanced relative to the two classes of modules that make ¹ vanish.     

An Lq-theory for weak solutions of the stokes system in exterior domains

We introduce a new concept for weak solutions in L^q-spaces, 1 < q < ∞, of the Stokes system in an exterior domain Ω ? ?ⁿ, n ? 2. Defining the variational formulation in the homogeneous Sobolev space $ \mathop H\limits^.{_{0}}^{1,q} (\Omega )^n = \{ u \in L_{1{\rm oc}}^q (\overline \Omega )^n;\nabla u \in L^q (\Omega )^{n^2 },u\left| {_{\partial \Omega } = 0} \right.\},$ we prove existence and uniqueness of weak solutions for an arbitrary external force and a prescribed divergence g = div u. On the other hand, solutions in the sense of distributions which are defined by taking test functions only in C(Ω)ⁿ are not unique if q > n/(n?1). In this case, a hidden boundary condition related to the force exerted on the body may be imposed to single out a unique solution.     

The cover time of random geometric graphs

We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r. Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x. The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G. Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011     

Unions and Intersections of Families of Lp-Spaces

Let L^Ψ and E^Ψ be the ORLICZ space and the space of finite elements respectively, on a measure space (Ω, Σ, μ), and let T ? (0, ∞). It is proved that if inf {p: p ? T} ? T or sup {p: p ? T} ? T and μ is an infinite atomless measure, then there is no ORLICZ function Ψ such that: \documentclass{article}\pagestyle{empty}\begin{document}$ L^\varphi = Lin\mathop { \cup L^p }\limits_{p\varepsilon T} $\end{document} or \documentclass{article}\pagestyle{empty}\begin{document}$ E^\varphi = Lin\mathop { \cup L^p }\limits_{p\varepsilon T} $\end{document} and moreover, there is no ORLICZ function Ψ such that: \documentclass{article}\pagestyle{empty}\begin{document}$ L^\varphi = Lin\mathop { \cap L^p }\limits_{p\varepsilon T} $\end{document} or \documentclass{article}\pagestyle{empty}\begin{document}$ E^\varphi = Lin\mathop { \cap L^p }\limits_{p\varepsilon T} $\end{document}.     

What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?

A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well-known conjectures by G. Hajós, P. Erd?s, and P.J. Kelly: (1) [B. Jackson] Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{n}{2} $\end{document} dicycles. (2) [W. Bienia & H. Meyniel] Every eulerian digraph is decomposable into at most n dicycles. Certain observations lead us to make three other conjectures: (a) Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{2n}}{3} $\end{document} dicycles. (b) Every symmetric digraph with n > 1 is decomposable into at most 2n – 3 dicycles. (c) Every eulerian digraph with n > 1 is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{8n}}{3} $\end{document} – 3 dicycles.     

Integral Operators in Sobolev Spaces on Domains with Boundary

Properties of integral operators with weak singularities arc investigated. It is assumed that G ? ?ⁿ is a bounded domain. The boundary δG should be smooth concerning the Sobolev trace theorem. It will be proved that the integral operators $\int {_G \frac{{f\left(\Theta \right)}}{{x - y|^{n - 1} }}u\left(\nu \right)d\partial G_\nu }$ and $ \int {_{\partial G} \frac{{f\left(\Theta \right)}}{{|x - y|^{n - 1} }}u\left(y \right)d\partial G_y }$ maps W_p^k(G) into W_p^k+1(G) and W_p^k?1(G) into W_p^k/p(G), respectively, and are bounded. Here θ ∈ S ? ?ⁿ, where S is the unit sphere. Furthermore, f possesses bounded first order derivatives and is bounded on S. Then applications to first order systems are discussed.     

The spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups

A ternary quasigroup (or 3‐quasigroup) is a pair (N, q) where N is an n‐set and q(x, y, z) is a ternary operation on N with unique solvability. A 3‐quasigroup is called 2‐idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x)=y. A conjugation of a 3‐quasigroup, considered as an OA(3, 4, n), $({{N}},{\mathcal{B}})$, is a permutation of the coordinate positions applied to the 4‐tuples of ${\mathcal{B}}$. The subgroup of conjugations under which $({{N}},{\mathcal{B}})$ is invariant is called the conjugate invariant subgroup of $({{N}},{\mathcal{B}})$. In this article, we determined the existence of 2‐idempotent 3‐quasigroups of order n, n≡7 or 11 (mod 12) and n≥11, with conjugate invariant subgroup consisting of a single cycle of length three. This result completely determined the spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups. As a corollary, we proved that an overlarge set of Mendelsohn triple system of order n exists if and only if n≡0, 1 (mod 3) and n≠6. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 292–304, 2010     

Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel

Let k be an arbitrary field, X₁,….,X_n indeterminates over k and F₁…, F₃ ε ∈ k[X₁…,X_n] polynomials of maximal degree $ d: = \mathop {\max }\limits_{1 \le i \le a} \deg $ (F_i). We give an elementary proof of the following effective Nullstellensatz: Assume that F₁,…,F have no common zero in the algebraic closure of k. Then there exist polynomials P₁…, P₃ ε ∈ k[X₁…,X_n] such that $ 1: = \mathop \Sigma \limits_{1 \le i \le a} $ P_iF_i and This result has many applications in Computer Algebra. To exemplify this, we give an effective quantitative and algorithmic version of the Quillen-Suslin Theorem baaed on our effective Nullstellensatz.     

Strengths and Weaknesses of LH Arithmetic

In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2^s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.     

Comparing Packing Measures to Hausdorff Measures on the Line

For each 0 < s < 1, define where , denote respectively the s‐dimensional packing measure and Hausdorff measure, and the infimum is taken over all the sets E ⊂ R with . In this paper we give a nontrivial estimation of c(s), namely, for each 0 < s < 1, where . As an application, we obtain a lower density theorem for Hausdorff measures.     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

Periodic problem for a nonlinear‐damped wave equation on the boundary

In this work we investigate the existence of periodic solutions in t for the following problem: We employ elliptic regularization and monotone method. We consider $\mbox{\boldmath{$\Omega$}}\mbox{\boldmath{$\subset$}}{\mathbb{R}}^{{{n}}} \ (n\geqslant 1)$ an open bounded set that has regular boundary Γ and Q=Ω ×(0,T), T>0, a cylinder of ${\mathbb{R}}^{n+1}$ with lateral boundary Σ = Γ × (0,T). Copyright © 2009 John Wiley & Sons, Ltd.