W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x,\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.     

五阶图与星图的笛卡尔积交叉数

In this paper, we compute the crossing number of a specific graph Hn, and then by contraction, we obtain the conclusion that cr（G13 × Sn） = 4[n/2] [n-1/2]＋[n/2] . The result fills up the blank of the crossing numbers of Cartesian products of stars with all 5-vertex graphs presented by Marian Klesc.     

K2,4×Sn的交叉数

Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图$K_{2,4}\times S_{n}$的交叉数是$Z(6,n)+4n.$ 当$m\geq 5,$猜想${\rm cr}(K_{2,m}\timesS_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor$.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

六阶图C_6+3K_2与P_n,C_n的联图交叉数

用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

$K_{5}\times S_{n}$ 的交叉数

把完全图$K_{5}$的五个顶点与另外$n$个顶点都联边得到一类特殊的图$H_{n}$.文中证明了$H_{n}$的交叉数为$Z(5,n)+2n+\lfloor \frac{n}{2}\rfloor+1$,并在此基础上证明了$K_{5}$与星$K_{1,n}$的笛卡尔积的交叉数为$Z(5,n)+5n+\lfloor\frac{n}{2} \rfloor+1$.     

Two classes of finite semigroups and monoids involving Lucas numbers

The class of finitely presented groups is an extension of the class of triangle groups studied recently. These groups are finite and their orders depend on the Lucas numbers. In this paper, by considering the three presentations

联图$K_5+P_n$的交叉数

A join graph denoted by G + H,is illustrated by connecting each vertex of graph G to each vertex of graph H.In this paper,we prove the crossing number of join product of K_5 + P_n is Z(5,n) + 2 n + [n/2] + 4 for n ≥ 2.     

树和单圈图的斜谱矩

给定图$G$,对图$G$的每条边确定一个方向,称为$G$的定向图$G^\sigma$, $G$称为$G^\sigma$的基础图. $G^\sigma$的斜邻接矩阵$S(G^\sigma)$是反对称矩阵,其特征值是0或纯虚数. $S(G^\sigma)$所有特征值的$k$次幂之和称为$G^\sigma$的$k$阶斜谱矩,其中$k$是非负整数.斜谱矩序列可用于对图进行排序.本文主要研究定向树和定向单圈图的斜谱矩,并对这两类图的斜谱矩序列依照字典序进行排序.首先确定了直径为$d$的树作为基础图的所有定向树中,斜谱矩序最大的$2\lfloor\frac{d}{4}\rfloor$个图; 然后确定以围长为$g$的单圈图作为基础图的所有定向单圈图中, 斜谱矩序最大的$2\lfloor\frac{g}{4}\rfloor+1$个图.     

A Note on the Largest Size of Families of Sets with a Forbidden Poset

Consider families of subsets of [n]:?=?{1,2,...,n} that do no contain a given poset P as a subposet. Let La(n, P) denote the largest size of such families and h(P) denote the height of P. The best known general upper bound for La(n, P) is $\left(\frac{1}{2}(|P|+h(P))-1\right)\left( \begin{array}{l}\,\,\,n \\ \lfloor \frac{n}{2} \rfloor\end{array}\right)$ , due to Bursi and Nagy (2012). This paper provides an improved upper bound $\frac{1}{m+1} \left(|P|+\frac{1}{2}(m^2+3m-2)(h(P)-1)-1\right) \left( \begin{array}{l} \,\,\,n \\ \lfloor \frac{n}{2} \rfloor\end{array}\right) $ , where m can be any positive integer less than $\lceil \frac{n}{2}\rceil$ .     

Reduction of symmetric semidefinite programs using the regular \ast-representation

We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix $*$ -representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K _8,n ) ≥ 2.9299n ² ? 6n, cr(K _9,n ) ≥ 3.8676n ² ? 8n, and (for any m ≥ 9) $$\lim_{n\to\infty}\frac{{\rm cr}(K_{m,n})}{Z(m,n)}\geq 0.8594\frac{m}{m-1},$$ where Z(m,n) is the Zarankiewicz number $\lfloor\frac{1}{4}(m-1)^2\rfloor\lfloor\frac{1}{4}(n-1)^2\rfloor$ , which is the conjectured value of cr(K _m,n ). Here the best factor previously known was 0.8303 instead of 0.8594.     

参数函数$\epsilon$取边际值时的$GCF_\epsilon$集

Let ∈ :N → R be a parameter function satisfying the condition ∈(k) + k + 1 > 0and let T∈ :(0,1] →(0,1] be a transformation defined by T∈(x) =-1 +(k + 1)x1 + k-k∈x for x ∈(1k + 1,1k].Under the algorithm T∈,every x ∈(0,1] is attached an expansion,called generalized continued fraction(GCF∈) expansion with parameters by Schweiger.Define the sequence {kn(x)}n≥1of the partial quotients of x by k1(x) = ∈1/x∈ and kn(x) = k1(Tn-1∈(x)) for every n ≥ 2.Under the restriction-k-1 < ∈(k) <-k,define the set of non-recurring GCF∈expansions as F∈= {x ∈(0,1] :kn+1(x) > kn(x) for infinitely many n}.It has been proved by Schweiger that F∈has Lebesgue measure 0.In the present paper,we strengthen this result by showing that{dim H F∈≥12,when ∈(k) =-k-1 + ρ for a constant 0 < ρ < 1;1s+2≤ dimHF∈≤1s,when ∈(k) =-k-1 +1ksfor any s ≥ 1where dim H denotes the Hausdorff dimension.     

Asymptotic Determination of the Last Packing Number of Quadruples

A 3-(n,4,1) packing design consists of an n-element set X and a collection of 4-element subsets of X, called blocks, such that every 3-element subset of X is contained in at most one block. The packing number of quadruples d(3,4,n) denotes the number of blocks in a maximum 3-(n,4,1) packing design, which is also the maximum number A(n,4,4) of codewords in a code of length n, constant weight 4, and minimum Hamming distance 4. In this paper the last packing number A(n,4,4) for n≡ 5(mod 6) is shown to be equal to Johnson bound with 21 undecided values n=6k+5, k∈{m: m is odd , 3≤ m≤ 35, m≠ 17,21}∪ {45,47,75,77,79,159}. AMS Classification:05B40, 94B25     

An Improvement of the General Bound on the Largest Family of Subsets Avoiding a Subposet

Let La(n, P) be the maximum size of a family of subsets of [n] = {1, 2, … , n} not containing P as a (weak) subposet, and let h(P) be the length of a longest chain in P. The best known upper bound for La(n, P) in terms of |P| and h(P) is due to Chen and Li, who showed that \(\text {La}(n,P) \le \frac {1}{m+1} \left (|{P}| + \frac {1}{2}(m^{2} +3m-2)(h(P)-1) -1 \right ) {\left (\begin {array}{c}{n}\\ {\lfloor n/2 \rfloor } \end {array}\right )}\) for any fixed m ≥ 1. In this paper we show that \(\text {La}(n,P) \le \frac {1}{2^{k-1}} \left (|P| + (3k-5)2^{k-2}(h(P)-1) - 1 \right ) {\left (\begin {array}{c}{n}\\ {\lfloor n/2 \rfloor } \end {array}\right )}\) for any fixed k ≥ 2, improving the best known upper bound. By choosing k appropriately, we obtain that \(\text {La}(n,P) = \mathcal {O}\left (h(P) \log _{2}\left (\frac {|{P}|}{h(P)}+2\right ) \right ) {\left (\begin {array}{c}{n}\\ {\lfloor n/2 \rfloor } \end {array}\right )}\) as a corollary, which we show is best possible for general P. We also give a different proof of this corollary by using bounds for generalized diamonds. We also show that the Lubell function of a family of subsets of [n] not containing P as an induced subposet is \(\mathcal {O}(n^{c})\) for every \(c>\frac {1}{2}\).     

二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices

Given a finite poset P, the intensively studied quantity La(n, P) denotes the largest size of a family of subsets of [n] not containing P as a weak subposet. Burcsi and Nagy (J. Graph Theory Appl. 1, 40–49 2013) proposed a double-chain method to get an upper bound \({\mathrm La}(n,P)\le \frac {1}{2}(|P|+h-2)\left (\begin {array}{c}n \\ \lfloor {n/2}\rfloor \end {array}\right )\) for any finite poset P of height h. This paper elaborates their double-chain method to obtain a new upper bound

$${\mathrm La}(n,P)\le \left( \frac{|P|+h-\alpha(G_{P})-2}{2}\right)\left( \begin{array}{c}n \\ \lfloor{\frac{n}{2}}\rfloor\end{array}\right) $$

for any graded poset P, where α(G _P ) denotes the independence number of an auxiliary graph defined in terms of P. This result enables us to find more posets which verify an important conjecture by Griggs and Lu (J. Comb. Theory (Ser. A) 119, 310–322, 2012).

     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of K<Subscript>n</Subscript>

We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the plane in general position. We show that for the number of (≤ k)-edges is at least