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>}}$.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

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.     

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.     

Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

Decomposition of the complete directed graph into k-circuits

We study the decomposition of $\text{K}{}_{\mathrm{n}}{}^1$ (the complete directed graph with n vertices) into arc-disjoint elementary k-circuits, primarily for the case k even. We solve the problem for many values of (n, k) and in particular for all n in the cases k = 4, 6, 8, and 16.     

Cycles of even length in graphs

In this paper we solve a conjecture of P. Erdös by showing that if a graph Gⁿ has n vertices and at least $\text{100kn}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ edges, then G contains a cycle C^2l of length 2l for every integer $\text{l ∈ [k, kn}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{]}$. Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gⁿ has only cn(log n)^α edges (α ≥ 1).     

On the van der Waerden conjecture and zeros of polynomials

Let

$\text{F(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{A}{}_{\mathrm{n}}\text{≠ 0,}$

and

$\text{G(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{B}{}_{\mathrm{n}}\text{≠ 0,}$

be polynomials with real zeros satisfying A_n?1 = B_n?1 = 0, and let

$\text{H(x) =}\text{∑}\text{k=o}\text{n-2}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}\text{.}$

Using the recently proved validity of the van der Waerden conjecture on permanents, some results on the real zeros of H(x) are obtained. These results are related to classical results on composite polynomials.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Derivations of Witt vectors with application to K2 of truncated polynomial rings and Laurent series

The absolute Kähler module $\text{Ω}{}_{\mathrm{w}}{}_{\mathrm{n}}{}^{\mathrm{(k)}}$ of the truncated generalized Witt vectors of a field k of positive characteristic is zero if and only if k is perfect. This recovers known information on $\text{K}{}_2\text{(}\text{k[t]}\text{(t}{}^{\mathrm{n}}\text{)}\text{)}$ with which the structure of K₂(k((t))) can be studied.     

American Mathematical Society short course series: Fundamentals of applied combinatorics : August 12–13, 1977, University of Washington in Seattle,Seattle, Washington

A simple proof is given for the fact that the number of nonsingular similarity relations on {1, 2,… n}, for which the transitive closure of k blocks, equals $\text{(}{}^{\mathrm{2n?2k?1}}{}_{\mathrm{n?1}}\text{) ?(}{}^{\mathrm{2n?2k?1}}{}_{\mathrm{n}}\text{)}$1 ? k ? n > ?2. In particular, this implies a recent result of Shapiro about Catalan numbers and Fine's sequence.     

Random near-regular graphs and the node packing problem

Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by G_n(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞,

$\text{P(G}{}_{\mathrm{n}}\text{(m)}\text{has property}\text{π)→}\text{0}\text{if}\text{m = 1,}\text{1}\text{if}\text{m ? 3,}$

and we conjecture that $\text{P(G}{}_{\mathrm{n}}\text{(2)}\text{has property}\text{π)→ (1–2e}{}^{\mathrm{?2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

Binomial self-inverse sequences and tangent coefficients

This paper treats the class of sequences {a_n} that satisfy the recurrence relation

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}\text{k}\text{a}{}_{\mathrm{k}}\text{d}{}^{\mathrm{n?k}}$

between the odd and even terms of {a_n} that involves the coefficients of tan(t), namely

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{2}\text{n}\text{+1}\text{2}\text{k}\text{+1}\text{)}\text{T}{}_{\mathrm{k}}\text{(d/2)}{}^{\mathrm{2k+1}}\text{a}{}_{\mathrm{2n?2k}}$

A combinatorial setting is then provided to elucidate the appearance of the tangent coefficients in this equation.     

The enumeration of shift register sequences

A study is made of the number of cycles of length k which can be produced by a general n-stage feedback shift register. This problem is equivalent to finding the number of cycles of length k on the so-called de Bruijn-Good graph (Proc. K. Ned. Akad. Wet.49 (1946), 758–764; J. London Math. Soc.21 (3) (1946), 169–172). The number of cycles of length k in such a graph is denoted by β(n, k). From the-de Bruijn-Good graph, it can be shown that β(n, k) is also the number of cyclically distinct binary sequences of length k which have all k successive sets of n adjacent digits (called “n windows”) distinct (the sequence to be considered cyclically). After listing some known results for β(n, k), we show that

$\text{β(k?3, k)=β(k, k)?2φ}{}_{\mathrm{k,\; 2}}\text{+2}\text{for}\text{k?5}$

, where $\text{φ}{}_{\mathrm{k,\; r}}\text{?}$ the number of integers l ? k such that (k, l) ? r, and (k, l) denotes the greatest common divisor of k and l. From the results of several computer programs, it is conjectured that

$\text{β(k?4, k)=β(k, k)?4φ}{}_{\mathrm{k,\; 3}}\text{?2(k, 2)+10 (k?8)}$

,

$\text{β(k?5, k)=β(k, k)?8φ}{}_{\mathrm{k,\; 4}}\text{?(k, 3)+19 (k?11)}$

$\text{β(k?6, k)=β(k, k)?16φ}{}_{\mathrm{k,\; 5}}\text{?4(k, 2)?2(k, 3)+48 (k?15)}$

     

On the probability that k positive integers are relatively prime II

Given a set S of positive integers let $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t)}$ denote the number of k-tuples 〈m₁, …, m_k〉 for which $\text{m}{}_{\mathrm{i}}\text{∈ S ? [1, t]}$ and (m₁, …, m_k) = 1. Also let $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n)}$ denote the probability that k integers, chosen at random from $\text{S ? [1, n]}$, are relatively prime. It is shown that if P = {p₁, …, p_r} is a finite set of primes and S = {m : (m, p₁ … p_r) = 1}, then $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t) = (td(S))}{}^{\mathrm{k}}\text{Π}{}_{\mathrm{\nu ?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) + O(t}{}^{\mathrm{k?1}}\text{)}$ if k ≥ 3 and $\text{Z}{}_2{}^{\mathrm{S}}\text{(t) = (td(S))}{}^2\text{Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^2\text{) + O(t}\text{log}\text{t)}$ where d(S) denotes the natural density of S. From this result it follows immediately that $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) = (ζ(k))}{}^{\mathrm{?1}}\text{Π}{}_{\mathrm{p\in P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{)}{}^{\mathrm{?1}}$ as n → ∞. This result generalizes an earlier result of the author's where $\text{P = ?}$ and S is then the whole set of positive integers. It is also shown that if S = {p₁^x₁ … p_r^x_r : x_i = 0, 1, 2,…}, then $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → 0}$ as n → ∞.     

A new result on the problem of Zarankiewicz

Zarankiewicz (Colloq. Math.2 (1951), 301) raised the following problem: Determine the least positive integer z(m, n, j, k) such that each 0–1-matrix with m rows and n columns containing z(m, n, j, k) ones has a submatrix with j rows and k columns consisting entirely of ones. This paper improves a result of Hylten-Cavallius (Colloq. Math.6 (1958), 59–65) who proved: $\text{[}\text{k}\text{2}\text{]}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{?}\text{lim}{}_{\mathrm{n\to \infty }}\text{inf}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}\text{?}\text{lim}{}_{\mathrm{n\to \infty }}\text{sup}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}\text{? (k ? 1)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. We prove that $\text{lim}{}_{\mathrm{n\to \infty }}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}$ exists and is equal to $\text{(k ? 1)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. For the special case where k = 2 resp. k = 3 this result was proved earlier by Kövari, Sos and Turan (Colloq. Math.3 (1954), 50–57) resp. Hylten-Cavallius.     

Construction of a recurrence relation for modified moments

In this paper we are constructing a recurrence relation of the form

$\text{∑}\text{i=0}\text{r}\text{ω}{}_{\mathrm{i}}\text{(k)m}{}_{\mathrm{k+i}}{}^{\mathrm{\{\lambda \}}}\text{[f] = ω(k)}$

for integrals (called modified moments)

$\text{m}{}_{\mathrm{k}}{}^{\mathrm{\{\lambda \}}}\text{[f]df=}\text{∫}\text{?1}\text{1}\text{f(x)C}{}_{\mathrm{k}}{}^{\mathrm{(\lambda )}}\text{(x)dx (k = 0,1,…)}$

in which C_k^(λ) is the k-th Gegenbauer polynomial of order $\text{λ(λ > ?}\text{1}\text{2}\text{)}$, and f is a function satisfying the differential equation

$\text{∑}\text{i=0}\text{n}\text{P}{}_{\mathrm{i}}\text{(x)f}{}^{\mathrm{(i)}}\text{(x) = p(x) (?1?x?1)}$

of order n, where p₀, p₁, …, p_n ? 0 are polynomials, and m_k^〈λ〉[p] is known for every k. We give three methods of construction of such a recurrence relation. The first of them (called Method I) is optimum in a certain sense.     

On the number of groups of a given order

Letting G(n) denote the number of nonisomorphic groups of order n, it is shown that for square-free n, G(n) ≤ ?(n) and G(n) ≤ (log n)^c on a set of positive density. Letting F_k(x) denote the number of n ≤ x for which G(n) = k, it is shown that $\text{F}{}_2\text{(x) =}\text{O(x(}\text{log}{}_4\text{x)}\text{(}\text{log}{}_3\text{x)}{}^2\text{)}$, where log_rx denotes the r-fold iterated logarithm.