Mathematics and Statistics

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.)

We study the property of Kelley and the property of Kelley weakly on Hausdorff continua. We extend results known for metric continua to the class of Hausdorff continua. We also present new results about these properties.

The aim of this paper is to study the interrelationship between various forms of (F, G)-shadowing property and represent it through the diagram. We show that asymptotic shadowing is equivalent to (ℕ₀, F _𝑐𝑓 )-shadowing property and that (ℕ₀, F _𝑐𝑓 )-shadowing implies (F _𝑐𝑓 , F _𝑐𝑓 )-shadowing. Necessary examples are discussed to support the diagram. We also give characterization for maps to have the (F, G)-shadowing property through the shift map on the inverse limit space. Further, we relate the (F, G)-shadowing property to the positively F _𝑠-expansive map. Also, we obtain the necessary and sufficient condition for the identity map to have (ℕ₀, F _𝑡)-shadowing property.

We prove that the filtered GRID invariants of Legendrian links in link Floer homology, and consequently their associated invariants in the spectral sequence, obstruct decomposable Lagrangian cobordisms in the symplectization of the standard contact structure on ℝ³, strengthening a result by Baldwin, Lidman, and the fifth author.