A Rao-type characterization for a sequence to have a realization containing a split graph

For a given graph H, a non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. The split graph on r+s vertices is denoted by S_r,s. In this paper, we give a Rao-type characterization for π to be potentially S_r,s-graphic. A simplification of this characterization is also presented.     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Conditions for -graphic sequences to be potentially -graphic

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].     

A characterization for a graphic sequence to be potentially C r -graphic

Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.     

The Characterization for a Graphic Sequence to have a Realization Containing K 1,1,s

A graphic sequence π?=?(d ₁, d ₂, . . . , d _n ) is said to be potentially K _1,1,s -graphic if there is a realization of π containing K _1,1,s as a subgraph, where K _1,1,s is the 1?× 1?× s complete 3-partite graph. In this paper, a simple characterization of potentially K _1,1,s -graphic sequences for s?≥ 2 and n?≥ 3s?+?1 is obtained. This characterization implies Lai’s conjecture on σ(K _1,1,s , n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ(K _2,s , n) for s?≥ 4 and n?≥ 3s?+?1, where K _2,s is the 2?× s complete bipartite graph.     

有一个实现包含Kr +1的可图序列

设K _{r +1}是一个r +1个顶点的完全图. 一个可图序列π =(d₁, d₂,…, d_n)称为是蕴含K _r+1 -可图的, 如果π有一个实现包含 K _{r +1}作为子图. 该文进一步研究了蕴含K _{r+1 -}可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n≥5r/2 +1时,σ(K _r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n≥5, d₅≥4 且不蕴含K₅ -可图序列π=(d₁, d₂,…, d_n)的集合.     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of  \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

Polynomial approximation inL p(S) forp>0

For a simple polytopeS inR ^d andp>0 we show that the best polynomial approximationE _n(f)_p≡E_n(f)L_p(S) satisfies $$E_n \left( f \right)_p \leqslant C\omega _S^r \left( {f,\frac{1}{n}} \right)p,$$ where ω _S ^r is a measure of smoothness off. This result is the best possible in the sense that a weak-type converse inequality is shown and a realization of ω _S ^r (f,t)_p via polynomial approximation is proved.     

On the gonality sequence of an algebraic curve

For any smooth irreducible projective curve X, the gonality sequence ${\{d_r \;| \; r \in \mathbb N\}}$ is a strictly increasing sequence of positive integer invariants of X. In most known cases d _r+1 is not much bigger than d _r . In our terminology this means the numbers d _r satisfy the slope inequality. It is the aim of this paper to study cases when this is not true. We give examples for this of extremal curves in ${{\mathbb P}^r}$ , for curves on a general K3-surface in ${{\mathbb P}^r}$ and for complete intersections in ${{\mathbb P}^3}$ .     

Linear deviations of the classes\tilde W_p^\alpha and approximations in spaces of multipliers

We consider the problem of the asymptotically best linear method of approximation in the metric of L_s[?π, π] of the set \(\tilde W_p^\alpha (1)\) of periodic functions with a bounded in L_p[?π, π] fractional derivative, by functions from \(\tilde W_p^\beta (M)\) ,β >α, for sufficiently large M, and the problem about the best approximation in L_s[?π, π] of the operator of differentiation on \(\tilde W_p^\alpha (1)\) by continuous linear operators whose norm (as operators from L_r[?π, π] into L_q[?π, π])does not exceed M. These problems are reduced to the approximation of an individual element in the space of multipliers, and this allows us to obtain estimates that are exact in the sense of the order.     

Several generalizations of Tverberg’s theorem

In a generalization of Radon’s theorem, Tverberg showed that each setS of at least (d+1) (r ? 1)+1 points inR ^d has anr-partition into (pair wise disjoint) subsetsS =S ₁ ∪ … ∪S _r so that \(\bigcap\nolimits_i^r {\underline{\underline {}} } _1 \) convS _i # Ø. This note considers the following more general problems: (1) How large mustS σR ^d be to assure thatS has anr-partitionS=S ₁∪ … ∪S _r so that eachn members of the family {convS _i ～ _i-1 ^r have non-empty intersection, where 1<=n<=r. (2) How large mustS ∪R ^d be to assure thatS has anr-partition for which \(\bigcap\nolimits_i^r {\underline{\underline {}} } _1 \) convS _r is at least 1-dimensional.     

The error term in Nevanlinna’s inequality

An upper bound is given for the error termS(r, |a _j |,f) in Nevanlinna’s inequality. For given positive increasing functions p and $ with ∫ ₁ ^∞ dr/p(r) = ∫ ₁ ^∞ dr/r ?(r) = ∞, setP(r) = ∫ ₁ ^r dt/p,Ψ(r) = ∫ ₁ ^r dt/t ?(t) We prove that $$S(r, \left\{ {a_j } \right\}, f) \leqslant \log \frac{{T(r, f)\phi (T(r, f))}}{{p(r)}} + O(1)$$ holds, with a small exceptional set of r, for any finite set of points |a _j | in the extended plane and any meromorphic function f such thatΨ(T(r, f)) =O(P(r)). This improves the known results of A. Hinkkanen and Y. F. Wang. The sharpness of the estimate is also considered.     

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 σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Graphic Sequences with an A-Connected Realization

A non-increasing sequence \({\pi = (d_1, d_2, \ldots, d_n)}\) of non-negative integers is said to be graphic if it is the degree sequence of a simple graph G on n vertices. Let A be an (additive) abelian group. An extremal problem for a graphic sequence to have an A-connected realization is considered as follows: determine the smallest even integer \({\sigma (A, n)}\) such that each graphic sequence \({\pi = (d_1, d_2, \ldots, d_n)}\) with d _n ≥ 2 and \({\sigma (\pi) = d_1 + d_2 + \cdots +d_n \ge \sigma (A, n)}\) has an A-connected realization. In this paper, we determine \({\sigma (A, n)}\) for |A| ≥ 5 and n ≥ 3.     

The de Bruijn–Erd?s theorem for hypergraphs

Fix integers n ≥ r ≥ 2. A clique partition of ${{[n] \choose r}}$ is a collection of proper subsets ${A_1, A_2, \ldots, A_t \subset [n]}$ such that ${\bigcup_i{A_i \choose r}}$ is a partition of ${{[n]\choose r}}$ . Let cp(n, r) denote the minimum size of a clique partition of ${{[n] \choose r}}$ . A classical theorem of de Bruijn and Erd?s states that cp(n, 2) =?n. In this paper we study cp(n, r), and show in general that for each fixed r ≥ 3, $${\rm cp}(n, r) \geq (1 + o(1))n^{r/2} \quad \quad {\rm as} \, \, n \rightarrow \infty.$$ We conjecture cp(n, r) =?(1 +?o(1))n ^r/2. This conjecture has already been verified (in a very strong sense) for r = 3 by Hartman–Mullin–Stinson. We give further evidence of this conjecture by constructing, for each r ≥ 4, a family of (1?+?o(1))n ^r/2 subsets of [n] with the following property: no two r-sets of [n] are covered more than once and all but o(n ^r ) of the r-sets of [n] are covered. We also give an absolute lower bound ${{\rm cp}(n, r) \geq {n \choose r}/{q + r - 1 \choose r}}$ when n =?q ² + q +?r ? 1, and for each r characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of cp(n, r) to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.     

The supertail of a subspace partition

Let V = V(n, q) be a vector space of dimension n over the finite field with q elements, and let d ₁ < d ₂ < ... < d _m be the dimensions that occur in a subspace partition ${\mathcal{P}}$ of V. Let σ _q (n, t) denote the minimum size of a subspace partition ${\mathcal P}$ of V, in which t is the largest dimension of a subspace. For any integer s, with 1 < s ≤ m, the set of subspaces in ${\mathcal{P}}$ of dimension less than d _s is called the s-supertail of ${\mathcal{P}}$ . The main result is that the number of spaces in an s-supertail is at least σ _q (d _s , d _s?1).     

Estimate for index of hypersurfaces in spheres with null higher order mean curvature

In a recent paper (Barros, Sousa in: Kodai Math. J. 2009) the authors proved that closed oriented non-totally geodesic minimal hypersurfaces of the Euclidean unit sphere have index of stability greater than or equal to n + 3 with equality occurring at only Clifford tori provided their second fundamental forms A satisfy the pinching: |A|² ≥ n. The natural generalization for this pinching is ?(r + 2)S _r+2 ≥ (n ? r)S _r  > 0. Under this condition we shall extend such result for closed oriented hypersurface Σ ⁿ of the Euclidean unit sphere ${\mathbb{S}^{n+1}}$ with null S _r+1 mean curvature by showing that the index of r-stability, ${Ind_{\Sigma^n}^{r}}$ , also satisfies ${Ind_{\Sigma^n}^{r}\ge n+3}$ . Instead of the previous hypothesis if we consider ${\frac{S_{r+2}}{{S_r}}}$ constant we have the same conclusion. Moreover, we shall prove that, up to Clifford tori, closed oriented hypersurfaces ${\Sigma^{n}\subset \mathbb{S}^{n+1}}$ with S _r+1 = 0 and S _r+2 < 0 have index of r-stability greater than or equal to 2n + 5.     

Deviation of best discrete and uniform polynomial approximants

ПустьC _2π — пространств о 2π-периодических вещественных непрер ывных функций, W{_rLip α={f∈C _2π ^r : ω(f ^(r), δ)≦δ^α}, Y?[?π,π] — некоторое дискр етное множество точе к на периоде, плотность ко торого задается соот ношением ?(Y)= max min ¦x-у¦. Дляf∈C_2π x∈[?π,π] y∈Y обозначим через p_k(f) p_k(f)_y т ригонометрические полиномы степени не в ышеk наилучшего чебышевского прибли жения функцииf на все м периоде и на дискретном множес тве Y соответственно. Тогда величина $$\Omega _{k,r + \alpha } (d) = \mathop {\sup }\limits_{f \in W_r Lip\alpha } \mathop {\sup }\limits_{\mathop {Y \subset [ - \pi ,\pi ]}\limits_{\rho (Y) \leqq d} } \left\| {p_k (f) - p_k (f)_Y } \right\| (d > 0)$$ xарактеризует отклон ение наилучших равно мерных и дискретных чебышевс ких приближений равномерно на классе функций W_rLip а. В работе да ются точные оценки для ?_k,r+α(d) пр и всехk, r и 0-?1.