Combinatorics (math.CO)

Abstract: The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Thomassen (2018) and Hartke, Jahanbekam and Thomas (2016) proved that $\chi(G^2) \leq 7$ if $G$ is a subcubic planar graph. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6.

Abstract: The purpose of this paper is twofold. We investigate a simple necessary condition, called the rhombus criterion, for two vertices in a polytope not to form an edge and show that in many examples of $0/1$-polytopes it is also sufficient. We explain how also when this is not the case, the criterion can give a good algorithm for determining the edges of high-dimenional polytopes. In particular we study the Chordal graph polytope, which arises in the theory of causality and is an important example of a characteristic imset polytope. We prove that, asymptotically, for almost all pairs of vertices the rhombus criterion holds. We conjecture it to hold for all pairs of vertices.

Abstract: The free semigroup $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the set of all finite words with letters from $\mathcal{A}$ equipped with the operation of concatenation. A subset $S$ of $\mathcal{F}$ is $k$-product-free if no element of $S$ can be obtained by concatenating $k$ words from $S$, and strongly $k$-product-free if no element of $S$ is a (non-trivial) concatenation of at most $k$ words from $S$. We prove that a $k$-product-free subset of $\mathcal{F}$ has upper Banach density at most $1/\rho(k)$, where $\rho(k) = \min\{\ell \colon \ell \nmid k - 1\}$. This confirms a conjecture of Ortega, Ru\'{e}, and Serra. We also determine the structure of the extremal $k$-product-free subsets for all $k \notin \{3, 5, 7, 13\}$; a special case of this proves a conjecture of Leader, Letzter, Narayanan, and Walters. We further determine the structure of all strongly $k$-product-free sets with maximum density.

Abstract: Efficient vectors are the natural set from which to choose a cardinal ranking vector for a reciprocal matrix. Such vectors are the key to certain business project selection models. Many ways to construct specific efficient vectors have been proposed. Yet, no previous method to produce all efficient vectors was known. Here, using some graph theoretic ideas, as well as a numerical extension technique, we show how to generate all efficient vectors for any given reciprocal matrix. We apply this method to give explicitly all efficient vectors for a 4-by-4 reciprocal matrix. Several examples are provided.

Abstract: A family $\mathcal{F} \subset \mathcal{P}(n)$ is $r$-wise $k$-intersecting if $|A_1 \cap \dots \cap A_r| \geq k$ for any $A_1, \dots, A_r \in \mathcal{F}$. It is easily seen that if $\mathcal{F}$ is $r$-wise $k$-intersecting for $r \geq 2$, $k \geq 1$ then $|\mathcal{F}| \leq 2^{n-1}$. The problem of determining the maximal size of a family $\mathcal{F}$ that is both $r_1$-wise $k_1$-intersecting and $r_2$-wise $k_2$-intersecting was raised in 2019 by Frankl and Kupavskii [1]. They proved the surprising result that, for $(r_1,k_1) = (3,1)$ and $(r_2,k_2) = (2,32)$ then this maximum is at most $2^{n-2}$, and conjectured the same holds if $k_2$ is replaced by $3$. In this paper we shall not only prove this conjecture but we shall also determine the exact maximum for $(r_1,k_1) = (3,1)$ and $(r_2,k_2) = (2,3)$ for all $n$.

Abstract: A distance estimator for a graph property $\mathcal{P}$ is an algorithm that given $G$ and $\alpha, \varepsilon >0$ distinguishes between the case that $G$ is $(\alpha-\varepsilon)$-close to $\mathcal{P}$ and the case that $G$ is $\alpha$-far from $\mathcal{P}$ (in edit distance). We say that $\mathcal{P}$ is estimable if it has a distance estimator whose query complexity depends only on $\varepsilon$. Every estimable property is also testable, since testing corresponds to estimating with $\alpha=\varepsilon$. A central result in the area of property testing, the Fischer--Newman theorem, gives an inverse statement: every testable property is in fact estimable. The proof of Fischer and Newman was highly ineffective, since it incurred a tower-type loss when transforming a testing algorithm for $\mathcal{P}$ into a distance estimator. This raised the natural problem, studied recently by Fiat--Ron and by Hoppen--Kohayakawa--Lang--Lefmann--Stagni, whether one can find a transformation with a polynomial loss. We obtain the following results. 1. If $\mathcal{P}$ is hereditary, then one can turn a tester for $\mathcal{P}$ into a distance estimator with an exponential loss. This is an exponential improvement over the result of Hoppen et. al., who obtained a transformation with a double exponential loss. 2. For every $\mathcal{P}$, one can turn a testing algorithm for $\mathcal{P}$ into a distance estimator with a double exponential loss. This improves over the transformation of Fischer--Newman that incurred a tower-type loss. Our main conceptual contribution in this work is that we manage to turn the approach of Fischer--Newman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of Frieze--Kannan Weak Regular partitions that are of independent interest.

Abstract: We develop Grothendieck's theory of dualizing complexes on finite posets, and its subsequent theory of Cohen-Macaulayness.

Abstract: We study the set of intersection sizes of a $k$-dimensional affine subspace and a point set of size $m \in [0, 2^n]$ of the $n$-dimensional binary affine space $AG(n,2)$. Following the theme of Erd\H{o}s, F\"uredi, Rothschild and T. S\'os, we partially determine which local densities in $k$-dimensional affine subspaces are unavoidable in all $m$-element point sets in the $n$-dimensional affine space.\\ We also show constructions of point sets for which the intersection sizes with $k$-dimensional affine subspaces takes values from a set of a small size compared to $2^k$. These are built up from affine subspaces and so-called subspace evasive sets. Meanwhile, we improve the best known upper bounds on subspace evasive sets and apply results concerning the canonical signed-digit (CSD) representation of numbers.