Mathematics and Statistics

We prove that, when 𝑛 goes to infinity, Kostant’s problem has negative answer for almost all simple highest weight modules in the principal block of the BGG category O for the Lie algebra sl_𝑛(ℂ).

In this article, we introduce a non-negative integer-valued function that measures the obstruction for converting topological isotopy between two Legendrian knots into a Legendrian isotopy. We refer to this function as the Cost function. We show that the Cost function induces a metric on the set of topologically isotopic Legendrian knots. Hence, the set of topologically isotopic Legendrian knots can be seen as a graph with path-metric given by the Cost function. Legendrian simple knot types are shown to be characterized using the Cost function. We also get a quantitative version of Fuchs–Tabachnikov’s Theorem that says any two Legendrian knots in (𝕊³, 𝜉_𝑠𝑡𝑑) in the same topological knot type become Legendrian isotopic after sufficiently many stabilizations [8]. We compute the Cost function for Legendrian simple knots (for example torus knots) and we note the behavior of Cost function for twist knots and cables of torus knots (some of which are Legendrian non-simple). We also construct examples of Legendrian representatives of 2-bridge knots and compute the Cost between them. Further, we investigate the behavior of the Cost function under the connect sum operation. We conclude with some questions about the Cost function, its relation with the standard contact structure, and the topological knot type.

Recent results have provided important functional generalizations, extensions and improvements of the Hardy and Levinson integral inequalities. However, they require some assumptions on the main functions, such as monotonicity or convexity assumptions, which remain somewhat restrictive. In this article, we propose two new ideas of functional generalizations, one based on a series expansion approach and the other on an integral approach. Both achieve the goal of offering adaptable generalizations and extensions of the Hardy and Levinson integral inequalities. They are formulated in two different general theorems, which are proved in detail. Several examples of new integral inequalities are derived.

Breuer and Klivans defined a diverse class of scheduling problems in terms of Boolean formulas with atomic clauses that are inequalities. We consider what we call graph-like scheduling problems. These are Boolean formulas that are conjunctions of disjunctions of atomic clauses (𝑥_𝑖 ≠ 𝑥_𝑗). These problems generalize proper coloring in graphs and hypergraphs. We focus on the existence of a solution with all 𝑥 _i taking the value of 0 or 1 (i.e. problems analogous to the bipartite case). When a graph-like scheduling problem has such a solution, we say it has property B just as is done for 2-colorable hypergraphs. We define the notion of a 𝜆-uniform graph-like scheduling problem for any integer partition 𝜆. Some bounds are attained for the size of the smallest 𝜆-uniform graph-like scheduling problems without B. We make use of both random and constructive methods to obtain bounds. Just as in the case of hypergraphs finding tight bounds remains an open problem.

Let {𝐿_𝑛}_≥0 be the sequence of Lucas numbers. In this paper, we determine all Lucas numbers that are palindromic concatenations of two distinct repdigits.

We study the “no-dimensional” analogue of Helly’s theorem in Banach spaces. Specifically, we obtain the following no-dimensional Helly-type results for uniformly convex Banach spaces: Helly’s theorem, fractional Helly’s theorem, colorful Helly’s theorem, and colorful fractional Helly’s theorem.

The combinatorial part of the proofs for these Helly-type results is identical to the Euclidean case as presented in [2]. The primary difference lies in the use of a certain geometric inequality in place of the Pythagorean theorem. This inequality can be explicitly expressed in terms of the modulus of convexity of a Banach space.

We revisit the algorithmic problem of finding a triangle in a graph (Triangle Detection), and examine its relation to other problems such as 3Sum, Independent Set, and Graph Coloring. We obtain several new algorithms:

(I) A simple randomized algorithm for finding a triangle in a graph. As an application, we study a question of Pˇatraşcu (2010) regarding the triangle detection problem.

(II) An algorithm which given a graph 𝐺 = (𝑉 , 𝐸) performs one of the following tasks in 𝑂(𝑚 + 𝑛) (i.e., linear) time: (i) compute a Ω(1/√𝑛)-approximation of a maximum independent set in 𝐺 or (ii) find a triangle in 𝐺. The run-time is faster than that for any previous method for each of these tasks.

(III) An algorithm which given a graph 𝐺 = (𝑉 , 𝐸) performs one of the following tasks in 𝑂(𝑚+𝑛^3/2) time: (i) compute √𝑛-approximation for Graph Coloring of 𝐺 or (ii) find a triangle in 𝐺. The run-time is faster than that for any previous method for each of these tasks on dense graphs, with 𝑚 = (𝑛^9/8).

(IV) Results (II) and (III) above suggest the following broader research direction: if it is difficult to find (A) or (B) separately, can one find one of the two efficiently? This motivates the dual pair concept we introduce. We provide several instances of dual-pair approximation, relating Longest Path, (1,2)-TSP, and other NP-hard problems.

A question of Erdős asked whether there exists a set of 𝑛 points such that 𝑐 ⋅ 𝑛 distances occur more than 𝑛 times. We provide an affirmative answer to this question, showing that there exists a set of 𝑛 points such that $⌊\frac{n}{4}⌋$ distances occur more than 𝑛 times. We also present a generalized version, finding a set of 𝑛 points where 𝑐_𝑚 ⋅ 𝑛 distances occurring more than 𝑛 + 𝑚 times.

The Erdős Matching Conjecture states that the maximum size 𝑓 (𝑛, 𝑘, 𝑠) of a family $F\subseteq \left(\begin{array}{l}\left[n\right]\\ k\end{array}\right)$ that does not contain 𝑠 pairwise disjoint sets is max. $\left\{\left|A_{k,s}\right|,\left|B_{n,k,s}\right|\right\}$ , where $A_{k,s}=\left(\left[\begin{array}{c}sk-1\\ k\end{array}\right]\right)$ and $B_{n,k,s}=\left\{B\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right):B\cap \left[s-1\right]\ne \varnothing \right\}$ . The case 𝑠 = 2 is simply the Erdős-Ko-Rado theorem on intersecting families and is well understood. The case 𝑛 = 𝑠𝑘 was settled by Kleitman and the uniqueness of the extremal construction was obtained by Frankl. Most results in this area show that if 𝑘, 𝑠 are fixed and 𝑛 is large enough, then the conjecture holds true. Exceptions are due to Frankl who proved the conjecture and considered variants for 𝑛 ∈ [𝑠𝑘, 𝑠𝑘 + 𝑐𝑠,𝑘 ] if 𝑠 is large enough compared to 𝑘. A recent manuscript by Guo and Lu considers non-trivial families with matching number at most 𝑠 in a similar range of parameters.

In this short note, we are concerned with the case 𝑠 ≥ 3 fixed, 𝑘 tending to infinity and 𝑛 ∈ {𝑠𝑘, 𝑠𝑘 + 1}. For 𝑛 = 𝑠𝑘, we show the stability of the unique extremal construction of size $\left(\begin{array}{c}sk-1\\ k\end{array}\right)=\frac{s-1}{s}\left(\begin{array}{c}sk\\ k\end{array}\right)$ with respect to minimal degree. As a consequence we derive $\underset{k\to \infty }{\lim }\frac{f\left(sk+1,k,s\right)}{\left(\begin{array}{c}sk+1\\ k\end{array}\right)}<\frac{s-1}{s}-{\epsilon }_s$ for some positive constant 𝜀_𝑠 which depends only on 𝑠.

A long standing Total Coloring Conjecture (TCC) asserts that every graph is total colorable using its maximum degree plus two colors. A graph is type-1 (or type-2) if it has a total coloring using maximum degree plus one (or maximum degree plus two) colors. For a graph 𝐺 with 𝑚 vertices and for a family of graphs {𝐻₁, 𝐻₂, … , 𝐻_𝑚}, denote $G\tilde{\circ }{\Lambda }_{i=1}^m{H}_i$ , the generalized corona product of 𝐺 and 𝐻₁, 𝐻₂, … , 𝐻_𝑚. In this paper, we prove that the total chromatic number of $G\tilde{\circ }{\Lambda }_{i=1}^m{H}_i$ is the maximum of total chromatic number of 𝐺 and maximum degree of $G\tilde{\circ }{\Lambda }_{i=1}^m{H}_i\in$ plus one. As an immediate consequence, we prove that $G\tilde{\circ }{\Lambda }_{i=1}^m{H}_i$ is type-1 when 𝐺 satisfies TCC and also the corona product of 𝐺 and 𝐻 is type-1 if 𝐺 satisfies TCC. This generalizes some results in (R. Vignesh. et. al. in Discrete Mathematics, Algorithms and Applications, 11(1): 2019) and all the results in (Mohan et. al. in Australian Journal of Combinatorics, 68(1): 15-22, 2017.)