An extremal problem for sets with applications to graph theory

Let X₁, …, X_n be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ? r_i and |B_ij| ? s_i for 1 ? i ? n, 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{ij}}\text{) = ?}$ for 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{il}}\text{) ≠ ?}$ for 1 ? j < l ? h. We prove that $\text{h?}\text{Π}\text{i=1}\text{n}\text{r}{}_{\mathrm{i}}\text{+s}{}_{\mathrm{i}}\text{r}{}_{\mathrm{i}}$. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).     

On a valence problem in extremal graph theory

Let L ≠ Kinp be a p-chromatic graph and e be an edge of L such that L ? e is (p?1)-chromatic If Gⁿ is a graph of n vertices without containing L but containing K_p, then the minimum valence of Gⁿ is

$\text{?n}\text{1?}\text{1}\text{p?}\text{3}\text{2}\text{+}\text{O}\text{(1).}$

     

Two problems in extremal graph theory

Graphs and Combinatorics -     

Compactness results in extremal graph theory

Let L be a given family of so called prohibited graphs. Let ex (n, L) denote the maximum number of edges a simple graph of ordern can have without containing subgraphs from L. A typical extremal graph problem is to determine ex (n, L), or at least, find good bounds on it. Results asserting that for a given L there exists a much smaller L*⫅L for which ex (n, L) ≈ ex (n, L*) will be calledcompactness results. The main purpose of this paper is to prove some compactness results for the case when L consists of cycles. One of our main tools will be finding lower bounds on the number of pathsP ^k+1 in a graph ofn vertices andE edges., witch is, in fact, a “super-saturated” version of a wellknown theorem of Erdős and Gallai. Dedicated to Tibor Gallai on his seventieth birthday     

An optimal problem in graph theory

The following problem is solved: determine a point on a tree having the property that the sum of the products of the intensities of its vertices by the corresponding distances to that point is a minimum. The proposed algorithm is reduced to the stepwise application to the tree of truncation of its vertices. A feasible interpretation of the problem is given.Translated from Matematicheskie Zametki, Vol. 10, No. 3, pp. 355–359, September, 1971.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

An extremal problem in the theory of hardy functions

It is proved that ifj is an inner function and ρ(T)=sup|∫(e^iγT/j(γ))f(γ)dγ| overf in the unit ball ofH ¹, then eitherρ ≡ 1 for allT≧0, or elseρ(T) ↓ 0 exponentially fast asT ↑ ∞. The inner functionsj corresponding to each alternative are classified.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

An extremal problem in convolutions

Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 41, No. 3, pp. 412–414, March, 1989.     

On an extremal problem in number theory

We define h(n) to be the largest function of n such that from any set of n nonzero integers, one can always extract a subset of h(n) integers with the property that any two sums formed from its elements are equal only if they have equal number of summands. A result of Erdös implies that $\text{h(n) ? n}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and it is the aim of the present paper to obtain the refinement $\text{h(n) ? n}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}\text{(}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$.     

An extremal problem in geodetic graphs

An upper bound for the number of lines in a geodetic block of diameter d on p points is obtained, using some new general properties of geodetic blocks which are also of independent interest.     

An extremal problem in hypergraph coloring

F(n, r, k) is defined to be the minimum number of edges in an r graph on n vertices in which there exists a strongly colored edge in every equipartite k-coloring. Approximate values are given for this function in the general case, and the problem is solved in the particular case of graphs.     

An extremal problem for operators

Let A be a Banach algebra, F a compact set in the complex plane, and h a function holomorphic in some neighborhood of the set F. Thus h(a) is meaningful for each element a ε A whose spectrum σ(a) is contained in F, and it is possible to evaluate the norm |h(a)|. Problem: Compute the supremum of the norms |h(a) as a ranges over all elements of A with spectrum contained in F and whose norm does not exceed one; that is, compute sup{|h(a)|; a ε A, σ(a) ⊂ F, |a| ⩽ 1}. This problem was first formulated and treated by the author in the particular case where A is the algebra of all linear operators on a finite-dimensional Hilbert space and F is the disc {z; |z| ⩽ r} for a given positive number r<1. The paper discusses motivation, connections with complex function theory, convergence of iterative processes, critical exponents, and the infinite companion matrix.     

An extremal problem for polynomials

We give a solution to an extremal problem for polynomials, which asks for complex numbers α₀,…,α_n${\alpha }_0,\dots ,{\alpha }_n$ of unit magnitude that minimise the largest supremum norm on the unit circle for all polynomials of degree n whose k  -th coefficient is either α_k${\alpha }_k$ or −α_k$-{\alpha }_k$.