Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

A note on hypergraphs with the Helly-property

Let H be a hypergraph and t a natural number. The sets which can be written and the union of different edges of H form a new hypergraph which is denoted by H′. Let us suppose that H has the Helly property and we want to state something similar for H′. We prove a conjecture of C, Berge and two negative results.     

On realizations of point determining graphs, and obstructions to full homomorphisms

A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations.A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H has ? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(?+1) vertices, and, when both k and ? are positive, there is at most one minimal H-obstruction with (k+1)(?+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.     

Spectra of coronae

We introduce a new invariant, the coronal of a graph, and use it to compute the spectrum of the corona G°H of two graphs G and H. In particular, we show that this spectrum is completely determined by the spectra of G and H and the coronal of H. Previous work has computed the spectrum of a corona only in the case that H is regular. We then explicitly compute the coronals for several families of graphs, including regular graphs, complete n-partite graphs, and paths. Finally, we use the corona construction to generate many infinite families of pairs of cospectral graphs.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

A study of cut points in connected topological spaces

We prove that every H(i) subset H of a connected space X such that there is no proper connected subset of X containing H, contains at least two non-cut points of X. This is used to prove that a connected space X is a COTS with endpoints if and only if X has at most two non-cut points and has an H(i) subset H such that there is no proper connected subset of X containing H. Also we obtain some other characterizations of COTS with endpoints and some characterizations of the closed unit interval.     

Frobenius-Schur indicators and exponents of spherical categories

We obtain two formulae for the higher Frobenius-Schur indicators: one for a spherical fusion category in terms of the twist of its center and the other one for a modular tensor category in terms of its twist. The first one is a categorical generalization of an analogous result by Kashina, Sommerhäuser, and Zhu for Hopf algebras, and the second one extends Bantay's 2nd indicator formula for a conformal field theory to higher degrees. These formulae imply the sequence of higher indicators of an object in these categories is periodic. We define the notion of Frobenius-Schur (FS-)exponent of a pivotal category to be the global period of all these sequences of higher indicators, and we prove that the FS-exponent of a spherical fusion category is equal to the order of the twist of its center. Consequently, the FS-exponent of a spherical fusion category is a multiple of its exponent, in the sense of Etingof, by a factor not greater than 2. As applications of these results, we prove that the exponent and the dimension of a semisimple quasi-Hopf algebra H have the same prime divisors, which answers two questions of Etingof and Gelaki affirmatively for quasi-Hopf algebras. Moreover, we prove that the FS-exponent of H divides dim⁴(H). In addition, if H is a group-theoretic quasi-Hopf algebra, the FS-exponent of H divides dim²(H), and this upper bound is shown to be tight.     

Degree of convergence of modified averaged iterations for fixed points problems and operator equations

Let H be a real Hilbert space. We propose a modification for averaged mappings to approximate the unique fixed point of a mapping T:H→H such that T is boundedly Lipschitzian and −T is monotone. We not only prove strong convergence theorems, but also determine the degree of convergence. Using this result, an iteration process is given for finding the unique solution of the equation Ax=f, where A:H→H is strongly monotone and boundedly Lipschitzian.     

Hilbert space representations of decoherence functionals and quantum measures

We show that any decoherence functional D can be represented by a spanning vector-valued measure on a complex Hilbert space. Moreover, this representation is unique up to an isomorphism when the system is finite. We consider the natural map U from the history Hilbert space K to the standard Hilbert space H of the usual quantum formulation. We show that U is an isomorphism from K onto a closed subspace of H and that U is an isomorphism from K onto H if and only if the representation is spanning. We then apply this work to show that a quantum measure has a Hilbert space representation if and only if it is strongly positive. We also discuss classical decoherence functionals, operator-valued measures and quantum operator measures.     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

A merit function method for infinite-dimensional SOCCPs

We introduce the Jordan product associated with the second-order cone K into the real Hilbert space H, and then define a one-parametric class of complementarity functions Φt on H×H with the parameter t∈[0,2). We show that the squared norm of Φt with t∈(0,2) is a continuously F(réchet)-differentiable merit function. By this, the second-order cone complementarity problem (SOCCP) in H can be converted into an unconstrained smooth minimization problem involving this class of merit functions, and furthermore, under the monotonicity assumption, every stationary point of this minimization problem is shown to be a solution of the SOCCP.     

Brooks' graph-coloring theorem and the independence number

Let h denote the maximum degree of a connected graph H, and let _χ(H) denote its chromatic, number. Brooks' Theorem asserts that if h ≥ 3, then _χ(H) ≤ h, unless H is the complete graph K_h+1. We show that when H is not K_h+1, there is an h-coloring of H in which a maximum independent set is monochromatic. We characterize those graphs H having an h-coloring in which some color class consists of vertices of degree h in H. Again, without any loss of generality, this color class may be assumed to be maximum with respect to the condition that its vertices have degree h.     

The Birman-Schwinger principle on the essential spectrum

Let H₀ and H be self-adjoint operators in a Hilbert space. We consider the spectral projections of H₀ and H corresponding to a semi-infinite interval of the real line. We discuss the index of this pair of spectral projections and prove an identity which extends the Birman-Schwinger principle onto the essential spectrum. We also relate this index to the spectrum of the scattering matrix for the pair H₀, H.     

Binary relations and reduced hypergroups

Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρ∩σ, ρ∪σ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.     

Negative correlation between power-law scaling and Hurst exponents in long-range connective sandpile models and real seismicity

We propose a generic negative correlation between power-law scaling and Hurst exponents for size/magnitude data from real and synthetic earthquakes. The synthetic earthquakes were produced from a conceptual earthquake model, the long-range connective sandpile (LRCS) model. The LRCS model is a new modification of sandpile models that considers the random distant connection between two separated cells instead of neighboring cells. We calculated the Hurst exponent H and the power-law scaling exponent B for event size data in the LRCS model. We systematically explored the relationships between these two exponents (H and B) and conclusively obtained a negative correlation between H and B. We also found this negative correlation for real earthquake data registered in the Taiwan Central Weather Bureau (CWB) catalog. This negative correlation has not been demonstrated previously for real seismicity, although it has been frequently suggested.     

On strong joins and pushout of combinatorial geometries

The strong join of two geometries G and H relative to a common subgeometry is a geometry on the point set (G ? x)∪(H ? x)∪x, the closed sets k of which have the property that k ∩ G is closed in the geometry G and k ∩ H is closed in the geometry H. The strong join does not always exist, but if x is a modular flat of G (or H) it does exist. This was proved by Brylawski in his interesting paper “Modular constructions for combinatorial geometries” [1]. We shall show that if one wants the strong join to exist for all H which contain x as a subgeometry, then x must be a modular flat of G. We also show that the concepts strong join and injective pushout defined in [1] are identical.     

On the Heterochromatic Number of Hypergraphs Associated to Geometric Graphs and to Matroids

The heterochromatic number h _c (H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by ν(H) the number of vertices of H and by τ(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n ≥ 3 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then h _c (H) = ν(H) ? τ(H) + 2. We also show that h _c (H) = ν(H) ? τ(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.     

Representations for Moore-Penrose inverses in Hilbert spaces

Let H₁, H₂ be two Hilbert spaces, and let T : H₁ → H₂ be a bounded linear operator with closed range. We present some representations of the perturbation for the Moore-Penrose inverse in Hilbert spaces for the case that the perturbation does not change the range or the null space of the operator.     

On a conjecture of Meyniel

A graph G is said to be very strongly perfect if for each induced subgraph H of G, each vertex of H belongs to a stable set that meets all maximal cliques of H. Meyniel proved that a graph is perfect if each of its odd cycles with at least five vertices contains at least two chords. Nowadays, such a graph is called a Meyniel graph. We prove that, as conjectured by Meyniel, a graph is very strongly perfect if and only if it is a Meyniel graph. We also design a polynomial-time algorithm which, given a Meyniel graph G and a vertex x of G, finds a stable set that contains x and meets all maximal cliques of G. We shall convert this algorithm into another polynomial-time algorithm which, given a Meyniel graph G, finds an optimal coloring of G, and a largest clique of G. Finally, we shall establish another property, related to perfection, of Meyniel graphs.