On a class of secant-like methods for solving nonlinear equations

We provide a semilocal convergence analysis for a certain class of secant-like methods considered also in Argyros (J Math Anal Appl 298:374–397, 2004, 2007), Potra (Libertas Mathematica 5:71–84, 1985), in order to approximate a locally unique solution of an equation in a Banach space. Using a combination of Lipschitz and center-Lipschitz conditions for the computation of the upper bounds on the inverses of the linear operators involved, instead of only Lipschitz conditions (Potra, Libertas Mathematica 5:71–84, 1985), we provide an analysis with the following advantages over the work in Potra (Libertas Mathematica 5:71–84, 1985) which improved the works in Bosarge and Falb (J Optim Theory Appl 4:156–166, 1969, Numer Math 14:264–286, 1970), Dennis (SIAM J Numer Anal 6(3):493–507, 1969, 1971), Kornstaedt (1975), Larsonen (Ann Acad Sci Fenn, A 450:1–10, 1969), Potra (L’Analyse Numérique et la Théorie de l’Approximation 8(2):203–214, 1979, Aplikace Mathematiky 26:111–120, 1981, 1982, Libertas Mathematica 5:71–84, 1985), Potra and Pták (Math Scand 46:236–250, 1980, Numer Func Anal Optim 2(1):107–120, 1980), Schmidt (Period Math Hung 9(3):241–247, 1978), Schmidt and Schwetlick (Computing 3:215–226, 1968), Traub (1964), Wolfe (Numer Math 31:153–174, 1978): larger convergence domain; weaker sufficient convergence conditions, finer error bounds on the distances involved, and a more precise information on the location of the solution. Numerical examples further validating the results are also provided.     

Tetravalent half-arc-transitive graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2p ² exist and a tetravalent half-arc-transitive graph of order 4p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41–76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2pq are classified for distinct odd primes p and q.     

Rectifiability of Sets of Finite Perimeter in Carnot Groups: Existence of a Tangent Hyperplane

We consider sets of locally finite perimeter in Carnot groups. We show that if E is a set of locally finite perimeter in a Carnot group G then, for almost every x∈G with respect to the perimeter measure of E, some tangent of E at x is a vertical halfspace. This is a partial extension of a theorem of Franchi-Serapioni-Serra Cassano in step 2 Carnot groups: they show in Math. Ann. 321, 479–531, 2001 and J. Geom. Anal. 13, 421–466, 2003 that, for almost every x, E has a unique tangent at x, and this tangent is a vertical halfspace. The second author was partially supported by NSF grant DMS-0701515.     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Extending partial isomorphisms for the small index property of many ω-categorical structures

Theorem:Let A be a finite K _m -free graph, p ₁ , …, p _n partial isomorphisms on A. Then there exists a finite extension B, which is also a K _m -free graph, and automorphisms f _i of B extending the p _i . A paper by Hodges, Hodkinson, Lascar and Shelah shows how this theorem can be used to prove the small index property for the generic countable graph of this class. The same method also works for a certain class of continuum many non-isomorphic ω-categorical countable digraphs and more generally for structures in an arbitrary finite relational language, which are built in a similar fashion. Hrushovski proved this theorem for the class of all finite graphs [Hr]; the proof presented here stems from his proof. Supported by EC-grant ERBCHBGCT 920013.     

Distributive Lattices with a Generalized Implication: Topological Duality

In this paper we introduce the notion of generalized implication for lattices, as a binary function ⇒ that maps every pair of elements of a lattice to an ideal. We prove that a bounded lattice A is distributive if and only if there exists a generalized implication ⇒ defined in A satisfying certain conditions, and we study the class of bounded distributive lattices A endowed with a generalized implication as a common abstraction of the notions of annihilator (Mandelker, Duke Math J 37:377–386, 1970), Quasi-modal algebras (Celani, Math Bohem 126:721–736, 2001), and weakly Heyting algebras (Celani and Jansana, Math Log Q 51:219–246, 2005). We introduce the suitable notions of morphisms in order to obtain a category, as well as the corresponding notion of congruence. We develop a Priestley style topological duality for the bounded distributive lattices with a generalized implication. This duality generalizes the duality given in Celani and Jansana (Math Log Q 51:219–246, 2005) for weakly Heyting algebras and the duality given in Celani (Math Bohem 126:721–736, 2001) for Quasi-modal algebras.     

Growth-type invariants for ℤ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> subshifts of finite type and arithmetical classes of real numbers

We discuss some numerical invariants of multidimensional shifts of finite type (SFTs) which are associated with the growth rates of the number of admissible finite configurations. Extending an unpublished example of Tsirelson (A strange two-dimensional symbolic system, 1992), we show that growth complexities of the form exp (n ^α+o(1)) are possible for non-integer α’s. In terminology of de Carvalho (Port. Math. 54(1):19–40, 1997), such subshifts have entropy dimension α. The class of possible α’s are identified in terms of arithmetical classes of real numbers of Weihrauch and Zheng (Math. Log. Q. 47(1):51–65, 2001).     

An Index Theorem for Band-Dominated Operators with Slowly Oscillating Coefficients (after Deundyak and Shteinberg)

We provide a proof of an index theorem for band-dominated operators with slowly oscillating coefficients. The statement is essentially the same as the main result of the announcement of Deundyak and Shteinberg (Funct Anal Appl 19(4):321–323, 1985), but our methods are very different from those hinted at there. The index theorem we prove can also be seen as a partial generalization to higher dimensions of the main result of the article of Rabinovich et al. (Integr Equ Oper Theory 49:221–238, 2004).     

On directed graphs with an independent covering set

We prove that if a directed graph,D, contains no odd directed cycle and, for all but finitely many vertices, EITHER the in-degrees are finite OR the out-degrees are at most one, thenD contains an independent covering set (i.e. there is a kernel). We also give an example of a countable directed graph which has no directed cycle, each vertex has out-degree at most two, and which has no independent covering set.Research supported by N.S.E.R.C. grants #69-0982 and #69-0259.     

A new approach to chordal graphs

By a chordal graph is meant a graph with no induced cycle of length ⩾ 4. By a ternary system is meant an ordered pair (W, T), where W is a finite nonempty set, and T ⊆ W × W × W. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set W, a bijective mapping from the set of all connected chordal graphs G with V(G) = W onto the set of all ternary systems (W, T) satisfying the axioms (A1)–(A5) is found in this paper.     

Frucht theorem for inverse semigroups

In the paper, the problem of representing a finite inverse semigroup by partial transformations of a graph is treated. The notions of weighted graph and its weighted partial isomorphisms are introduced. The main result is that any finite inverse semigroup is isomorphic to the semigroup of weighted partial isomorphisms of a weighted graph. This assertion is a natural generalization of the Frucht theorem for groups. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 246–251, February, 1997. This research was partially supported by the International Science Foundation under grant No. GSU 041049. Translated by A. I. Shtern     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

An FIO calculus for marine seismic imaging, II: Sobolev estimates

We establish sharp L ²-Sobolev estimates for classes of pseudodifferential operators with singular symbols [Guillemin and Uhlmann (Duke Math J 48:251–267, 1981), Melrose and Uhlmann (Commun Pure Appl Math 32:483–519, 1979)] whose non-pseudodifferential (Fourier integral operator) parts exhibit two-sided fold singularities. The operators considered include both singular integral operators along curves in \mathbb R²{\mathbb R^2} with simple inflection points and normal operators arising in linearized seismic imaging in the presence of fold caustics [Felea (Comm PDE 30:1717–1740, 2005), Felea and Greenleaf (Comm PDE 33:45–77, 2008), Nolan (SIAM J Appl Math 61:659–672, 2000)].     

A fully benzenoid system has a unique maximum cardinality resonant set

A benzenoid system is a 2-connected plane graph such that its each inner face is a regular hexagon of side length 1. A benzenoid system is Kekuléan if it has a perfect matching. Let P be a set of hexagons of a Kekuléan benzenoid system B. The set P is called a resonant set of B if the hexagons in P are pair-wise disjoint and the subgraph B−P (obtained by deleting from B the vertices of the hexagons in P) is either empty or has a perfect matching. It was shown (Gutman in Wiss. Z. Thechn. Hochsch. Ilmenau 29:57–65, 1983; Zheng and Chen in Graphs Comb. 1:295–298, 1985) that for every maximum cardinality resonant set P of a Kekuléan benzenoid system B, the subgraph B−P is either empty or has a unique perfect matching. A Kekuléan benzenoid system B is said to be fully benzenoid if there exists a maximum cardinality resonant set P of B, such that the subgraph B−P is empty. It is shown that a fully benzenoid system has a unique maximum cardinality resonant set, a well-known statement that, so far, has remained without a rigorous proof.     

Paired-Domination in Subdivided Star-Free Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. In [Dorbec P, Gravier S, Henning MA, J Comb Optim 14(1):1–7, 2007], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced subdivided stars, depending on the size of the star.     

Weak Reflections and Weak Factorization Systems

We describe a one-to-one correspondence between saturated weak factorization systems and weak reflections in categories C\mathcal{C} with finite products. This actually extends to an adjunction between the category of natural weak factorization systems on C\mathcal{C} (in the sense of Grandis and Tholen, Arch Math 42:397–408, 2006, and Garner, arXiv preprint, 2007) and the category of monads on C\mathcal{C}. Explicit comparisons are made with the parallel result of Cassidy et al. (J Aust Math Soc 38:287–329, 1985), linking factorization systems and reflective subcategories.     

Straight-Line Rectangular Drawings of Clustered Graphs

We show that every c-planar clustered graph has a straight-line c-planar drawing in which each cluster is represented by an axis-parallel rectangle, thus solving a problem posed by Eades, Feng, Lin, and Nagamochi (Algorithmica 44(1):1–32, 2006).     

Functional BKR Inequalities,and their Duals,with Applications

The inequality conjectured by van den Berg and Kesten (J. Appl. Probab. 22, 556–569, 1985), and proved by Reimer (Comb. Probab. Comput. 9, 27–32, 2000), states that for A and B events on S, a finite product of finite sets, and P any product measure on S,

A new hybrid algorithm for a system of equilibrium problems and variational inclusion

The purpose of this paper is to consider a shrinking projection method of finding the common element of the set of common fixed points for a finite family of a ξ-strict pseudo-contraction, the set of solutions of a systems of equilibrium problems and the set of solutions of variational inclusions. Then, we prove strong convergence theorems of the iterative sequence generated by the shrinking projection method under some suitable conditions in a real Hilbert space. Our results improve and extend recent results announced by Peng, Wang, Shyu and Yao (J Inequal Appl, 2008:15, Article ID 720371, 2008), Takahashi, Takeuchi and Kubota (J Math Anal Appl 341:276–286, 2008), Takahashi and Takahashi (Nonlinear Anal 69:1025–1033, 2008) and many others.     

A Note About Critical Percolation on Finite Graphs

In this note we study the geometry of the largest component C₁\mathcal {C}_{1} of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137–184, 2005). There it is shown that this component is of size n ^2/3, and here we show that its diameter is n ^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886–1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \mathbbZ_n^d\mathbb{Z}_{n}^{d} (with d large and n→∞) and the Hamming cube {0,1} ⁿ .