Combinatorics
New submissions
[ showing up to 2000 entries per page: fewer | more ]
New submissions for Fri, 10 May 24
- [1] arXiv:2405.05296 [pdf, other]
-
Title: A Note on Polychromatic Colorings of Shift-ChainsAuthors: Torsten UeckerdtSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
We popularize the question whether (for large $m$) all $m$-uniform shift-chain hypergraphs are (properly) $2$-colorable. On the other hand, we show that for every $m$ some $m$-uniform shift-chains are not polychromatic $3$-colorable.
- [2] arXiv:2405.05356 [pdf, ps, other]
-
Title: Accessibility of Sparse SetsAuthors: Oscar QuesterSubjects: Combinatorics (math.CO)
A set $D \subseteq \mathbb{N}$ is called $r$-large if every $r$-coloring of $\mathbb{N}$ admits arbitrarily long monochromatic arithmetic progressions $a,a+d,...,a+(k-1)d$ with gap $d \in D$. Closely related to largeness is accessibility; a set $D \subseteq \mathbb{N}$ is called $r$-accessible if every $r$-coloring of $\mathbb{N}$ admits arbitrarily long monochromatic sequences $x_1,x_2,...,x_k$ with $x_{i+1}-x_{i} \in D$. It is known that if $D \subseteq \mathbb{N}$ is $2$-large, then the gaps between elements in $D$ cannot grow exponentially. In this paper, we show that if $D$ is $2$-accessible, then the gaps between elements in $D$ cannot grow much faster than exponentially.
- [3] arXiv:2405.05357 [pdf, ps, other]
-
Title: Flattened Catalan WordsComments: arXiv admin note: substantial text overlap with arXiv:2404.05672Subjects: Combinatorics (math.CO)
In this work, we define flattened Catalan words as Catalan words whose runs of weak ascents have leading terms that appear in weakly increasing order. We provide generating functions, formulas, and asymptotic expressions for the number of flattened Catalan words based on the number of runs of ascents (descents), runs of weak ascents (descents), $\ell$-valleys, valleys, symmetric valleys, $\ell$-peaks, peaks, and symmetric peaks.
- [4] arXiv:2405.05368 [pdf, ps, other]
-
Title: The minimum orientable genus of the repeated Cartesian product of families of graphsSubjects: Combinatorics (math.CO)
Determining the minimum genus of a graph is a fundamental optimisation problem in the study of network design and implementation as it gives a measure of non-planarity of graphs. In this paper, we are concerned with determining the smallest value of $g$ such that a given graph $G$ has an embedding on the orientable surface of genus $g$. In particular, we consider the Cartesian product of graphs since this is a well studied graph operation which is often used for modelling interconnection networks. The $s$-cube $Q_i^{(s)}$ is obtained by taking the repeated Cartesian product of $i$ complete bipartite graphs $K_{s,s}$. We determine the genus of the Cartesian product of the $2r$-cube with the repeated Cartesian product of cycles and of the Cartesian product of the $2r$-cube with the repeated Cartesian product of paths.
- [5] arXiv:2405.05375 [pdf, other]
-
Title: Antimagic and product antimagic graphs with pendant edgesComments: 20 pages, 6 figuresSubjects: Combinatorics (math.CO)
Let $G=(V,E)$ be a simple graph of size $m$ and $L$ a set of $m$ distinct real numbers. An $L$-labeling of $G$ is a bijection $\phi: E \rightarrow L$. We say that $\phi$ is an antimagic $L$-labeling if the induced vertex sum $\phi_+: V \rightarrow \mathbb {R}$ defined as $\phi_+(u)=\sum_{uv\in E}\phi(uv)$ is injective. Similarly, $\phi$ is a product antimagic $L$-labeling of $G$ if the induced vertex product $\phi_{\circ}: V \rightarrow \mathbb {R}$ defined as $\phi_{\circ}(u)=\prod_{uv\in E}\phi(uv)$ is injective. A graph $G$ is antimagic (resp. product antimagic) if it has an antimagic (resp. a product antimagic) $L$-labeling for $L=\{1,2,\dots,m\}$. Hartsfield and Ringel conjectured that every simple connected graph distinct from $K_2$ is antimagic, but the conjecture remains widely open.
We prove, among other results, that every connected graph of size $m$, $m \geq 3$, admits an antimagic $L$-labeling for every arithmetic sequence $L$ of $m$ positive real numbers, if every vertex of degree at least three is a support vertex. As a corollary, we derive that these graphs are antimagic, reinforcing the veracity of the conjecture by Hartsfield and Ringel. Moreover, these graphs admit also a product antimagic $L$-labeling provided that the smallest element of $L$ is at least one. The proof is constructive. - [6] arXiv:2405.05381 [pdf, ps, other]
-
Title: Excluding disjoint Kuratowski graphsSubjects: Combinatorics (math.CO)
A graph is a ``$k$-Kuratowski graph'' if it has exactly $k$ components, each isomorphic to $K_5$ or to $K_{3,3}$. We prove that if a graph $G$ contains no $k$-Kuratowski graph as a minor,then there is a set $X$ of boundedly many vertices such that $G\setminus X$ can be drawn in a (possibly disconnected) surface in which no $k$-Kuratowski graph can be drawn.
- [7] arXiv:2405.05384 [pdf, ps, other]
-
Title: Excluding sums of Kuratowski graphsSubjects: Combinatorics (math.CO)
We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing $k$ copies of $K_5$ or $K_{3,3}$, if and only if it has bounded genus.
- [8] arXiv:2405.05483 [pdf, ps, other]
-
Title: Zero-one Grothendieck PolynomialsComments: 23 pages, 22 figuresSubjects: Combinatorics (math.CO)
Fink, M\'esz\'aros and St.Dizier showed that the Schubert polynomial $\mathfrak{S}_w(x)$ is zero-one if and only if $w$ avoids twelve permutation patterns. In this paper, we prove that the Grothendieck polynomial $\mathfrak{G}_w(x)$ is zero-one, i.e., with coefficients either 0 or $\pm$1, if and only if $w$ avoids six patterns. As applications, we show that zero-one homogeneous Grothendieck polynomials are Lorentzian, partially confirming three conjectures of Huh, Matherne, M\'esz\'aros and St.Dizier. Moreover, we verify several conjectures on the support and coefficients of Grothendieck polynomials posed by M\'{e}sz\'{a}ros, Setiabrata and St.Dizier for the case of zero-one Grothendieck polynomials.
- [9] arXiv:2405.05527 [pdf, ps, other]
-
Title: Boolean Structure ConstantsComments: 15 pagesSubjects: Combinatorics (math.CO)
The Schubert problem asks for combinatorial models to compute structure constants of the cohomology ring with respect to the Schubert classes, and has been an important open problem in algebraic geometry and combinatorics that guided fruitful research in decades. In this paper, we provide an explicit formula for the (equivariant) Schubert structure constants $c_{uv}^w$ across all Lie types when the elements $u,v,w$ are boolean. In particular, in type $A$, all Schubert structure constants on boolean elements are either $0$ or $1$.
- [10] arXiv:2405.05571 [pdf, other]
-
Title: Computing $\vec{\mathcal{S}}$-DAGs and Parity GamesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiederrecht introduced a new directed width measure, $\vec{\mathcal{S}}$-DAG-width, using directed separations and obtained a structural duality for it. In 2012 Berwanger~et~al.~solved Parity Games in polynomial time on digraphs of bounded DAG-width. With generalising this result to digraphs of bounded $\vec{\mathcal{S}}$-DAG-width and also providing an algorithm to compute the $\vec{\mathcal{S}}$-DAG-width of a given digraphs we give first algorithmical results for this new parameter.
- [11] arXiv:2405.05650 [pdf, ps, other]
-
Title: Variety of mutual-visibility problems in hypercubesSubjects: Combinatorics (math.CO)
Let $G$ be a graph and $M \subseteq V(G)$. Vertices $x, y \in M$ are $M$-visible if there exists a shortest $x,y$-path of $G$ that does not pass through any vertex of $M \setminus \{x, y \}$. We say that $M$ is a mutual-visibility set if each pair of vertices of $M$ is $M$-visible, while the size of any largest mutual-visibility set of $G$ is the mutual-visibility number of $G$. If some additional combinations for pairs of vertices $x, y$ are required to be $M$-visible, we obtain the total (every $x,y \in V(G)$ are $M$-visible), the outer (every $x \in M$ and every $y \in V(G) \setminus M$ are $M$-visible), and the dual (every $x,y \in V(G) \setminus M$ are $M$-visible) mutual-visibility set of $G$. The cardinalities of the largest of the above defined sets are known as the total, the outer, and the dual mutual-visibility number of $G$, respectively.
We present results on the variety of mutual-visibility problems in hypercubes. - [12] arXiv:2405.05812 [pdf, ps, other]
-
Title: The $cd$-index of semi-Eulerian posetsComments: Comments are welcomeSubjects: Combinatorics (math.CO)
We generalize the definition of the $cd$-index of an Eulerian poset to the class of semi-Eulerian posets. For simplicial semi-Eulerian Buchsbaum posets, we show that all coefficients of the $cd$-index are non-negative. This proves a conjecture of Novik for odd dimensional manifolds and extends it to the even dimensional case.
- [13] arXiv:2405.05867 [pdf, ps, other]
-
Title: Quasisymmetric Schur $Q$-functions and peak Young quasisymmetric Schur functionsComments: 51 pagesSubjects: Combinatorics (math.CO); Representation Theory (math.RT)
In this paper, we explore the relationship between quasisymmetric Schur $Q$-functions and peak Young quasisymmetric Schur functions. We introduce a bijection on $\mathsf{SPIT}(\alpha)$ such that $\{\mathrm{w}_{\rm c}(T) \mid T \in \mathsf{SPIT}(\alpha)\}$ and $\{\mathrm{w}_{\rm r}(T) \mid T \in \mathsf{SPIT}(\alpha)\}$ share identical descent distributions. Here, $\mathsf{SPIT}(\alpha)$ is the set of standard peak immaculate tableaux of shape $\alpha$, and $\mathrm{w}_{\rm c}$ and $\mathrm{w}_{\rm r}$ denote column reading and row reading, respectively. By combining this equidistribution with the algorithm developed by Allen, Hallam, and Mason, we demonstrate that the transition matrix from the basis of quasisymmetric Schur $Q$-functions to the basis of peak Young quasisymmetric Schur functions is upper triangular, with entries being non-negative integers. Furthermore, we provide explicit descriptions of the expansion of peak Young quasisymmetric Schur functions in specific cases, in terms of quasisymmetric Schur $Q$-functions. We also investigate the combinatorial properties of standard peak immaculate tableaux, standard Young composition tableaux, and standard peak Young composition tableaux. We provide a hook length formula for $\mathsf{SPIT}(\alpha)$ and show that standard Young composition tableaux and standard peak Young composition tableaux can be bijectively mapped to specific words in a familiar form. Especially, cases of compositions with rectangular shape are examined in detail.
- [14] arXiv:2405.05902 [pdf, ps, other]
-
Title: The largest subgraph without a forbidden induced subgraphComments: 20 pagesSubjects: Combinatorics (math.CO); Probability (math.PR)
We initiate the systematic study of the following Tur\'an-type question. Suppose $\Gamma$ is a graph with $n$ vertices such that the edge density between any pair of subsets of vertices of size at least $t$ is at most $1 - c$, for some $t$ and $c > 0$. What is the largest number of edges in a subgraph $G \subseteq \Gamma$ which does not contain a fixed graph $H$ as an induced subgraph or, more generally, which belongs to a hereditary property $\mathcal{P}$? This provides a common generalization of two recently studied cases, namely $\Gamma$ being a (pseudo-)random graph and a graph without a large complete bipartite subgraph. We focus on the interesting case where $H$ is a bipartite graph.
We determine the answer up to a constant factor with respect to $n$ and $t$, for certain bipartite $H$ and for $\Gamma$ either a dense random graph or a Paley graph with a square number of vertices. In particular, our bounds match if $H$ is a tree, or if one part of $H$ has $d$ vertices complete to the other part, all other vertices in that part have degree at most $d$, and the other part has sufficiently many vertices. As applications of the latter result, we answer a question of Alon, Krivelevich, and Samotij on the largest subgraph with a hereditary property which misses a bipartite graph, and determine up to a constant factor the largest number of edges in a string subgraph of $\Gamma$. The proofs are based on a variant of the dependent random choice and a novel approach for finding induced copies by inductively defining probability distributions supported on induced copies of smaller subgraphs.
Cross-lists for Fri, 10 May 24
- [15] arXiv:2405.05270 (cross-list from math.HO) [pdf, ps, other]
-
Title: Algorithmic methods of finite discrete structures. The Four Color Theorem. Theory, methods, algorithmsComments: 123 pages, in Ukrainian language, 140 figures, a preprint of monographySubjects: History and Overview (math.HO); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
The Four color problem is closely related to other branches of mathematics and practical applications. More than 20 of its reformulations are known, which connect this problem with problems of algebra, statistical mechanics and planning. And this is also typical for mathematics: the solution to a problem studied out of pure curiosity turns out to be useful in representing real objects and processes that are completely different in nature. Despite the published machine methods for combinatorial proof of the Four color conjecture, there is still no clear description of the mechanism for coloring a planar graph with four colors, its natural essence and its connection with the phenomenon of graph planarity. It is necessary not only to prove (preferably by deductive methods) that any planar graph can be colored with four colors, but also to show how to color it. The paper considers an approach based on the possibility of reducing a maximally flat graph to a regular flat cubic graph with its further coloring. Based on the Tate-Volynsky theorem, the vertices of a maximally flat graph can be colored with four colors, if the edges of its dual cubic graph can be colored with three colors. Considering the properties of a colored cubic graph, it can be shown that the addition of colors obeys the transformation laws of the fourth order Klein group. Using this property, it is possible to create algorithms for coloring planar graphs.
- [16] arXiv:2405.05273 (cross-list from math.HO) [pdf, ps, other]
-
Title: Lovasz' Conjecture and Other Applications of Topological Methods in Discrete MathematicsComments: 17 pages, 9 figuresSubjects: History and Overview (math.HO); Combinatorics (math.CO)
In 20th century mathematics, the field of topology, which concerns the properties of geometric objects under continuous transformation, has proved surprisingly useful in application to the study of discrete mathematics, such as combinatorics, graph theory, and theoretical computer science. In this paper, we seek to provide an introduction to the relevant topological concepts to non-specialists, as well as a selection of some existing applications to theorems in discrete mathematics.
- [17] arXiv:2405.05629 (cross-list from math.GT) [pdf, ps, other]
-
Title: Short proofs of Tverberg-type theorems for cell complexesSubjects: Geometric Topology (math.GT); Combinatorics (math.CO); Metric Geometry (math.MG)
We present short proofs of two Tverberg-type theorems for cell complexes by S. Hasui, D. Kishimoto, M. Takeda, and M. Tsutaya. One of them states that for any prime power $r$, any simplicial sphere $X$ of dimension $(d+1)(r-1)-1$, and any continuous map $f:X\to\mathbb R^d$ there are pairwise disjoint faces $\sigma_1,\ldots,\sigma_r$ of $X$ such that $f(\sigma_1)\cap\ldots f(\sigma_r)\ne\emptyset$.
- [18] arXiv:2405.05718 (cross-list from math.AG) [pdf, ps, other]
-
Title: Homological smoothness and Deligne resolution for tropical fansComments: 24 pages. arXiv admin note: text overlap with arXiv:2105.01504Subjects: Algebraic Geometry (math.AG); Algebraic Topology (math.AT); Combinatorics (math.CO)
We say that a tropical fan is homologically smooth if each of its open subsets verify tropical Poincare duality. A tropical homology manifold is a tropical variety that is locally modelled by open subsets of homologically smooth tropical fans.
We show that homological smoothness is a T-stable property in the category of tropical fans. This implies in particular that quasilinear fans are homologically smooth, and tropical varieties locally modelled by them are tropical homology manifolds. Previously, this was known only for locally matroidal tropical varieties.
In order to show the above results, we prove a tropical analogue of the Deligne weight spectral sequence for homologically smooth tropical fans. This allows to describe the cohomology of tropical modifications, and will be of importance in our companion work which develops a Hodge theory in the tropical setting. - [19] arXiv:2405.05954 (cross-list from math.MG) [pdf, other]
-
Title: The Gaussian measure of a convex body controls its maximal covering radiusAuthors: Maud SzustermanComments: 17 pages, 7 figuresSubjects: Metric Geometry (math.MG); Combinatorics (math.CO)
The well-studied vector balancing constant $\beta(U, V)$ of a pair of convex bodies $(U,V)$, is lower bounded by a lattice counterpart, $\alpha(U,V)$. In [BS97], Banaszczyk and Szarek proved that $\alpha(B_2^n, V)\leq c$ when $V$ has Gaussian measure at least $\frac{1}{2}$, and conjectured that, for centrally symmetric $V$, $\beta(B_2^n, V)$ is always bounded by a function of the Gaussian measure of $V$, independent of $n$. We resolve this conjecture in the affirmative. Moreover, we show that the analogous result holds for $\alpha(B_2^n, V)$ even without the central symmetry assumption.
Replacements for Fri, 10 May 24
- [20] arXiv:2301.09457 (replaced) [pdf, ps, other]
-
Title: Blocking sets, minimal codes and trifferent codesComments: Simplified proofs based on the comments by the refereeSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
- [21] arXiv:2302.02190 (replaced) [pdf, ps, other]
-
Title: An Alon-Tarsi Style Theorem for Additive ColoringsAuthors: Ian GossettComments: 12 pages. Preprint version. Peer-reviewed version to appear in Graphs and CombinatoricsSubjects: Combinatorics (math.CO)
- [22] arXiv:2304.08003 (replaced) [pdf, ps, other]
-
Title: Monochromatic cycles in 2-edge-colored bipartite graphs with large minimum degreeSubjects: Combinatorics (math.CO)
- [23] arXiv:2310.03230 (replaced) [pdf, other]
-
Title: The squish map and the $\text{SL}_2$ double dimer modelComments: 22 pages, 17 figures May 8 Revision: Corrected typosJournal-ref: Electron. J. Combin.31(2024), no.1, Paper No. 1.61, 24 ppSubjects: Combinatorics (math.CO)
- [24] arXiv:2311.09072 (replaced) [pdf, ps, other]
-
Title: From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSPComments: ICALP 2024Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
- [25] arXiv:2211.03987 (replaced) [pdf, ps, other]
-
Title: Theta series of ternary quadratic lattice cosetsSubjects: Number Theory (math.NT); Combinatorics (math.CO)
- [26] arXiv:2212.01917 (replaced) [pdf, ps, other]
-
Title: Möbius function of the subgroup lattice of a finite group and Euler CharacteristicComments: 10 pages. Revised version; the first version contained some inaccuracies that have been correctedSubjects: Group Theory (math.GR); Combinatorics (math.CO)
- [27] arXiv:2307.02579 (replaced) [pdf, ps, other]
-
Title: d-Fold Partition DiamondsComments: 16 pages, 3 figures; v3: to appear in Discrete MathematicsSubjects: Number Theory (math.NT); Combinatorics (math.CO)
- [28] arXiv:2404.11529 (replaced) [pdf, ps, other]
-
Title: The distribution on permutations induced by a random parking functionAuthors: Ross G. PinskyComments: This version is greatly expanded from the first version, and includes a lot more resultsSubjects: Probability (math.PR); Combinatorics (math.CO)
[ showing up to 2000 entries per page: fewer | more ]
Disable MathJax (What is MathJax?)
Links to: arXiv, form interface, find, math, recent, 2405, contact, help (Access key information)