Box-total dual integrality and edge-connectivity

Mathematical Programming - Given a graph $$G=(V,E)$$ and an integer $$k\ge 1$$ , the graph $$H=(V,F)$$ , where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected...     

On a Problem of Potentially Pancyclic-graphic Sequences Due to S.B. Rao

Acta Mathematicae Applicatae Sinica, English Series - A non-increasing sequence π = (d1, d2,..., dn) of nonnegative integers is said to be potentially hamiltonian-graphic (resp. potentially...     

Coverings and structure of crossing families

The second problem we consider is to find a compact representation of F. We prove that there exists a so-called hypercactus K of size O(|V|), consisting of cycles and (hyper)edges arranged in a tree-like manner, and a mapping from V to V(K) in such a way that there is a bijection between the minimum cuts of K and the members of F. If F corresponds to the minimum cuts of a k-edge-connected graph then K reduces to the well-known cactus representation of minimum cuts due to Dinitz et al. Received September 1995 / Revised version received March 1997 Published online March 16, 1999     

Rao's conjecture on self-complementary graphs with K-factors

Rao posed the following conjecture, “Let G be a self-complementary graph of order p, π = (d₁ … dp) be its degree sequence. Then G has a k-factor if and only if π ? k, = (d1 ? k, … dP ? k) is graphical.” We construct a family of counterexamples for this conjecture for every k ? 3.     

A New Lower Bound on the Potential-Ramsey Number of Two Graphs

A nonincreasing sequenceπ=(d1,…,dn)of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.In this case,G is referred to as a realization ofπ.Given a graph H,a graphic sequenceπis potentially H-graphic ifπhas a realization containing H as a subgraph.For graphs G1 and G2,the potential-Ramsey number rpot(G1,G2)is the smallest integer k such that for every k-term graphic sequenceπ,eitherπis potentially G1-graphic or the complementary sequenceπ=(k-1-dk,…,k-1-d1)is potentially G2-graphic.For 0≤k≤[t/2],denote Kt-k to be the graph obtained from Kt by deleting k independent edges.If k=0,Busch et al.(Graphs Combin.,30(2014)847-859)present a lower bound on rpot(G,Kt)by using the 1-dependence number of G.In this paper,we utilize i-dependence number of G for i≥1 to give a new lower bound on rpot(G,Kt-k)for any k with 0≤k≤[T/2].Moreover,we also determine the exact values of rpot(Kn,Kt-k)for 1≤k≤2.     

The potential-Ramsey number of Kn and K t −k

Czechoslovak Mathematical Journal - A nonincreasing sequence π = (d1,…, dn) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices. In this...     

开曲面凸性判别条件(一)

<正> 给定一曲面片,问:在什么条件下它是凸的?如果一曲面称为“凸曲面”是以它能安装在某一个凸体的表面上作为定义的话,那么,进一步要问:它要满足什么样的条件才能安装在某个凸体的表面上呢? 如果曲面π是封闭曲面,问题早已解决,即封闭曲面π是凸曲面的充要条件是:π对其所包围的有界域D而言是点点局部凸的,即π上每个点都有对D——因而对π——有     

Graded Quantum Groups and Quasitriangular Hopf Group-Coalgebras

ABSTRACT

Starting from a Hopf algebra endowed with an action of a group π by Hopf automorphisms, we construct (by a “twisted” double method) a quasitriangular Hopf π-coalgebra. This method allows us to obtain non-trivial examples of quasitriangular Hopf π-coalgebras for any finite group π and for infinite groups π such as GL _n (𝕂). In particular, we define the graded quantum groups, which are Hopf π-coalgebras for π = ?[[h]] ^l and generalize the Drinfeld-Jimbo quantum enveloping algebras.     

Variable Selection Diagnostics Measures for High-Dimensional Regression

Markov chain Monte Carlo (MCMC) is nowadays a standard approach to numerical computation of integrals of the posterior density π of the parameter vector η. Unfortunately, Bayesian inference using MCMC is computationally intractable when the posterior density π is expensive to evaluate. In many such problems, it is possible to identify a minimal subvector β of η responsible for the expensive computation in the evaluation of π. We propose two approaches, DOSKA and INDA, that approximate π by interpolation in ways that exploit this computational structure to mitigate the curse of dimensionality. DOSKA interpolates π directly while INDA interpolates π indirectly by interpolating functions, for example, a regression function, upon which π depends. Our primary contribution is derivation of a Gaussian processes interpolant that provably improves over some of the existing approaches by reducing the effective dimension of the interpolation problem from dim(η) to dim(β). This allows a dramatic reduction of the number of expensive evaluations necessary to construct an accurate approximation of π when dim(η) is high but dim(β) is low.

We illustrate the proposed approaches in a case study for a spatio-temporal linear model for air pollution data in the greater Boston area.

Supplemental materials include proofs, details, and software implementation of the proposed procedures.     

Quasi-Affinity for Unbounded Representations

Quasi-affinity for unbounded representations are introduced and it is shown that, if a self-adjoint representation π is quasi-affine to a *-representation ?, then ? is also self-adjoint and π and ? are unitarily equivalent.     

Cores of partitioning games

A generalization of assignment games, called partitioning games, is introduced. Given a finite set N of players, there is an a priori given set π of coalitions of N and only coalitions in π play an essential role. Necessary and sufficient conditions for the nonemptiness of the cores of all games with essential coalitions π are developed. These conditions appear extremely restrictive. However when N is ‘large’, there are relatively few ‘types’ of players, and members of π are ‘small’ and defined in terms of numbers of players of each type contained in subsets, then approximate cores are nonempty.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r, n) such that every n-term graphic sequence π = (d1, d2,..., dn) with term sum σ(π) = d1 + d2 +…+ dn ≥σ(Kr,r, n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. πr has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.     

蕴含W_6-可图序列

对于给定的图H,如果可图序列π有一个实现包含H作为子图,则称π是蕴含H-可图的.本文给出了可图序列π蕴含W_6-可图的一个充分条件,其中W_r是r个顶点的轮图.     

蕴含W6-可图序列

摘要对于给定的图日,如果可图序列π有一个实现包含日作为子图,则称丌是蕴含H-可图的．本文给出了可图序列π蕴含W6-可图的一个充分条件,其中Wτ是τ个顶点的轮图．     

Paths in graphs and minimal π-sequences in semigroups

By taking a graph theoretic point of view, the author's theory of minimal sequences in semi groups is generalized to minimal π-sequences, where π is any positive quasi-order on the semi group. This generalization is especially complete when π is a linear quasi-order. Finally some possible future applications to the social sciences are considered.     

Asymptotics of functions satisfying the γ-weak inequality with applications to uniformly bounded representations

Let G be a real reductive group of class $\text{H}$, and π a uniformly bounded representation of G on a Hilbert space having infinitesimal character. We then show that the K-finite matrix elements of π decay “exponentially” on G provided that the infinitesimal character of π is in general position. Further we show that π is infinitesimally equivalent to a subquotient of a cuspidal principal series representation π_Q,ω,ν where ν belongs to a tube domain defined by ?Q. These facts follow from the asymptotics of functions satisfying the γ-weak inequality.     

On the NP-hardness of edge-deletion and -contraction problems

If π is a property on graphs, the corresponding edge deletion (edge contraction, respectively) problem is: Given a graph G, determine the minimum number of edges of G whose deletion (contraction) results in a graph satisfying property π. We show that these problems are NP-hard if π is finitely characterizable by 3-connected graphs.     

On the removal of forbidden graphs by edge-deletion or by edge-contraction

If π is a property on graphs, the corresponding edge deletion (edge contraction, respectively) problem is: Given a graph G, determine the minimum number of edges of G whose deletion (contraction) results in a graph satisfying property π. We show that these problems are NP-hard if π is finitely characterizable by 3-connected graphs.     

开曲面的凸性判别条件(二)

<正> 在本文(一)中我们给出了一个开曲面为凸曲面的充分必要条件.现在我们试图给出另一个判别条件.这里的记号以及局部凸的定义都与本文(一)的相同.我们先证明一个引理: 引理 设π为单连通的曲面,以γ为其周界,π是点点局部凸的.假设对于任一属于int π的点P,都至少有一个局部支持平面,记作S_p,使得S_p对周界γ有γS_p∪S_p~-.那么我们有γγ.当γ不在一个平面上时,γ~°是三维欧氏空间中的凸区域.这时γ°上     

实现同一度序列的图的最大团数

图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法．