The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

The chromatic index of graphs with a spanning star

Vizing's Theorem states that any graph G has chromatic index either the maximum degree Δ(G) or Δ(G) + 1. If G has 2_s + 1 points and Δ(G) = 2s, a well-known necessary condition for the chromatic index to equal 2_s is that G have at most 2s² lines. Hilton conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s ? 2.     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

Verbal Subgroups and Subalgebras in Skew Fields

Let D be an arbitrary skew field and K a central subfield of D. We prove that D can be embedded in a skew field Δ such that w(Δ)=Δ for every nonempty Lie word w on a set of variables y₁,y₂,.?.?. with coefficients in K; moreover, we have for the multiplicative group Δ^* that v(Δ^*)=Δ^* for every nonempty word \(v=x_{1}^{\varepsilon_{1}}x_{2}^{\varepsilon_{2}}\ldots x_{n}^{\varepsilon_{n}}\) (?_i=±1; i=1,2,.?.?.,n).     

On a class of graphs with prescribed mean curvature

We study a class of quasilinear elliptic equations on the unit ball of ℝ ⁿ in the divergence form ∑ _j=1 ⁿ D _j{G(|x|²,|Du|²)D _j u} =H(|x|) and get estimates on the boundary by using a modified barrier-function technique of Bernstein. We establish a maximum principle for the gradients of solutions and get a global gradient estimate. We prove that solutions with constant boundary condition must be radial. Finally, we apply these results to graphs {(x,u(x)):x∈H ⁿ } whereu:H ⁿ →ℝ is a smooth map of then-hyperbolic spaceH ⁿ =B(0,1) with the metric to get the existence of graphs with radial prescribed mean curvature.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A class of (4,2)-disk pairs which are trivial

Suppose Δ?S³ is a ribbon disk and let D (Δ) denote the cononical properly embedded 2-disk obtained by pushing the interior of Δ into B⁴. A well-known conjecture states that the disk pair (B⁴, D(Δ)) is trivial provided the sphere pair ?(B⁴, D(Δ)) is trivial. We show here that the conjecture is true for those D(Δ) with the property that there is an embedded 2-disk, D²?S³, whose boundary is ?D(Δ) and which intersects Δ in ‘transverse double points’.     

The equality S1 = D = R

The new result of this paper is that for θ( x ; a )‐stable (a weakening of “T is stable”) we have S1[θ( x ; a )] = D[θ( x ; a ), L, ∞]. S1 is Hrushovski's rank. This is an improvement of a result of Kim and Pillay, who for simple theories under the (strong) assumption that either of the ranks be finite obtained the same identity. Only the first equality is new, the second equality is a result of Shelah from the seventies. We derive it by studying localizations of several rank functions, we get the following Main Theorem. Suppose that μ is regular satisfying μ ≥ |T|⁺, p is a finite type, and Δ is a set of formulas closed under Boolean operations. If either (a) R[p, Δ, μ⁺] < ∞ or (b) p is Δ‐stable and μ satisfies “for every sequence {μ_i : i < |Δ| + ?₀} of cardinals μ_i < μ we have that holds”, then S[p, Δ, μ⁺] = D[p, Δ, μ⁺] = R[p, Δ, μ⁺]. The S rank above is a localized version of Hrushovski's S1 rank. This rank, as well as our systematic use of local stability, allows us to get a more conceptual proof of the equality of D and R, which is an old result of Shelah. A particular (asymptotic) case of the theorem offers a new sufficient condition for the equality of S1 and D[·, L, ∞]. We also manage, due to a more general approach, to avoid some combinatorial difficulties present in Shelah's original exposition.     

Space complexity of random formulae in resolution

We study the space complexity of refuting unsatisfiable random k-CNFs in the Resolution proof system. We prove that for Δ ≥ 1 and any ϵ > 0, with high probability a random k-CNF over n variables and Δn clauses requires resolution clause space of Ω(n/Δ^1+ϵ). For constant Δ, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density Δ ≫ n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with Δn clauses requires treelike refutation size of exp(Ω(n/Δ^1+ϵ)), for any ϵ > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92–109, 2003     

On reduction of block matrices in a Hilbert space

We study the problem of the reduction of self-adjoint block matrices B = (B _ij ) with given graph by a group of unitary block diagonal matrices. Under the condition that the matrices B ² and B ⁴ are orthoscalar, we describe the graphs of block matrices for which this problem is a problem of *-finite, *-tame, or *-wild representation type.     

Randomly coloring graphs with lower bounds on girth and maximum degree

We consider the problem of generating a random q‐coloring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree Δ > c₁ln n and the girth g > c₂ln Δ (n = |V|) for sufficiently large c₁, c₂, then this chain mixes rapidly provided q/Δ > β, where β ≈ 1.763 is the root of β = e^1/β. For this class of graphs, this beats the 11Δ/6 bound of Vigoda 14 for general graphs. We extend the result to random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 167–179, 2003     

Relative distance between two scalar fields. Application to mathematical modelling approximation

Inspired in the relative error between two quantities, we define a functional Δ_D that operates on two non‐negative scalar fields, which are integrable in a given open connected set D. We prove that Δ_D defines a metric, but not an ultrametric nor a translation invariant metric. We show how to apply Δ_D to evaluate the performance of analytical approximations of PDEs. The principal advantage of using Δ_D instead of other distances given in the literature is that the value given by Δ_D has a very easy interpretation: a value close to 0 means relatively near, but a value close to 1 means relatively infinitely far. Copyright © 2013 John Wiley & Sons, Ltd.     

On the reconstruction of boolean algebras from their automorphism groups

A Boolean algebraB is called faithful, if for every direct summandB ₁ ofB: ifB ₁ is rigid, (that is, it does not have any automorphisms other than the identity), then there isB ₂ such thatBB ₁×B ₁×B ₁×B ₂. LetB be a complete Boolean algebra, thenB can be uniquely represented asBB ^R×B ^D×B ^D×B ^F, whereB ^R,B ^D,B ^F are pairwise totally different, (that is, no two of them have non-zero isomorphic direct summands),B ^R,B ^D are rigid andB ^F is faithful. Aut(B) denotes the automorphism group ofB.I thank the NSF for supporting this research by a grant.     

Edge intersection graphs of systems of paths on a grid with a bounded number of bends

We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n²) is needed. We also show several results related to the classes B_k-EPG, where B_k-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph K_m,n does not belong to B_2m−3-EPG (it is known that this graph belongs to B_2m−2-EPG); for any odd integer k we have B_k-EPG B_k+1-EPG; there is no number k such that all graphs belong to B_k-EPG; only 2^O(knlog(kn)) out of all the labeled graphs with n vertices are in B_k-EPG.     

A minimum principle for superharmonic functions subject to interface conditions

Let D be a bounded domain in R² with smooth boundary. Let B₁, …, B_m be non-intersecting smooth Jordan curves contained in D, and let D′ denote the complement of ∪_{i ? 1}^mB_i respect to D. Suppose that $\text{u ? C}{}^2\text{(D′) ∩ C(}\text{D}\text{?}$) and Δu ? 0 in D′ (where Δ is the Laplacian), while across each “interface” B_i, i = 1,…, m, there is “continuity of flux” (as suggested by the theory of heat conduction). It is proved here that the presence of the interfaces does not alter the conclusions of the classical minimum principle (for Δu ? 0 in D). The result is extended in several regards. Also it is applied to an elliptic free boundary problem and to the proof of uniqueness for steady-state heat conduction in a composite medium. Finally this minimum principle (which assumes “continuity of flux”) is compared with one due to Collatz and Werner which employs an alternative interface condition.     

Augmentation quotients for burnside rings of generalized dihedral groups

Let H be a finite abelian group of odd order, D be its generalized dihedral group, i.e., the semidirect product of C₂ acting on H by inverting elements, where C₂ is the cyclic group of order two. Let Ω (D) be the Burnside ring of D, Δ(D) be the augmentation ideal of Ω (D). Denote by Δⁿ(D) and Q_n(D) the nth power of Δ(D) and the nth consecutive quotient group Δⁿ(D)/Δⁿ⁺¹(D), respectively. This paper provides an explicit Z-basis for Δⁿ(D) and determines the isomorphism class of Q_n(D) for each positive integer n.     

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph KN with N?Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and edges, with N=⌈B^′n⌉ for some constant B^′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.