Search

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann. [ABSTRACT FROM AUTHOR]

We say a family of subsets of { 1 , 2 , … , n } is antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of { 1 , 2 , … , n } (of any size). Our inequality implies that for any k ∈ N , among all such families of size 2 k , a family consisting of the union of two antipodal ( k − 1 ) -dimensional subcubes has the smallest possible edge boundary. [ABSTRACT FROM AUTHOR]

For a set of matroids M, let exM(n) be the maximum size of a simple rank-n matroid in M. We prove that, for any finite field F, if M is a minor-closed class of F-representable matroids of bounded branch-width, then limn→ ∞exM(n)/n exists and is a rational number, ∆. We also show that exM(n) - ∆n is periodic when n is sufficiently large and that exM is achieved by a subclass of M of bounded path-width. [ABSTRACT FROM AUTHOR]

The Wiener index W ( G ) of a connected graph G is the sum of distances between all pairs of vertices of G . A connected graph G is said to be a cactus if each of its blocks is either a cycle or an edge. Let G n , t be the set of all n -vertex cacti containing exactly t cycles. Liu and Lu (2007) determined the unique graph in G n , t with the minimum Wiener index. We now establish a sharp upper bound on the Wiener index of graphs in G n , t and identify the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

A unique type of subcontexts is always present in formal contexts with many concepts: the contranominal scales. We make this precise by giving an upper bound for the number of minimal generators (and thereby for the number of concepts) of contexts without contranominal scales larger than a given size. We give an interpretation of this bound in terms of the Vapnik–Chervonenkis dimension of the concept lattice. Extremal contexts are constructed which meet this bound exactly. They are completely classified. [ABSTRACT FROM AUTHOR]

We give a short argument showing that the set of openness points of a continuous function from a metric space X into a metric space Y is of type Gδ. If X is locally connected and Y := R, the set of nonopenness points (of type Fσ) coincides with the set of points of extrema of f. We discuss which Fσ sets can be equal to the set of points of extrema for a continuous function f from R into R, and we present a short survey of the known results on this topic. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

In the article solution of the problem of extremal value of x(τ) is presented, for the n-th order linear systems. The extremum of x(τ) is considered as a function of the roots s1, s2, ... sn of the characteristic equation. The obtained results give a possibility of decomposition of the whole n-th order system into a set of 2-nd order systems. [ABSTRACT FROM AUTHOR]

In 1978, Gutman proposed the concept of graph energy, defined as the sum of the absolute values of eigenvalues of the adjacency matrix of a molecular graph, which is related to the energy of π -electrons in conjugated hydrocarbons. Recently, Gutman and Wagner proposed the concept of matching energy and pointed out that the chemical applications of matching energy go back to the 1970s. In this paper, we study the extremal values of the matching energy and characterize the graphs with minimal matching energy among all tricyclic graphs with a given diameter. Our methods can help to find more extremal values for other classes of molecular networks and the results suggest the structures with extremal energies. [ABSTRACT FROM AUTHOR]

Erdős, Gallai, and Tuza posed the following problem: given an n -vertex graph G , let τ 1 ( G ) denote the smallest size of a set of edges whose deletion makes G triangle-free, and let α 1 ( G ) denote the largest size of a set of edges containing at most one edge from each triangle of G . Is it always the case that α 1 ( G ) + τ 1 ( G ) ≤ n 2 / 4 ? We also consider a variant on this conjecture: if τ B ( G ) is the smallest size of an edge set whose deletion makes G bipartite, does the stronger inequality α 1 ( G ) + τ B ( G ) ≤ n 2 / 4 always hold? By considering the structure of a minimal counterexample to each version of the conjecture, we obtain two main results. Our first result states that any minimum counterexample to the original Erdős–Gallai–Tuza Conjecture has “dense edge cuts”, and in particular has minimum degree greater than n / 2 . This implies that the conjecture holds for all graphs if and only if it holds for all triangular graphs (graphs where every edge lies in a triangle). Our second result states that α 1 ( G ) + τ B ( G ) ≤ n 2 / 4 whenever G has no induced subgraph isomorphic to K 4 − , the graph obtained from the complete graph K 4 by deleting an edge. Thus, the original conjecture also holds for such graphs. [ABSTRACT FROM AUTHOR]

A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [n] not containing a 2-chain, F1 ⊂ F2. Erdős extended this theorem to determine the largest family without a k-chain, F1 ⊂ F2 ⊂ . . . ⊂ Fk. Erdős and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds.In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for k-chains, for all k. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the k + 1 middle levels. We also characterize all extremal configurations. [ABSTRACT FROM AUTHOR]

We prove that each {claw, K4}-free 4-regular graph, with just one class of exceptions, is a line graph. Applying this result, we present lower bounds on the independence numbers for {claw, K4}-free 4-regular graphs and for {claw, diamond}-free 4-regular graphs. Furthermore, we characterize the extremal graphs attaining the bounds. [ABSTRACT FROM AUTHOR]

Abstract: We consider the properties of weak cancellation, -surjectivity, good index theory, and -injectivity, for the class of extremally rich -algebras, and for the smaller class of isometrically rich -algebras. We establish all four properties for isometrically rich -algebras and for extremally rich -algebras that are either purely infinite or of real rank zero, -injectivity in the real rank zero case following from a prior result of H. Lin. We also show that weak cancellation implies the other properties for extremally rich -algebras and that the class of extremally rich -algebras with weak cancellation is closed under extensions. Moreover, we consider analogous properties which replace the group with the extremal K-set as well as two versions of -surjectivity. [Copyright &y& Elsevier]

A k-uniform linear path of length ℓ, denoted by ℙ, is a family of k-sets { F,..., F such that | F ∩ F|=1 for each i and F ∩ F = $\not 0$ whenever | i− j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex( n, H), is the maximum number of edges in a k-uniform hypergraph $\mathcal{F}$ on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex( n, P exactly for all fixed ℓ ≥1, k≥4, and sufficiently large n. We show that . The only extremal family consists of all the k-sets in [ n] that meet some fixed set of t vertices. We also show that , and describe the unique extremal family. Stability results on these bounds and some related results are also established. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Füredi conjectured that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -graphs with edges. Talbot in Talbot (2002) provided some evidences for Frankl and Füredi’s conjecture. In this paper, we prove that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -uniform graphs on vertices with edges when where under some conditions. As an implication, we also derive that Frankl and Füredi’s conjecture holds for 3-uniform graphs with edges where . [ABSTRACT FROM AUTHOR]

Abstract: A measurement on a section K of the set of states of a finite dimensional -algebra is defined as an affine map from K to a probability simplex. Special cases of such sections are used in description of quantum networks, in particular quantum channels. Measurements on a section correspond to equivalence classes of the so-called generalized POVMs, which are called quantum testers in the case of networks. We find extremality conditions for measurements on K and characterize generalized POVMs such that the corresponding measurement is extremal. These results are applied to the set of channels. We find explicit extremality conditions for two outcome measurements on qubit channels and give an example of an extremal qubit 1-tester such that the corresponding measurement is not extremal. [Copyright &y& Elsevier]

Abstract: In this work, two types of codes such that they both dominate and locate the vertices of a graph are studied. Those codes might be sets of detectors in a network or processors controlling a system whose set of responses should determine a malfunctioning processor or an intruder. Here, we present our contributions on -codes and -codes concerning bounds, extremal values and realization theorems. [Copyright &y& Elsevier]

We consider a time-optimal problem for the Reeds and Shepp model describing a moving point on a plane, with a onesided variation of the speed and a free final direction of the velocity. Using the Pontryagin Maximum Principle, we obtain all possible types of extremal and, analyzing them and discarding nonoptimal ones, construct the optimal synthesis. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

Abstract: Two players, Dominator and Staller, alternately choose vertices of a graph , one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is to finish the game as soon as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. It has been conjectured in Kinnersley et al. (2012) [7] that holds for an arbitrary graph with no isolated vertices, which is in particular open when is a forest. In this paper, we present constructions that lead to large families of trees that attain the conjectured -bound. Some of these families can be used to construct graphs with game domination number of their order by gluing them to an arbitrary graph. All extremal trees on up to 20 vertices were found by a computer. In particular, there are exactly ten trees on 20 vertices with , all of which belong to the constructed families. [Copyright &y& Elsevier]

Abstract: The aim of the paper is to give a description of biderivations for a certain class of generalized matrix algebras. We prove that under certain conditions a biderivation of a generalized matrix algebra is a sum of an extremal and an inner biderivation. We also consider the question when a biderivation of a generalized matrix algebra is an inner biderivation. As a consequence we show that every biderivation of a full matrix algebra over a unital algebra is inner. [Copyright &y& Elsevier]

We introduce the class of n-extremal holomorphic maps, a class that generalizes both finite Blaschke products and complex geodesics, and apply the notion to the finite interpolation problem for analytic functions from the open unit disc into the symmetrized bidisc Γ. We show that a well-known necessary condition for the solvability of such an interpolation problem is not sufficient whenever the number of interpolation nodes is 3 or greater. We introduce a sequence ν, where ν≥0, of necessary conditions for solvability, prove that they are of strictly increasing strength and show that n−3 is insufficient for the solvability of an n-point problem for n≥3. We propose the conjecture that condition n−2 is necessary and sufficient for the solvability of an n-point interpolation problem for Γ and we explore the implications of this conjecture.We introduce a classification of rational Γ-inner functions, that is, analytic functions from the disc into Γ whose radial limits at almost all points on the unit circle lie in the distinguished boundary of Γ. The classes are related to n-extremality and the conditions ν; we prove numerous strict inclusions between the classes. [ABSTRACT FROM PUBLISHER]

A number of extremal problems of approximation theory of functions have been solved on the real line $$ \mathbb{R} $$ . Exact constants in the Jackson-type inequalities in the space L( $$ \mathbb{R} $$) are calculated. The exact values of average ν-widths are obtained for the classes of functions from L( $$ \mathbb{R} $$) defined by averaged moduli of continuity of the k-th order, as well as for the classes of functions defined by K-functionals. The quite complete analysis of the final results related to the solution of extremal problems of approximation theory in the periodic case and for the whole real axis is carried out in the chronological order. [ABSTRACT FROM AUTHOR]

This paper contains selected applications of the new tangential extremal principles and related results developed in Mordukhovich and Phan (Math Program ) to calculus rules for infinite intersections of sets and optimality conditions for problems of semi-infinite programming and multiobjective optimization with countable constraints. [ABSTRACT FROM AUTHOR]

In this paper we develop new extremal principles in variational analysis that deal with finite and infinite systems of convex and nonconvex sets. The results obtained, unified under the name of tangential extremal principles, combine primal and dual approaches to the study of variational systems being in fact first extremal principles applied to infinite systems of sets. The first part of the paper concerns the basic theory of tangential extremal principles while the second part presents applications to problems of semi-infinite programming and multiobjective optimization. [ABSTRACT FROM AUTHOR]

Abstract: The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. Integral circulant graphs can be characterised by their order n and a set of positive divisors of n in such a way that they have vertex set and edge set . Among integral circulant graphs of fixed prime power order , those having minimal energy or maximal energy , respectively, are known. We study the energy of integral circulant graphs of arbitrary order n with so-called multiplicative divisor sets. This leads to good bounds for and as well as conjectures concerning the true value of . [Copyright &y& Elsevier]

This article investigates extremality, stationarity, and regularity properties of infinite collections of sets in Banach spaces. Our approach strongly relies on the machinery developed for finite collections. When dealing with an infinite collection of sets, we examine the behavior of its finite subcollections. This allows us to establish certain primal-dual relationships between the stationarity/regularity properties some of which can be interpreted as extensions of the Extremal principle. Stationarity criteria developed in the article are applied to proving intersection rules for Fréchet normals to infinite intersections of sets in Asplund spaces. [ABSTRACT FROM AUTHOR]

We present a correspondence between positive operator valued measures (POVMs) and sets of generalized coherent states. POVMs describe quantum observables and, similar to quantum states, quantum observables can also be mixed. We show how the formalism of generalized coherent states leads to a useful characterization of extremal POVMs. We prove that covariant phasespace observables related to squeezed states are extremal, while those related to number states are not extremal. [ABSTRACT FROM AUTHOR]

Abstract: A balanced bipartition of a graph is a partition of into two subsets and , which differ in size by at most . The minimum balanced bipartition problem asks for a balanced bipartition of a graph minimizing , where is the number of edges joining and . We present a tight upper bound on the minimum of , giving one answer to a question of Bollobás and Scott. We prove that every connected triangle-free plane graph of order at least 3 has a balanced bipartition with , and we show that , , and , with , are precisely the extremal graphs. We also show that every plane graph without separating triangles has a balanced bipartition such that . [Copyright &y& Elsevier]

For a family ${{\cal F}}$ of subsets of [ n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that ${{\cal F}}$ is P-free if it does not contain a subposet isomorphic to P. Let ex( n, P) be the largest size of a P-free family of subsets of [ n]. Let Q be the poset with distinct elements a, b, c, d, a < b, c < d; i.e., the 2-dimensional Boolean lattice. We show that 2 N − o( N) ≤ ex( n, Q) ≤ 2.283261 N + o( N), where $N = \binom{n}{\lfloor n/2 \rfloor}$. We also prove that the largest Q-free family of subsets of [ n] having at most three different sizes has at most 2.20711 N members. [ABSTRACT FROM AUTHOR]

Abstract: The family of subsets of is 2-union free if it does not contain three different sets A, B, C such that , and is union free if it does not contain different sets , , …, such that . Let , be the maximum size of a union free, union free family, respectively. Simple construction shows that , which slightly improves the lower bound obtained by Kleitman if n is odd. Another more complicated construction further improves this lower bound. Union free family of m subsets of naturally corresponds to an matrix with independent rows. The result is related to maximum number m of independent rows in some matrix with n columns. [Copyright &y& Elsevier]

Abstract: The Padmakar–Ivan (PI) index of a graph is defined as the sum of terms [] over all edges of G, where is an edge, connecting the vertices and , where is the number of edges of lying closer to the vertex than to the vertex , and where is defined analogously. The extremal values of the PI index are determined in the class of connected bipartite graphs with a given number of edges. [Copyright &y& Elsevier]

Abstract: For a given matrix , we say a matrix has no configuration if no submatrix of is a row and column permutation of . We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an -rowed simple matrix which has no configuration . A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where denotes the simple matrix. We extend this in several ways. For two matrices on the same number of rows, let denote the concatenation of and . Our first two sets of results are exact bounds that find some matrices where and . Our final result provides asymptotic boundary cases; namely matrices for which is yet for any choice of column not in , we have is . This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a -rowed (0,1)-matrix , we also consider a function which is the minimum number of columns in an -rowed simple matrix for which each -set of rows contains as a configuration. [Copyright &y& Elsevier]

In this paper, a description of the null-sets for the generalized Aikawa-Ohtsuka condenser module is obtained under the assumption that the module has the continuity property. Bibliography: 11 titles. [ABSTRACT FROM AUTHOR]

The problem of existence of an optimal control is solved on the basis of Weierstrass's classical theorem if the set of admissible controls belongs to the class of piecewise continuous functions. In the process of describing admissible controls, the main assumption is that the number of switchings (points of discontinuity) is uniformly bounded and not just finite, as in the main problem of optimal control theory. On the one hand, this assumption does not restrict the spectrum of optimal control applications. On the other hand, it fits the Weierstrass's theorem owing to the convenience in characterizing the sequential compactness. The formulation of Weierstrass's theorem, which asserts the existence of continuous function extrema on sequentially compact sets, is customary, and its proof complies with the traditional scheme, whereas the concepts (convergent sequences and some others) are adapted to the peculiarity of optimal problems. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the extremal function $ f $norm for the class of non-vanishing functions whose first $ n$We define an analytic function $ K$ and show that the functions $ K$ satisfy a certain differential equation. This equation yields a set of relationships between the area moments and the circle moments of $ \vert f\vert^2$is a polynomial of degree at most $ n$ [ABSTRACT FROM AUTHOR]

Abstract: The problem of finding the maximal hyperplane section of , where , has been open for a long time. It is known that the answer depends on both p and n. In this paper, using the well-known equivalence between hyperplane sections and the isotropic constant of a body, we give an upper bound estimate for the volume of hyperplane sections of normalized -balls that does not depend on n and p. In addition, on the basis of results of Meyer, Pajor and Schmuckenschläger, we show further the corresponding extremal body and hyperplane section when this volume attains its minimum. [ABSTRACT FROM AUTHOR]

The Hosoya index and the Merrifield-Simmons index are typical examples of graph invariants used in mathematical chemistry for quantifying relevant details of molecular structure. In recent years, quite a lot of work has been done on the extremal problem for these two indices, i.e., the problem of determining the graphs within certain prescribed classes that maximize or minimize the index value. This survey collects and classifies these results, and also provides some useful auxiliary results, tools and techniques that are frequently used in the study of this type of problem. [ABSTRACT FROM AUTHOR]

We study a disc formula for the relative extremal function for a subset of a complex manifold and apply it to give a description of pluripolar sets and polynomial hulls. [ABSTRACT FROM AUTHOR]

Abstract: Let be the n-dimensional hypercube: the graph with vertex set and edges between vertices that differ in exactly one coordinate. For and we say that is F-free if every embedding satisfies . We consider the question of how large can be if it is F-free. In particular we generalise the main prior result in this area, for , due to E.A. Kostochka and prove a local stability result for the structure of near-extremal sets. We also show that the density required to guarantee an embedded copy of at least one of a family of forbidden configurations may be significantly lower than that required to ensure an embedded copy of any individual member of the family. Finally we show that any subset of the n-dimensional hypercube of positive density will contain exponentially many points from some embedded d-dimensional subcube if n is sufficiently large. [Copyright &y& Elsevier]

Abstract: Ahlswede (1980)  and Frankl (1977)  independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are -valued. In this paper we show that this technique does not extend to -intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding -valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set. [Copyright &y& Elsevier]

Abstract: We generalize a recent result of de la Cal and Cárcamo concerning an extremal property of Bernstein operators. [Copyright &y& Elsevier]

Abstract: Let be a connected and simple graph, and let denote the number of stable sets in . In this letter, we have presented a sharp upper bound for the -value among the set of graphs with cut edges for all possible values of , and characterized the corresponding extremal graphs as well. [Copyright &y& Elsevier]

Abstract: By the extremal number we denote the maximum number of edges in a graph of order and girth at least . The set of such graphs is denoted by . In 1975, Erdős mentioned the problem of determining extremal numbers in a graph of order and girth at least five. In this paper, we consider a generalized version of the problem for any value of girth by using the hybrid simulated annealing and genetic algorithm (HSAGA). Using this algorithm, some new results for have been obtained. In particular, we generate some graphs of girth and 8 which in some cases have more edges than corresponding cages. Furthermore, future work will be described regarding the investigation of structural properties of such extremal graphs and the implementation of HSAGA using parallel computing. [Copyright &y& Elsevier]

Abstract: In this note by saying that a 0–1 matrix avoids a pattern given as a 0–1 matrix we mean that no submatrix of either equals or can be transformed into by replacing some 1 entries with 0 entries. We present a new method for estimating the maximal number of the 1 entries in a matrix that avoids a certain pattern. Applying this method we give a linear bound on the maximal number of the 1 entries in an by matrix avoiding pattern and thereby we answer the question that was asked by Gábor Tardos. Furthermore, we use our approach on patterns related to . [Copyright &y& Elsevier]

Let $a in mathbb {C} setminus [-1,1]$ be given. We consider the problem of finding $sup |p(a)|$ among all polynomials $p$ with complex coefficients of degree less than or equal to $n$ with $max _{-1leq x leq 1}|p(x)| leq 1$. We derive an asymptotic expression for the extremal polynomial and for the extremal value in terms of elementary functions. The solution is based on the description of Zolotarev polynomials with respect to square root polynomial weights. [ABSTRACT FROM AUTHOR]

We obtain solutions of new extremal problems of the geometric theory of functions of a complex variable related to estimates for the inner radii of nonoverlapping domains. Some known results are generalized to the case of open sets. [ABSTRACT FROM AUTHOR]