Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Thue-Morse at multiples of an integer

Let t=(tn)_n?0 be the classical Thue-Morse sequence defined by , where s₂ is the sum of the bits in the binary representation of n. It is well known that for any integer k?1 the frequency of the letter “1” in the subsequence t₀,tk,t2k,… is asymptotically 1/2. Here we prove that for any k there is an n?k+4 such that tkn=1. Moreover, we show that n can be chosen to have Hamming weight ?3. This is best in a twofold sense. First, there are infinitely many k such that tkn=1 implies that n has Hamming weight ?3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s₂ is replaced by sb for an arbitrary base b?2.     

Nontrivial lower bounds for the least common multiple of some finite sequences of integers

We present here a method which allows to derive a nontrivial lower bounds for the least common multiple of some finite sequences of integers. We obtain efficient lower bounds (which in a way are optimal) for the arithmetic progressions and lower bounds less efficient (but nontrivial) for quadratic sequences whose general term has the form un=an(n+t)+b with (a,t,b)∈Z³, a?5, t?0, gcd(a,b)=1. From this, we deduce for instance the lower bound: lcm{¹²+1,²²+1,…,n²+1}?0,32n(1,442) (for all n?1). In the last part of this article, we study the integer lcm(n,n+1,…,n+k) (k∈N, n∈N^∗). We show that it has a divisor dn,k simple in its dependence on n and k, and a multiple mn,k also simple in its dependence on n. In addition, we prove that both equalities: lcm(n,n+1,…,n+k)=dn,k and lcm(n,n+1,…,n+k)=mn,k hold for an infinitely many pairs (n,k).     

Perfect matchings in large uniform hypergraphs with large minimum collective degree

We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.     

Constructions of new orthogonal arrays and covering arrays of strength three

A covering array of size N, strength t, degree k, and order v, or a CA(N;t,k,v) in short, is a k×N array on v symbols. In every t×N subarray, each t-tuple column vector occurs at least once. When ‘at least’ is replaced by ‘exactly’, this defines an orthogonal array, OA(t,k,v). A difference covering array, or a DCA(k,n;v), over an abelian group G of order v is a k×n array (aij) (1?i?k, 1?j?n) with entries from G, such that, for any two distinct rows l and h of D (1?l<h?k), the difference list Δlh={dh1−dl1,dh2−dl2,…,dhn−dln} contains every element of G at least once.Covering arrays have important applications in statistics and computer science, as well as in drug screening. In this paper, we present two constructive methods to obtain orthogonal arrays and covering arrays of strength 3 by using DCAs. As a consequence, it is proved that there are an OA(3,5,v) for any integer v?4 and v?2 (mod 4), and an OA(3,6,v) for any positive integer v satisfying gcd(v,4)≠2 and gcd(v,18)≠3. It is also proved that the size CAN(3,k,v) of a CA(N;3,k,v) cannot exceed v³+v² when k=5 and v≡2 (mod 4), or k=6, v≡2 (mod 4) and gcd(v,18)≠3.     

Generalization of matching extensions in graphs (III)

Proposing them as a general framework, Liu and Yu (2001) [6] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d+2?|V(G)| and |V(G)|−n−d is even. If on deleting any n vertices from G the remaining subgraph H of G contains a k-matching and each k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. In this paper, we obtain more properties of (n,k,d)-graphs, in particular the recursive relations of (n,k,d)-graphs for distinct parameters n,k and d. Moreover, we provide a characterization for maximal non-(n,k,d)-graphs.     

Equiconvergence and equisummability of nonharmonic Fourier expansions with ordinary trigonometric series

Givenf ε L(?π, π), we consider its nonharmonic Fourier series \(f(x) \sim \sum c_n e^{i\lambda _n x} \) , where λ_n are the roots of the entire function L(z) = ∫ _-π ^π e ^izt dσ (t). We show that this series is equiconvergent, uniformly inside (-π, π), and equisummable with the Fourier series off with respect to the trigonometric system if σ′ (t) =k (t) (π - ∣t∣)^-α, α ε (0, 1), vark <∞, k (π ?0) ≠ 0,k (? π + 0) ≠ 0.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

On approximation of max-vertex-cover

We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G=(V,E), where |V|=n⩾k, such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k>(3/4)n, and a simple randomized algorithm for k>(1/2)n. Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k, our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.     

Generalization of matching extensions in graphs (II)

Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311-320.] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d?|V(G)|-2 and |V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. Liu and Yu's Papee's paper, the recursive relations for distinct parameters n,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)-graphs in the general case d?0.     

Depth and Stanley depth of the facet ideals of some classes of simplicial complexes

Let Δ _n,d (resp. Δ′ _n,d ) be the simplicial complex and the facet ideal I _n,d = (x ₁... x _d, x d?k+1... x _2d?k ,..., x _n?d+1... x _n ) (resp. J _n,d = (x ₁... x _d , x _d?k+1... x _2d?k ,..., x n?2d+2k+1... x _n?d+2k , x n?d+k+1... x n x ₁... x _k)). When d ≥ 2k + 1, we give the exact formulas to compute the depth and Stanley depth of quotient rings S/J _n,d and S/I _n,d ^t for all t ≥ 1. When d = 2k, we compute the depth and Stanley depth of quotient rings S/Jn,d and S/I _n,d , and give lower bounds for the depth and Stanley depth of quotient rings S/I _n,d ^t for all t ≥ 1.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B_p,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,k are of the form (μ,π), where μ is a pairing on {1,…,2p}, π is a partition into k blocks of the same set, and a certain relation holds between μ and π. (The set partitions π that can appear in B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,k identifies it with a set of objects of the form (ρ,t), where ρ is a pairing on a 2(p-k+1)-subset of {1,…,2p} (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when p=k-1, then ρ is empty, and our bijection reduces to a well-known tree bijection.     

Erasure Decoding for Gabidulin Codes

We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matrices, we show that, the erasure(t erasures mean that t components of a code vector are erased) decoding Gabidulin code can be seen as a computation of three matrice and an affine permutation, instead of computing an inverse from the generator or parity check matrix. This significantly reduces the decoding complexity compared to others algorithms. For t erasures with t ≤ r, where r = n − k, the erasure algorithm decoding for Gab _{n, k} (g) Gabidulin code compute the t symbols by simple multiplication of three matrices. That requires rt + r(k − 1) Galois field multiplications, t(r − 1) + (t + r)k field additions, r ² + r(k + 1) field negations and t(k + 1) field inversions.     

Graphs of order two less than the Moore bound

The problem of determining the largest order n_d,k of a graph of maximum degree at most d and diameter at most k is well known as the degree/diameter problem. It is known that n_d,k?M_d,k where M_d,k is the Moore bound. For d=4, the current best upper bound for n_4,k is M_4,k-1. In this paper we study properties of graphs of order M_d,k-2 and we give a new upper bound for n_4,k for k?3.     

Algorithms for graphs with small octopus

A d-octopus of a graph G=(V,E) is a subgraph T=(W,F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common. First, we study the complexity of finding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are efficient approximation algorithms with worst case performance ratio c·d for some small constant c>0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore, the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k=2) and 2d (for k⩾3). Finally, we show that there are O(n^7d+2) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus.     

Periodic orbits in complex Abel equations

This paper is devoted to prove two unexpected properties of the Abel equation dz/dt=z³+B(t)z²+C(t)z, where B and C are smooth, 2π-periodic complex valuated functions, t∈R and z∈C. The first one is that there is no upper bound for its number of isolated 2π-periodic solutions. In contrast, recall that if the functions B and C are real valuated then the number of complex 2π-periodic solutions is at most three. The second property is that there are examples of the above equation with B and C being low degree trigonometric polynomials such that the center variety is formed by infinitely many connected components in the space of coefficients of B and C. This result is also in contrast with the characterization of the center variety for the examples of Abel equations dz/dt=A(t)z³+B(t)z² studied in the literature, where the center variety is located in a finite number of connected components.     

Pancyclic graphs and linear forests

Given integers k,s,t with 0≤s≤t and k≥0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n≥k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with k+t≤m≤n, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with m≤r≤n, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.     

Error and erasure correcting algorithms for rank codes

In this paper, transmitted signals are considered as square matrices of the Maximum rank distance (MRD) (n, k, d)-codes. A new composed decoding algorithm is proposed to correct simultaneously rank errors and rank erasures. If the rank of errors and erasures is not greater than the Singleton bound, then the algorithm gives always the correct decision. If it is not a case, then the algorithm gives still the correct solution in many cases but some times the unique solution may not exist.     

Enumeration of rises and falls by position

Let π=(π₁, π₂,…,π_n) denote a permutation of Z_n = {1, 2,…, n}. The pair (π_i, π_i+1) is a rise if π_i<π_i+1 or a fall if π_i>π_i+1. Also a conventional rise is counted at the beginning of π and a conventional fall at the end. Let k be a fixed integer ≥ 1. The rise π_i,π_i+1 is said to be in a in a j (mod k) position if i ≡ j (mod k); similarly for a fall. The conventional rise at the beginning is in a 0 (mod k) position, while the conventional fall at the end is in an n (mod k) position. Let $\text{P}{}_{\mathrm{n}}\text{≡P}{}_{\mathrm{n}}\text{(r}{}_0\text{,…,r}{}_{\mathrm{k}}\text{?1,?}{}_0\text{,…,?;}{}_{\mathrm{k}}\text{?1)}$ denote the number of permutations having r_i rises i (mod k) positions and ?;_i falls in i (mod k) positions. A generating function for P_n is obtained. In particular, for k = 2 the generating function is quite explicit and also, for certain special cases when k = 4.