Combinatorics (math.CO)

Abstract: We prove some novel multi-parameter point-line incidence estimates in vector spaces over finite fields. While these could be seen as special cases of higher-dimensional incidence results, they outperform their more general counterparts in those contexts. We go on to present a number of applications to illustrate their use in combinatorial problems from geometry and number theory.

Abstract: In 2011, Henning, L\"{o}wenstein, and Rautenbach observed that the domination number of a graph is bounded from above by the product of the packing number and the maximum degree of the graph. We prove a stronger statement in subcubic graphs: the independent domination number is bounded from above by three times the packing number.

Abstract: If $G$ is a graph and $X\subseteq V(G)$, then $X$ is a total mutual-visibility set if every pair of vertices $x$ and $y$ of $G$ admits a shortest $x,y$-path $P$ with $V(P) \cap X \subseteq \{x,y\}$. The cardinality of a largest total mutual-visibility set of $G$ is the total mutual-visibility number $\mu_{\rm t}(G)$ of $G$. In this paper the total mutual-visibility number is studied on Hamming graphs, that is, Cartesian products of complete graphs. Different equivalent formulations for the problem are derived. The values $\mu_{\rm t}(K_{n_1}\,\square\, K_{n_2}\,\square\, K_{n_3})$ are determined. It is proved that $\mu_{\rm t}(K_{n_1} \,\square\, \cdots \,\square\, K_{n_r}) = O(N^{r-2})$, where $N = n_1+\cdots + n_r$, and that $\mu_{\rm t}(K_s^{\,\square\,, r}) = \Theta(s^{r-2})$ for every $r\ge 3$, where $K_s^{\,\square\,, r}$ denotes the Cartesian product of $r$ copies of $K_s$. The main theorems are also reformulated as Tur\'an-type results on hypergraphs.

Abstract: In this paper, we introduce an inversion statistic on the hyperoctahedral group $B_n$ by using an decomposition of a positive root system of this reflection group. Then we prove some combinatorial properties for the inversion statistic. We establish an enumeration system on the group $B_n$ and give an efficient method to uniquely derive any group element known its enumeration order with the help of the inversion table. In addition, we prove that the \textit{flag-major index} is equi-distributed with this inversion statistic on $B_n$.

Abstract: We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch-conjecture and prove that if there is a pivot rule for the simplex algorithm for which one can bound the number of steps by the (monotone) diameter of the polyhedron of feasible solutions then the general linear programming problem can be solved in strongly polynomial time.

Abstract: We prove a generalization of the Ahlswede-Cai local-global principle. A new technique to handle edge-isoperimetric problems is introduced which we call the pull-push method. Our main result includes all previously published results in this area as special cases with the only exception of the edge-isoperimetric problem for grids. With this we partially answer a question of Harper on local-global principles. We also describe a strategy for further generalization of our results so that the case of grids would be covered, which would completely settle Harper's question.

Abstract: We determine all maximum weight downsets in the product of two chains, where the weight function is a strictly increasing function of the rank. Many discrete isoperimetric problems can be reduced to the maximum weight downset problem. Our results generalize Lindsay's edge-isoperimetric theorem in two dimensions in several directions. They also imply and strengthen (in several directions) a result of Ahlswede and Katona concerning graphs with maximal number of adjacent pairs of edges. We find all optimal shifted graphs in the Ahlswede-Katona problem. Furthermore, the results of Ahlswede-Katona are extended to posets with a rank increasing and rank constant weight function. Our results also strengthen a special case of a recent result by Keough and Radcliffe concerning graphs with the fewest matchings. All of these results are achieved by applications of a key lemma that we call the reflect-push method. This method is geometric and combinatorial. Most of the literature on edge-isoperimetric inequalities focuses on finding a solution, and there are no general methods for finding all possible solutions. Our results give a general approach for finding all compressed solutions for the above edge-isoperimetric problems. By using the Ahlswede-Cai local-global principle, one can conclude that lexicographic solutions are optimal for many cases of higher dimensional isoperimetric problems. With this and our two dimensional results we can prove Lindsay's edge-isoperimetric inequality in any dimension. Furthermore, our results show that lexicographic solutions are the unique solutions for which compression techniques can be applied in this general setting.

Abstract: We introduce a new infinite family of regular graphs admitting nested solutions in the edge-isoperimetric problem for all their Cartesian powers. The obtained results include as special cases most of previously known results in this area.

Abstract: For $2\leq s<t$, the Erd\H{o}s-Rogers function $f_{s,t}(n)$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. There has been a tremendeus amount of work towards estimating this function, but until very recently only the case $t=s+1$ was well understood. A recent breakthrough of Mattheus and Verstra\"ete on the Ramsey number $r(4,k)$ states that $f_{2,4}(n)\leq n^{1/3+o(1)}$, which matches the known lower bound up to the $o(1)$ term. In this paper we build on their approach and generalize this result by proving that $f_{s,s+2}(n)\leq n^{\frac{2s-3}{4s-5}+o(1)}$ holds for every $s\geq 2$. This comes close to the best known lower bound, improves a substantial body of work and is the best that any construction of similar kind can give.

Abstract: Xuding Zhu introduced a refined scale of choosability in 2020 and observed that the four color theorem is tight on this scale. We formalize and explore this idea of tightness in what we call strictly colorable graphs. We then characterize all strictly colorable complete multipartite graphs.