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.     

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.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

Ordering uniform supertrees by their spectral radii

A supertree is a connected and acyclic hypergraph. For a hypergraph H, the maximal modulus of the eigenvalues of its adjacency tensor is called the spectral radius of H. By applying the operation of moving edges on hypergraphs and the weighted incidence matrix method, we determine the ninth and the tenth k-uniform supertrees with the largest spectral radii among all k-uniform supertrees on n vertices, which extends the known result.     

Decomposing Hypergraphs into Simple Hypertrees

T be a simple k-uniform hypertree with t edges. It is shown that if H is any k-uniform hypergraph with n vertices and with minimum degree at least , and the number of edges of H is a multiple of t then H has a T-decomposition. This result is asymptotically best possible for all simple hypertrees with at least two edges. Received December 28, 1998     

Path length in the covering graph of a lattice

Here it is proved that a cyclic (n, k) code over GF(q) is equidistant if and only if its parity check polynomial is irreducible and has exponent $\text{e =}\text{(q}{}^{\mathrm{k}}\text{? 1)}\text{a}$ where a divides q ? 1 and (a, k) = 1. The length n may be any multiple of e. The proof of this theorem also shows that if a cyclic (n,k) code over GF(q) is not a repetition of a shorter code and the average weight of its nonzero code words is integral, then its parity check polynomial is irreducible over GF(q) with exponent $\text{n =}\text{(q}{}^{\mathrm{k}}\text{? 1)}\text{a}$ where a divides q ? 1.     

Perfect matchings in uniform hypergraphs with large minimum degree

A perfect matching in a k-uniform hypergraph on n vertices, n divisible by k, is a set of n/k disjoint edges. In this paper we give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every k≥3 and sufficiently large n, a perfect matching exists in every n-vertex k-uniform hypergraph in which each set of k−1 vertices is contained in n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/k rather than n/2.     

Interval hypergraphs and D-interval hypergraphs

A hypergraph $\text{H = (V,}\text{E}\text{)}$ is called an interval hypergraph if there exists a one-to-one function ? mapping the elements of V to points on the real line such that for each edge E, there is an interval I, containing the images of all elements of E, but not the images of any elements not in E₁. The difference hypergraph D(H) determined by H is formed by adding to $\text{E}$ all nonempty sets of the form E₁ ? E₁, where E₁ and E₁ are edges of HH is said to be a D-interval hypergraph if D(H) is an interval hypergraph. A forbidden subhypergraph characterization of D-interval hypergraphs is given. By relating D-interval hypergraphs to dimension theory for posets, we determine all 3-irreducible posets of length one.     

A generalization of Turán's theorem to directed graphs

We consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on m vertices. For an integer n?2, let T_n denote the transitive tournament with vertex set X_n={1,2,3,…,n} and edge set {(i,j):1?i<j?n}. A subgraph H of T_n is said to be m-locally unipathic when the restriction of H to each m element subset of X_n consisting of m consecutive integers is unipathic. We show that the maximum number of edges in a m-locally unipathic subgraph of T_n is ($\text{q}\text{2}\text{)(m?1)}{}^2\text{+q(m?1)r+?}\text{1}\text{4}\text{r}{}^2\text{?}$ where n= q(m?1+r and $\text{?}\text{1}\text{2}\text{(m?1)??r<?}\text{3}\text{2}\text{(m?1)?}$. As is the case with Turán's theorem, the extremal graphs for our problem are complete multipartite graphs. Unlike Turán's theorem, the part sizes will not be uniform. The proof of our principal theorem rests on a combinatorial theory originally developed to investigate the rank of partially ordered sets.     

A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

Characterization of H(n, q) by the parameters

Distance-regular graphs which have the same parameters as the Hamming scheme H(n, q) are classified. If q ≠ 4, H(n, q) is the only such graph. If q = 4, there are precisely $\text{[}\text{n}\text{2}\text{]}$ (isomorphism classes of) such graphs other than H(n, q).     

Solution of two fractional packing problems of lovász

Lovász asked whether the following is true for each hypergraph H and natural number k:(1) if $\text{v}{}_{\mathrm{k}}\text{(H′) = k · v}{}^1\text{(H′)}$ holds for each hypergraph H′ arising from H by multiplication of points, then v_k(H) = τ_k(H);(7) if $\text{τ}{}_{\mathrm{k}}\text{(H′) = k · τ}{}^1\text{(H′)}$ holds for each hypergraph H′ arising by removing edges, then τ_k (H) = v_k (H).We prove and generalize assertion (1) and give a counterexample to (7).     

Graphs without quadrilaterals

Let f(n) denote the maximum number of edges of a graph on n vertices not containing a circuit of length 4. It is well known that $\text{f(n) ～}\text{1}\text{2}\text{n}\text{n}$. The old conjecture $\text{f(q}{}^2\text{+ q + 1) =}\text{1}\text{2}\text{q(q + 1)}{}^2$ is proved for infinitely many q (whenever q = 2^k).     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

Extremal uncrowded hypergraphs

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size $\text{c}{}_{\mathrm{k}}\text{(}\text{n}\text{t}\text{)(}\text{ln}\text{t)}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$.     

On the maximum number of edges in a hypergraph whose linegraph contains no cycle

Soit H = (X,F) un hypergraphe h-uniforme avec ∥X∥ = n et soit L_h±1(H) le graphe dont les sommets représentent les arêtes de H. deux sommets étant relíes si et seulement si les arétes qu'ils représentent intersectent en h ± 1 sommets. Nous montrons que si L_h±1(H) ne contient pas de cycle, alors $\text{∥F∥<(}{}^{\mathrm{n}}{}_{\mathrm{h\pm 1}}\text{)/h±1}$. la borne étant exacte pour h = 2 et pour des valeurs de H pour h = 3. Ce probl`eme mène á une conjecture sur les “presque systèmes de Steine.”Let H = (X, F) be a h-uniform hypergraph, with ∥X∥ = n and let L_h±1(H) be the graph whose vertices are the edges of H, two vertices being joined if and only if the edges they represent intersect in h ±1 vertices. We prove that, if L_h±1H contains no cycle, then $\text{∥F∥(}{}^{\mathrm{n}}{}_{\mathrm{h\pm 1}}\text{)/h±1}$; moreover the bound is exact for h = 2 and with some values of n for h = 3. This problem leads to a conjecture on “almost Steiner systems”.