Search

We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that EFX allocation exists if we do not allocate at most (n-1) goods. Reducing the number of unallocated goods has emerged as a systematic way to tackle the main question. For example, follow-up works on three- and four-agents cases, respectively, allocated two more unallocated goods through an involved procedure. In this paper, we study the general case and achieve sublinear numbers of unallocated goods. Through a new approach, we show that for every ε∈(0,1/2] , there always exists a (1−ε) -EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We define the notion of rainbow cycle number R(·) in directed graphs. For all d∈N, R(d) is the largest k such that there exists a k-partite graph G=(∪i∈[k]Vi,E) , in which each part has at most d vertices (i.e., |Vi|≤d for all i∈[k]); for any two parts Vi and Vj, each vertex in Vi has an incoming edge from some vertex in Vj and vice versa; and there exists no cycle in G that contains at most one vertex from each part. We show that any upper bound on R(d) directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on R(d) , yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. Funding: J. Garg was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1942321]. R. Mehta was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1750436]. [ABSTRACT FROM AUTHOR]

On a uniform grid on the real axis, we study the Yanenko–Stechkin–Subbotin problem of extremal function interpolation in the mean in the space , , of two-way real sequences with the least value of the norm of a linear formally self-adjoint differential operator of order with constant real coefficients. In case of even , the value of the least norm in the space , , of the extremal interpolant is calculated exactly if the grid step and the averaging step are related by the inequality . [ABSTRACT FROM AUTHOR]

The paper is devoted to some extremal problems, related to convex polygons in the Euclidean plane and their perimeters. We present a number of results that have simple formulations, but rather intricate proofs. Related and still unsolved problems are also discussed. [ABSTRACT FROM AUTHOR]

If $ P(z)=a_n\prod _{v=1}^{n}(z-z_v) $ P (z) = a n ∏ v = 1 n (z − z v) is a polynomial of degree n having all its zeros in $ |z|\le k, k\ge 1 $ | z | ≤ k , k ≥ 1 then Aziz [Inequalities for the derivative of a polynomial. Proc Am Math Soc. 1983;89(2):259–266] proved that \[ \max_{|z|=1}|P'(z)|\ge \frac{2}{1+k^n}\sum_{v=1}^{n}\frac{k}{k+|z_v|}\max_{|z|=1}|P(z)|. \] max | z | = 1 | P ′ (z) | ≥ 2 1 + k n ∑ v = 1 n k k + | z v | max | z | = 1 | P (z) |. Recently, Kumar [On the inequalities concerning polynomials. Complex Anal Oper Theory. 2020;14(6):1–11 (Article ID 65)] established a generalization of this inequality and proved under the same hypothesis for a polynomial $ P(z)=a_0+a_1z+a_2z^2+\cdots +a_nz^n=a_n\prod _{v=1}^{n}(z-z_v) $ P (z) = a 0 + a 1 z + a 2 z 2 + ⋯ + a n z n = a n ∏ v = 1 n (z − z v) , that $$\begin{align*} & \max_{|z|=1}|P'(z)| \\ & \ge \left(\frac{2}{1+k^n}+\frac{(|a_n|k^n-|a_0|)(k-1)}{(1+k^n)(|a_n|k^n+k|a_0|)}\right)\sum_{v=1}^{n}\frac{k}{k+|z_v|}\max_{|z|=1}|P(z)|. \end{align*} $$ max | z | = 1 | P ′ (z) | ≥ (2 1 + k n + (| a n | k n − | a 0 |) (k − 1) (1 + k n) (| a n | k n + k | a 0 |)) ∑ v = 1 n k k + | z v | max | z | = 1 | P (z) |. In this paper, we sharpen the above inequalities and further extend the obtained results to the polar derivative of a polynomial. As a consequence, our results also sharpens considerably some results of Dewan and Upadhye [Inequalities for the polar derivative of a polynomial. J Ineq Pure Appl Math. 2008;9:1–9 (Article ID 119)]. [ABSTRACT FROM AUTHOR]

The second multiplicative Zagreb eccentricity index E*2 (G) of a simple connected graph G is expressed as the product of the weights ε(a)εG(b) over all edges ab of G, where ε(a) stands for the eccentricity of the vertex a in G. In this paper, some extremal problems on the E*2 index over some special graph classes including trees, unicyclic graphs and bicyclic graphs are examined, and the corresponding extremal graphs are characterized. Besides, the relationships between this vertex-eccentricity-based graph invariant and some well-known parameters of graphs and existing graph invariants such as the number of vertices, number of edges, minimum vertex degree, maximum vertex degree, eccentric connectivity index, connective eccentricity index, first multiplicative Zagreb eccentricity index and second multiplicative Zagreb index are investigated. [ABSTRACT FROM AUTHOR]

Given k$$ k $$ graphs G1,...,Gk$$ {G}_1,\dots, {G}_k $$ over a common vertex set of size n$$ n $$, what is the maximum value of ∑i∈[k]e(Gi)$$ {\sum}_{i\in \left[k\right]}e\left({G}_i\right) $$ having no "colorful" copy of H$$ H $$, that is, a copy of H$$ H $$ containing at most one edge from each Gi$$ {G}_i $$? Keevash, Saks, Sudakov, and Verstraëte denoted this number as exk(n,H)$$ {\mathrm{ex}}_k\left(n,H\right) $$ and completely determined exk(n,Kr)$$ {\mathrm{ex}}_k\left(n,{K}_r\right) $$ for large n$$ n $$. In fact, they showed that, depending on the value of k$$ k $$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured that the same holds for every color‐critical graphs, and proved it for 3‐color‐critical graphs. They also asked to classify the graphs H$$ H $$ that have only these two extremal constructions. We prove their conjecture for 4‐color‐critical graphs and for almost all r$$ r $$‐color‐critical graphs when r>4$$ r>4 $$. Moreover, we show that for every non‐color‐critical non‐bipartite graphs, none of the two natural constructions is extremal for certain values of k$$ k $$. [ABSTRACT FROM AUTHOR]

Nikiforov defined the A α -matrix of a graph G as A α (G) = α D (G) + (1 − α) A (G) , where α ∈ [ 0 , 1 ] , D (G) and A (G) are the diagonal matrix of degrees and the adjacency matrix respectively. The largest eigenvalue of A α (G) is called the A α -spectral radius of G , denoted by ρ α (G). In this paper, we first give an upper bound on ρ α (G) of a connected graph G with fixed size m ≥ 3 k and maximum degree Δ ≤ m − k , where k is a positive integer. For two connected graphs G 1 and G 2 with size m ≥ 4 , employing this upper bound, we prove that ρ α (G 1) > ρ α (G 2) if Δ (G 1) > Δ (G 2) and Δ (G 1) ≥ 2 m 3 + 1. As an application, we determine the graph with the maximal A α -spectral radius among all graphs with fixed size and girth. Our theorems generalize the recent results for the signless Laplacian spectral radius of a graph. [ABSTRACT FROM AUTHOR]

Identifying the graph with maximum or minimum spectral radius among a given class of graphs is a central problem in extremal spectral graph theory, known as the Brualdi–Solheid problem. For a graph G = (V G , E G) , a subset S ⊆ V G is called a maximum dissociation set if the induced subgraph G [ S ] does not contain P 3 as its subgraph, and the subset has maximum cardinality. The dissociation number of G is the number of vertices in a maximum dissociation set of G. In this paper, we first characterize all the connected graphs (resp. bipartite graphs, trees) having maximum spectral radius among connected graphs (resp. bipartite graphs, trees) with given order and dissociation number. Secondly, we show that the connected n -vertex graph with dissociation number φ having minimum spectral radius is a tree, where φ ≥ 2 3 n. Finally, we determine the graphs having minimum spectral radius with fixed order n and dissociation number φ ∈ { 2 , ⌈ 2 n / 3 ⌉ , n − 1 , n − 2 }. [ABSTRACT FROM AUTHOR]

The main objective of this work is to use the Krein{Rutman theorem to characterize extremal points for a (n; p)-type Riemann{Liouville fractional-order boundary value problem. The key premise is that a mapping from a linear, compact operator to its spectral radius, which depends on =, is continuous and strictly increasing as a function of =. A nonlinear problem is also treated as an application of the result for the linear case's extremal point. [ABSTRACT FROM AUTHOR]

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. (Turán problems for Edge-ordered graphs, 2021). They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are n 1 + o (1) . Here we resolve this conjecture proving the stronger upper bound of n 2 O (log n) . This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions Ω (n c) for some c > 1 . However, our result is probably not the last word: here we conjecture that the even stronger upper bound of n log O (1) n also holds for the same set of extremal functions. [ABSTRACT FROM AUTHOR]

"The generalized Turán number of 2S'" by Yanjiao Liu and Jianhua Yin explores the concept of the generalized Turán number and its application to graphs. The authors focus on determining the value of ex(n; Ks; 2S') for different scenarios. The article presents the proof of Theorem 1.4, which establishes the lower and upper bounds for ex(n; Ks; 2S `) based on the extremal graph Kn. The text provides several claims and proofs to support the main theorem. [Extracted from the article]

We prove an analogue of the Korneichuk–Stechkin lemma for functions with values in L-spaces. As applications, we obtain sharp Ostrowski type inequalities and solve problems of optimal recovery of identity and convexifying operators, as well as the problem of integral recovery on the classes of L-space valued functions with given majorant of modulus of continuity. The recovery is done based on n mean values of the functions over intervals. Moreover, on the classes of functions with given majorant of modulus of continuity of their Hukuhara type derivative, we solve the problem of optimal recovery of the function and the Hukuhara type derivative. The recovery is done based on n values of the function. We obtain sharp Landau type inequalities and solve an analogue of the Stechkin problem about approximation of unbounded operators by bounded ones and the problem of optimal recovery of an unbounded operator on a class of elements, known with error. Consideration of L-space valued functions gives a unified approach to solution of the mentioned above extremal problems for the classes of multi- and fuzzy-valued functions, and for the classes of functions with values in Banach spaces, in particular random processes, and many other classes of functions. [ABSTRACT FROM AUTHOR]

The spectral radius and rank of a graph are defined to be the spectral radius and rank of its adjacency matrix, respectively. It is an important problem in spectral extremal graph theory to determine the extremal graph that has the maximum or minimum spectral radius over certain families of graphs. Monsalve and Rada (2021) [8] obtained the extremal graphs with maximum and minimum spectral radii among all graphs with order n and rank 4. In this paper, we first determine the extremal graph which attains the maximum spectral radius among all graphs with any given order n and rank r , and further determine the extremal graph which attains the minimum spectral radius among all graphs with order n and rank 5. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper we continue with our investigation of principal and antiprincipal solutions at infinity solutions of a dynamic symplectic system. The paper is a continuation of part I appeared in Differential Equations and Applications in 2022, where we have presenteded a theory of genera of conjoined bases for symplectic dynamic systems on time scales and its connections with principal solutions at infinity and antiprincipal solutions at infinity for these systems together with some basic properties of this new concept on time scales. Here we provide a characterization of all principal solutions of dynamic symplectic system at infinity in the given genus in terms of the initial conditions and a fixed principal solution at infinity from this genus. Further, we provide a characterization of all antiprincipal solutions of dynamic symplectic system at infinity in the given genus in terms of the initial conditions and a fixed principal solution at infinity from this genus. We also establish mutual limit properties of principal and antiprincipal solutions at infinity. [ABSTRACT FROM AUTHOR]

The paper proves a theorem about the structure of the distribution function on which the extremum of the fractionally linear functional is reached in the presence of an uncountable number of linear constraints. The problem of finding an extremal distribution function arises when determining the optimal control strategy in a class of Markov homogeneous randomized control strategies. The structure of extremal functions is described by a finite number of parameters; hence, the problem is greatly simplified since it is reduced to the search for an extremum of some function. [ABSTRACT FROM AUTHOR]

A new approach to solving eigenvalue optimization problems for large structured matrices is proposed and studied. The class of optimization problems considered is related to computing structured pseudospectra and their extremal points, and to structured matrix nearness problems such as computing the distance to instability or to singularity under structured perturbations. The perturbation structure can be a general linear structure. We focus on the practically important cases of large matrices with a given sparsity pattern and on perturbation matrices with given range and corange. It is known that analogous eigenvalue optimization for unstructured complex matrices favorably works with rank-1 matrices. The novelty of the present paper is that structured eigenvalue optimization can still be performed with rank-1 matrices, which yields a significant reduction of storage and in some cases of the computational cost. Optimizers are shown to be rank-1 matrices orthogonally projected onto the given structure. This is used in the numerical algorithms. The numerical approach comes in two different versions. If the rank-1 matrices projected onto the structure form a manifold and if the orthogonal projection onto the corresponding tangent spaces is known and computationally inexpensive, as is the case for matrices with given range and corange, then the method relies on a gradient system on this manifold. Otherwise, in particular for matrices with a given sparsity pattern, the method relies on the orthogonal projection of the free gradient onto the tangent space of the manifold of complex rank-1 matrices. The solution of this rank-1 system is then projected onto the structure. It is shown that there is a bijective correspondence between the stationary points of the gradient system on the structure space and of the rank-1 system. Near a local minimizer the rank-1 tangent projection is very close to the identity map, and so the computationally favorable rank-1 projected system behaves locally like the gradient system. Numerical experiments illustrate the two approaches for large matrices with a given sparsity pattern and for perturbation matrices with given range and corange. [ABSTRACT FROM AUTHOR]

Brown et al. (J Combin Theory Ser B 15(1):77–93, 1973) considered Turán-type extremal problems for digraphs. However, to date there are very few results on this problem, even asymptotically. Let P 2 , 2 → be the orientation of C 4 which consists of two 2-paths with the same initial and terminal vertices. Huang and Lyu [Discrete Math., 343 (5) (2020)] recently determined the Turán number of P 2 , 2 → , and considered it a more natural and interesting problem to determine the Turán number of directed cycles. Let P k → and C k → denote the directed path and the directed cycle of order k, respectively. In this paper we determine the maximum size of C k → -free digraphs of order n for all n , k ∈ N ∗ , as well as the extremal digraphs attaining this maximum size. Similar result is obtained for P k → where n is large. In addition, we generalize the result of Huang and Lyu by characterizing the extremal digraphs avoiding an arbitrary orientation of C 4 except P 2 , 2 → . In particular, for oriented even cycles, we classify which oriented even cycles inherit the difficulty of their underlying graphs and which do not. [ABSTRACT FROM AUTHOR]

The degree diameter problem is a fundamental and well-studied problem in extremal graph theory, which deals with trade-offs among three parameters: the maximum degree, the diameter, and the number of vertices in a graph. In this paper, we introduce another parameter that represents the robustness of a network and investigate trade-offs among the parameters. For positive integers r and k , we say that a graph is (r , k) -connected if it contains r internally vertex-disjoint paths of length at most k between any pair of vertices. We consider an (r , k) -connected graph with n vertices whose maximum degree is minimized. Our contribution is to show that the minimum of the maximum degree of such a graph is Θ (max { r n k , r }) , which is a tight bound up to constant factors. [ABSTRACT FROM AUTHOR]

The conditional matching preclusion number of a graph G , denoted by m p 1 G , is the minimum number of edges whose deletion results in the graph with no isolated vertices that has neither perfect matching nor almost-perfect matching. In this paper, we first give some sharp upper and lower bounds of conditional matching preclusion number. Next, the graphs with large and small conditional matching preclusion numbers are characterized, respectively. In the end, we investigate some extremal problems on conditional matching preclusion number. [ABSTRACT FROM AUTHOR]

Szeged-like topological indices are well-studied distance-based molecular descriptors, which include, for example, the (edge-)Szeged index, the (edge-)Mostar index, and the (vertex-)PI index. For these indices, the corresponding polynomials were also defined, i.e., the (edge-)Szeged polynomial, the Mostar polynomial, the PI polynomial, etc. It is well known that, by evaluating the first derivative of such a polynomial at  x = 1 , we obtain the related topological index. The aim of this paper is to introduce and investigate a new graph polynomial of two variables, which is called the SMP polynomial, such that all three vertex versions of the above-mentioned indices can be easily calculated using this polynomial. Moreover, we also define the edge-SMP polynomial, which is the edge version of the SMP polynomial. Various properties of the new polynomials are studied on some basic families of graphs, extremal problems are considered, and several open problems are stated. Then, we focus on the Cartesian product, and we show how the (edge-)SMP polynomial of the Cartesian product of n graphs can be calculated using the (weighted) SMP polynomials of its factors. [ABSTRACT FROM AUTHOR]

We study the following question: How few edges can we delete from any H $H$‐free graph on n $n$ vertices to make the resulting graph k $k$‐colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For H $H$ any fixed odd cycle, we determine the answer up to a constant factor when n $n$ is sufficiently large. We also prove an upper bound when H $H$ is a fixed clique that we conjecture is tight up to a constant factor, and prove upper bounds for more general families of graphs. We apply our results to get a new bound on the maximum cut of graphs with a forbidden odd cycle in terms of the number of edges. [ABSTRACT FROM AUTHOR]

Characterizing the graph having the maximum or minimum spectral radius in a given class of graphs is a classical problem in spectral extremal graph theory, originally proposed by Brualdi and Solheid. Given a graph G , a vertex subset S is called a maximum generalized 4-independent set of G if the induced subgraph G [ S ] dose not contain a 4-tree as its subgraph, and the subset S has maximum cardinality. The cardinality of a maximum generalized 4-independent set is called the generalized 4-independence number of G. In this paper, we firstly determine the connected graph (resp. bipartite graph, tree) having the largest spectral radius over all connected graphs (resp. bipartite graphs, trees) with fixed order and generalized 4-independence number, in addition, we establish a lower bound on the generalized 4-independence number of a tree with fixed order. Secondly, we describe the structure of all the n -vertex graphs having the minimum spectral radius with generalized 4-independence number ψ , where ψ ⩾ ⌈ 3 n / 4 ⌉. Finally, we identify all the connected n -vertex graphs with generalized 4-independence number ψ ∈ { 3 , ⌈ 3 n / 4 ⌉ , n − 1 , n − 2 } having the minimum spectral radius. • Characterize the extremal graphs having the maximum spectral radius in some given class of graphs. • Establish a sharp lower bound on the generalized 4-independence number of a tree with fixed order. • Describe the structure of connected graphs in terms of generalized 4-independence numbers and spectral radii. [ABSTRACT FROM AUTHOR]

Extremal problems for multiple time delay hyperbolic systems are presented. The optimal boundary control problems for hyperbolic systems in which multiple time delays appear both in the state equations and in the Neumann boundary conditions are solved. The time horizon is fixed. Making use of Dubovicki-Milutin scheme, necessary and sufficient conditions of optimality for the Neumann problem with the quadratic performance functionals and constrained control are derived. [ABSTRACT FROM AUTHOR]

A graph H$$ H $$ is common if the number of monochromatic copies of H$$ H $$ in a 2‐edge‐coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csóka, Hubai, and Lovász [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2‐edge‐coloring. We give a complete analysis of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H$$ H $$ in such perturbations and classify graphs H$$ H $$ based on this analysis into three categories:Graphs of Class I are weakly locally common.Graphs of Class II are not weakly locally common.Graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common. [ABSTRACT FROM AUTHOR]

An interval graph is the intersection graph of a family F of intervals on the real line. An interval order is a partial order (F , ≺) , where F is a family of intervals on the real line, such that for all I 1 , I 2 ∈ F , I 1 ≺ I 2 if and only if I 1 lies entirely to the left of I 2. In both cases, the family F is called a model of the graph (order). The interval count of a given graph (resp. order) is the smallest number of interval lengths needed in any model of this graph (resp. order). The first problem we consider is related to the classes of graphs and orders which can be represented with two interval lengths a and b , with respect to the inclusion hierarchy among such classes for variables a , b. The second problem is an extremal problem which consists of determining the smallest graph or order which has interval count at least k. In particular, we study a conjecture by Fishburn on this extremal problem, verifying its validity when such a conjecture is constrained to the classes of trivially perfect orders and split orders. [ABSTRACT FROM AUTHOR]

For two given measure-preserving functions defined on the unit interval f , g : I → I , the function given by C f , g (u , v) : = λ (f − 1 ([ 0 , u ]) ∩ g − 1 ([ 0 , v ])) is a copula. Although the theoretical problem for constructing this copula is completely solved, in practice it is a rather difficult task. The principal problem is the reverse implication (that is, to prove that f and g are measure-preserving when C f , g is a copula). We provide new proof of this fact with a technique that is far from the previous ones already known in the literature. Indeed, finding two measure-preserving functions f and g , such that C f , g = C , for a given C , is equivalent to a suitable decomposition of such copula in the form C = C f , id ⁎ C id , g (the ⁎ -product), where id denotes the identity function. We also provide explicit algorithms which solve this problem in various contexts such as the measure preserving functions f and g are monotonic, as well as the copula C is a diagonal copula, an extreme copula, an extremal biconic copula, an Archimedean copula, a conic copula, a copula invariant under truncations, or an α -migrative copula. [ABSTRACT FROM AUTHOR]

Brualdi and Hoffman [On the spectral radius of (0, 1)-matrices. Linear Algebra Appl. 1985;65:133–146] proposed the problem of determining the maximal spectral radius of graphs with a given size. In this paper, we consider the Brualdi–Hoffman-type problem for graphs with a given matching number. The maximal Q-spectral radius of graphs with a given size and matching number is obtained, and the corresponding extremal graphs are completely determined. [ABSTRACT FROM AUTHOR]

This paper introduces a new concept of Caputo type interval-valued fractional conformable calculus. Based on this, some theorems and properties related to fractional conformable calculus are presented. As an application, this paper attempts to investigate an initial value problem of functional integro-differential equations with Caputo type interval-valued fractional conformable derivatives. We not only prove the existence of at least one solution, the extremal solutions and the unique solution of the above problem, but also establish some monotone iterative sequences converging to the extremal solutions. More meaningful and important, some comparison principles and generalized Gronwall inequality related to the proposed problem are also proved. Two examples are presented to illustrate the main results. We firmly believe that the concept of interval-valued fractional conformable calculus, new comparison principles and generalized Gronwall inequality introduced here can be conveniently applied to qualitative analysis of a variety of new interval-valued fractional conformable biological models, economic models, etc., which will better describe and explain various complex phenomena derived from the real world. [ABSTRACT FROM AUTHOR]

Minors play a key role in graph theory, and extremal problems on forbidding minors have attracted appreciable amount of interest in the past decades. In this paper, we focus on spectral extrema of K s , t -minor free graphs, and determine extremal graphs with maximum spectral radius over all K s , t -minor free graphs of sufficiently large order. This generalizes and improves several previous results. For t ≥ s ≥ 2 , our result completely solves Tait's conjecture. For t ≥ s = 1 , our result gives a spectral analogue of a theorem due to Ding, Johnson and Seymour, which determines the maximum number of edges in K 1 , t -minor free connected graphs. Some spectral and structural tools, such as, local edge maximality, local degree sequence majorization and double eigenvectors transformation, are used to characterize structural properties of extremal graphs. [ABSTRACT FROM AUTHOR]

Copyright of Radio Electronics, Computer Science, Control is the property of Zaporizhzhia National Technical University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The [ n , k , r ] -Locally recoverable codes (LRC) studied in this work are a well-studied family of [ n , k ] linear codes for which the value of each symbol can be recovered by a linear combination of at most r other symbols. In this paper, we study the LMD problem, which is to find the largest possible minimum distance of [ n , k , r ] -LRCs, denoted by D (n , k , r). LMD can be approximated within an additive term of one—it is known that D (n , k , r) is equal to either d ⁎ or d ⁎ − 1 , where d ⁎ = n − k − ⌈ k r ⌉ + 2. Moreover, for a range of parameters, it is known precisely whether the distance D (n , k , r) is d ⁎ or d ⁎ − 1. However, the problem is still open despite a significant effort. In this work, we convert LMD to an equivalent simply-stated problem in graph theory. Using this conversion, we show that an instance of LMD is at least as hard as computing the size of a maximal graph of high girth, a hard problem in extremal graph theory. This is an evidence that LMD—although can be approximated within an additive term of one—is hard to solve in general. As a positive result, thanks to the conversion and the exiting results in extremal graph theory, we solve LMD for a range of code parameters that has not been solved before. [ABSTRACT FROM AUTHOR]

Generalized Turán problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size t in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants. [ABSTRACT FROM AUTHOR]

A block code is called a locally recoverable code (LRC for short) with $(r,\delta)$ -locality, if subject to any $\delta -1$ erasure failures, every symbol in the encoding can still be recovered by accessing at most $r$ other symbols. Recently, it was discovered by several authors that a $q$ -ary optimal $(r,\delta)$ -LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$ -ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special cases). In this paper, we further investigate constructions of optimal $(r,\delta)$ -LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of $\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal $(r,\delta)$ -LRC with code length $\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ , where $d$ is the minimum distance. In particular, to our surprise, for $\delta =2$ this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami et al. (2018) for $d\geq 7$. In addition, for $d=6$ , we are able to remove the constraint required in Jin (2019) that $q$ is even. [ABSTRACT FROM AUTHOR]

The Sombor index is a novel topological index, which was introduced by Gutman and defined for a graph G as S O (G) = ∑ u v ∈ E (G) d u 2 + d v 2 , where d u = d G (u) denotes the degree of vertex u in graph G. Extremal problems on the Sombor index for trees with a given diameter has been considered by Chen et al. (MATCH Commun Math Comput Chem 87:23–49, 2022) and Li et al. (Appl Math Comput 416:126731, 2022). As an extension of the results introduced above, we determine the maximum Sombor indices for unicyclic graphs with a fixed order and given diameter. [ABSTRACT FROM AUTHOR]

The proposed distribution is validated by COVID-19 data from the UK and is evaluated for goodness-of-fit using the empirical survival Jensen-Shannon divergence and the Kolmogorov-Smirnov two-sample test statistic. 35741558 23 Jaenada M., Miranda P., Pardo L. Robust Test Statistics Based on Restricted Minimum Rényi's Pseudodistance Estimators. In [[26]], the authors focus on a general family of measures of divergence and purpose a restricted minimum divergence estimator under constraints and a new double-index (dual) divergence test statistic which is thoroughly examined. The present Special Issue of I Entropy i , entitled Information and Divergence Measures, covers various aspects and applications in the general area of Information and Divergence Measures. [Extracted from the article]

Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5‐cycles that an n‐vertex planar graph can contain. [ABSTRACT FROM AUTHOR]

For positive integers n > d ≥ k , let ϕ (n , d , k) denote the least integer ϕ such that every n -vertex graph with at least ϕ vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function ϕ (n , d , k) , and conjectured that for any positive integers n > d ≥ k , it holds that ϕ (n , d , k) ≤ ⌊ k − 1 2 ⌋ ⌊ n d + 1 ⌋ + ϵ , where ϵ = 1 if k is odd and ϵ = 2 otherwise. In this paper we determine the values of the function ϕ (n , d , k) exactly. This confirms the above conjecture of Erdős et al. for all positive integers k ≠ 4 and in a corrected form for the case k = 4. Our proof utilizes, among others, a lemma of Erdős et al. [3] , a theorem of Jackson [6] , and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7] , where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al. [ABSTRACT FROM AUTHOR]

A graph is minimally k -(edge)-connected if it is k -connected (respectively, k -edge-connected) and deleting any arbitrary chosen edge always leaves a graph which is not k -connected (respectively, k -edge-connected). What is the maximum (signless Laplacian) spectral radius and what are the corresponding extremal graphs among minimally k -(edge)-connected graphs for k ≥ 2 ? Chen and Guo (2019) gave the answer to k = 2 and characterized the corresponding extremal graphs. In this paper, we first give the answer to k = 3 for minimally 3-connected graphs. For the signless Laplacian spectral radius, we also consider the problem for k = 2 , 3 and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

A common theme in many extremal problems in graph theory is the relation between local and global properties of graphs. One of the most celebrated results of this type is the Ruzsa–Szemerédi triangle removal lemma, which states that if a graph is |$\varepsilon $| -far from being triangle free, then most subsets of vertices of size |$C(\varepsilon)$| are not triangle free. Unfortunately, the best known upper bound on |$C(\varepsilon)$| is given by a tower-type function, and it is known that |$C(\varepsilon)$| is not polynomial in |$\varepsilon ^{-1}$|⁠. The triangle removal lemma has been extended to many other graph properties, and for some of them the corresponding function |$C(\varepsilon)$| is polynomial. This raised the natural question, posed by Goldreich in 2005 and more recently by Alon and Fox, of characterizing the properties for which one can prove removal lemmas with polynomial bounds. Our main results in this paper are new sufficient and necessary criteria for guaranteeing that a graph property admits a removal lemma with a polynomial bound. Although both are simple combinatorial criteria, they imply almost all prior positive and negative results of this type. Moreover, our new sufficient conditions allow us to obtain polynomially bounded removal lemmas for many properties for which the previously known bounds were of tower type. In particular, we show that every semi-algebraic graph property admits a polynomially bounded removal lemma. This confirms a conjecture of Alon. [ABSTRACT FROM AUTHOR]