An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

The topological type of the α-sections of convex sets

An α=(α₁,…,αk)(0?αi?1) section of a family {K₁,…,Kk} of convex bodies in Rd is a transversal halfspace H⁺ for which Vold(Ki∩H⁺)=αi⋅Vold(Ki) for every 1?i?k. Our main result is that for any well-separated family of strictly convex sets, the space of α-sections is diffeomorphic to Sd−k.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

Monotonicity of permanents of direct sums of doubly stochastic matrices

Let Ωn be the set of all n × n doubly stochastic matrices, let J_n be the n × n matrix all of whose entries are 1/n and let σ _k (A) denote the sum of the permanent of all k × k submatrices of A. It has been conjectured that if A ε Ω _n and A ≠ J_J then g_A,k (θ) ? σ _k ((1 θ)J_n 1 θA) is strictly increasing on [0,1] for k = 2,3,…,n. We show that if A = A ₁ ⊕ ⊕A_t (t ≥ 2) is an n × n matrix where A_i for i = 1,2, …,t, and if for each i g_Ai,ki (θ) is non-decreasing on [0.1] for k_t = 2,3,…,n_i , then g_A,k (θ) is strictly increasing on [0,1] for k = 2,3,…,n.     

On the Slowly Well Orderedness of εo

For α < ε₀, N_α denotes the number of occurrences of ω in the Cantor normal form of α with the base ω. For a binary number-theoretic function f let B(K; f) denote the length n of the longest descending chain (α₀, …, α_n–1) of ordinals <ε₀ such that for all i < n, Nα_i ≤ f (K, i). Simpson [2] called ε₀ as slowly well ordered when B (K; f) is totally defined for f (K; i) = K · (i+ 1). Let |n| denote the binary length of the natural number n, and |n|_k the k-times iterate of the logarithmic function |n|. For a unary function h let L(K; h) denote the function B (K; h₀(K; i)) with h₀(K, i) = K + |i| · |i|_h(i). In this note we show, inspired from Weiermann [4], that, under a reasonable condition on h, the functionL (K; h) is primitive recursive in the inverse h^–1 and vice versa.     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

On arithmetic and asymptotic properties of up-down numbers

Let σ=(σ₁,…,σ_N), where σ_i=±1, and let C(σ) denote the number of permutations π of 1,2,…,N+1, whose up-down signature sign(π(i+1)-π(i))=σ_i, for i=1,…,N. We prove that the set of all up-down numbers C(σ) can be expressed by a single universal polynomial Φ, whose coefficients are products of numbers from the Taylor series of the hyperbolic tangent function. We prove that Φ is a modified exponential, and deduce some remarkable congruence properties for the set of all numbers C(σ), for fixed N. We prove a concise upper bound for C(σ), which describes the asymptotic behaviour of the up-down function C(σ) in the limit C(σ)?(N+1)!.     

Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.