Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let L be a finite lattice. Inspired by Ungar’s solution to the famous slopes problem, we define an Ungar move to be an operation that sends an element \(x\in L\) to the meet of \(\{x\}\cup T\) , where T is a subset of the set of elements covered by x. We introduce the following Ungar game. Starting at the top element of L, two players—Atniss and Eeta—take turns making nontrivial Ungar moves; the first player who cannot do so loses the game. Atniss plays first. We say L is an Atniss win (respectively, Eeta win) if Atniss (respectively, Eeta) has a winning strategy in the Ungar game on L. We first prove that the number of principal order ideals in the weak order on \(S_n\) that are Eeta wins is \(O(0.95586^nn!)\) . We then consider a broad class of intervals in Young’s lattice that includes all principal order ideals, and we characterize the Eeta wins in this class; we deduce precise enumerative results concerning order ideals in rectangles and type-A root posets. We also characterize and enumerate principal order ideals in Tamari lattices that are Eeta wins. Finally, we conclude with some open problems and a short discussion of the computational complexity of Ungar games. PubDate: 2024-02-21

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The defective chromatic number of a graph class is the infimum k such that there exists an integer d such that every graph in this class can be partitioned into at most k induced subgraphs with maximum degree at most d. Finding the defective chromatic number is a fundamental graph partitioning problem and received attention recently partially due to Hadwiger’s conjecture about coloring minor-closed families. In this paper, we prove that the defective chromatic number of any minor-closed family equals the simple lower bound obtained by the standard construction, confirming a conjecture of Ossona de Mendez, Oum, and Wood. This result provides the optimal list of unavoidable finite minors for infinite graphs that cannot be partitioned into a fixed finite number of induced subgraphs with uniformly bounded maximum degree. As corollaries about clustered coloring, we obtain a linear relation between the clustered chromatic number of any minor-closed family and the tree-depth of its forbidden minors, improving an earlier exponential bound proved by Norin, Scott, Seymour, and Wood and confirming the planar case of their conjecture. PubDate: 2024-02-21

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper we prove that every totally real algebraic integer \(\lambda \) of degree \(d \ge 2\) occurs as an eigenvalue of some tree of height at most \(d(d+1)/2+3\) . In order to prove this, for a given algebraic number \(\alpha \ne 0\) , we investigate an additive semigroup that contains zero and is closed under the map \(x \mapsto \alpha /(1-x)\) for \(x \ne 1\) . The problem of finding the smallest such semigroup seems to be of independent interest. PubDate: 2024-02-02

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We give a short constructive proof for the existence of a Hamilton cycle in the subgraph of the \((2n+1)\) -dimensional hypercube induced by all vertices with exactly n or \(n+1\) many 1s. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let \(n \ge 2k \ge 4\) be integers, \({[n]\atopwithdelims ()k}\) the collection of k-subsets of \([n] = \{1, \ldots , n\}\) . Two families \({\mathcal {F}}, {\mathcal {G}} \subset {[n]\atopwithdelims ()k}\) are said to be cross-intersecting if \(F \cap G \ne \emptyset \) for all \(F \in {\mathcal {F}}\) and \(G \in {\mathcal {G}}\) . A family is called non-trivial if the intersection of all its members is empty. The best possible bound \( {\mathcal {F}} + {\mathcal {G}} \le {n \atopwithdelims ()k} - 2 {n - k\atopwithdelims ()k} + {n - 2k \atopwithdelims ()k} + 2\) is established under the assumption that \({\mathcal {F}}\) and \({\mathcal {G}}\) are non-trivial and cross-intersecting. For the proof a strengthened version of the so-called shifting technique is introduced. The most general result is Theorem 4.1. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The size-Ramsey number \({\hat{r}}(G')\) of a graph \(G'\) is defined as the smallest integer m so that there exists a graph G with m edges such that every 2–coloring of the edges of G contains a monochromatic copy of \(G'\) . Answering a question of Beck, Rödl and Szemerédi showed that for every \(n\ge 1\) there exists a graph \(G'\) on n vertices each of degree at most three, with size-Ramsey number at least \(cn\log ^{\frac{1}{60}}n\) for a universal constant \(c>0\) . In this note we show that a modification of Rödl and Szemerédi’s construction leads to a bound \({\hat{r}}(G')\ge cn\,\exp (c\sqrt{\log n})\) . PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract An \(\alpha ,\beta \) -Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors \(\alpha \) and \(\beta \) . Two k-colorings of a graph are k-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than k colors). Las Vergnas and Meyniel showed that if a graph is \((k-1)\) -degenerate, then each pair of its k-colorings are k-Kempe equivalent. Mohar conjectured the same conclusion for connected k-regular graphs. This was proved for \(k=3\) by Feghali, Johnson, and Paulusma (with a single exception \(K_2\square \,K_3\) , also called the 3-prism) and for \(k\ge 4\) by Bonamy, Bousquet, Feghali, and Johnson. In this paper we prove an analogous result for list-coloring. For a list-assignment L and an L-coloring \(\varphi \) , a Kempe swap is called L-valid for \(\varphi \) if performing the Kempe swap yields another L-coloring. Two L-colorings are called L-equivalent if we can form one from the other by a sequence of L-valid Kempe swaps. Let G be a connected k-regular graph with \(k\ge 3\) and \(G\ne K_{k+1}\) . We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only \(K_2\square \,K_3\) ). Further, if \(G\in \{K_{k+1},K_2\square \,K_3\}\) , L is a \(\Delta \) -assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When \(k\ge 4\) , the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let H be a graph such that for every degree-assignment \(L_H\) all \(L_H\) -colorings are \(L_H\) -equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment \(L_G\) for G all \(L_G\) -colorings are \(L_G\) -equivalent. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980 s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363–370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai’s problems by constructing an infinite family of s-arc-transitive digraphs for each integer \(s\ge 2\) , and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function \(f:\mathbb {N}\rightarrow \mathbb {N}\cup \{\infty \}\) with \(f(1)=1\) and \(f(n)\geqslant \left( {\begin{array}{c}3n+1\\ 3\end{array}}\right) \) , we construct a hereditary class of graphs \({\mathcal {G}}\) such that the maximum chromatic number of a graph in \({\mathcal {G}}\) with clique number n is equal to f(n) for every \(n\in \mathbb {N}\) . In particular, we prove that there exist hereditary classes of graphs that are \(\chi \) -bounded but not polynomially \(\chi \) -bounded. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We prove that, for every graph F with at least one edge, there is a constant \(c_F\) such that there are graphs of arbitrarily large chromatic number and the same clique number as F in which every F-free induced subgraph has chromatic number at most \(c_F\) . This generalises recent theorems of Briański, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every \(r\geqslant 3\) the class of \(K_r\) -free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We show that if a finite point set \(P\subseteq {\mathbb {R}}^2\) has the fewest congruence classes of triangles possible, up to a constant M, then at least one of the following holds. There is a \(\sigma >0\) and a line l which contains \(\Omega ( P ^\sigma )\) points of P. Further, a positive proportion of P is covered by lines parallel to l each containing \(\Omega ( P ^\sigma )\) points of P. There is a circle \(\gamma \) which contains a positive proportion of P. This provides evidence for two conjectures of Erdős. We use the result of Petridis–Roche–Newton–Rudnev–Warren on the structure of the affine group combined with classical results from additive combinatorics. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: A sweep of a point configuration is any ordered partition induced by a linear functional. Posets of sweeps of planar point configurations were formalized and abstracted by Goodman and Pollack under the theory of allowable sequences of permutations. We introduce two generalizations that model posets of sweeps of higher dimensional configurations. Sweeps of a point configuration are in bijection with faces of an associated sweep polytope. Mimicking the fact that sweep polytopes are projections of permutahedra, we define sweep oriented matroids as strong maps of the braid oriented matroid. Allowable sequences are then the sweep oriented matroids of rank 2, and many of their properties extend to higher rank. We show strong ties between sweep oriented matroids and both modular hyperplanes and Dilworth truncations from (unoriented) matroid theory. Pseudo-sweeps are a generalization of sweeps in which the sweeping hyperplane is allowed to slightly change direction, and that can be extended to arbitrary oriented matroids in terms of cellular strings. We prove that for sweepable oriented matroids, sweep oriented matroids provide a sphere that is a deformation retract of the poset of pseudo-sweeps. This generalizes a property of sweep polytopes (which can be interpreted as monotone path polytopes of zonotopes), and solves a special case of the strong Generalized Baues Problem for cellular strings. A second generalization are allowable graphs of permutations: symmetric sets of permutations pairwise connected by allowable sequences. They have the structure of acycloids and include sweep oriented matroids. PubDate: 2024-02-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Given a (thick) irreducible spherical building \(\Omega \) , we establish a bound on the difference between the generating rank and the embedding rank of its long root geometry and the dimension of the corresponding Weyl module, by showing that this difference does not grow when taking certain residues of \(\Omega \) (in particular the residue of a vertex corresponding to a point of the long root geometry, but also other types of vertices occur). We apply this to the finite case to obtain new results on the generating rank of mainly the exceptional long root geometries, answering an open question by Cooperstein about the generating ranks of the exceptional long root subgroup geometries. We completely settle the finite case for long root geometries of type \({{\textsf{A}}}_n\) , and the case of type \(\mathsf {F_{4,4}}\) over any field with characteristic distinct from 2 (which is not a long root subgroup geometry, but a hexagonic geometry). PubDate: 2024-01-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract For strongly connected, pure n-dimensional regular CW-complexes, we show that evenness (each \((n{-}1)\) -cell is contained in an even number of n-cells) is equivalent to generalizations of both cycle decomposition and traversability. PubDate: 2024-01-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A topological version of the famous Hedetniemi conjecture says: The mapping index of the Cartesian product of two \({\mathbb {Z}}/2\) - spaces is equal to the minimum of their \({\mathbb {Z}}/2\) -indexes. The main purpose of this article is to study the topological version of the Hedetniemi conjecture for G-spaces. Indeed, we show that the topological Hedetniemi conjecture cannot be valid for general pairs of G-spaces. More precisely, we show that this conjecture can possibly survive if the group G is either a cyclic p-group or a generalized quaternion group whose size is a power of 2. PubDate: 2023-12-19

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We show that every graph with pathwidth strictly less than a that contains no path on \(2^b\) vertices as a subgraph has treedepth at most 10ab. The bound is best possible up to a constant factor. PubDate: 2023-12-19

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract For \(0 \le t \le r\) let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance \(m(3,3)=m(4,r)=1\) , and \(m(t,r) \le r-2\) for all \(t \not = 5\) , and \(m(t,r) \le r-3\) if r is even. We prove that \(m(2l,r) \le 3l - 6\) for every \(l \ge 3\) and \(r \ge 2 l\) . PubDate: 2023-12-19

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A family \({\mathcal {F}}\) on ground set \([n]:=\{1,2,\ldots , n\}\) is maximal k-wise intersecting if every collection of at most k sets in \({\mathcal {F}}\) has non-empty intersection, and no other set can be added to \({\mathcal {F}}\) while maintaining this property. In 1974, Erdős and Kleitman asked for the minimum size of a maximal k-wise intersecting family. We answer their question for \(k=3\) and sufficiently large n. We show that the unique minimum family is obtained by partitioning the ground set [n] into two sets A and B with almost equal sizes and taking the family consisting of all the proper supersets of A and of B. PubDate: 2023-12-01 DOI: 10.1007/s00493-023-00046-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study families \({\mathcal {F}}\subseteq 2^{[n]}\) with restricted intersections and prove a conjecture of Snevily in a stronger form for large n. We also obtain stability results for Kleitman’s isodiametric inequality and families with bounded set-wise differences. Our proofs introduce a new twist to the classical linear algebra method, harnessing the non-shadows of \({\mathcal {F}}\) , which may be of independent interest. PubDate: 2023-12-01 DOI: 10.1007/s00493-023-00053-4

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Huynh et al. recently showed that a countable graph G which contains every countable planar graph as a subgraph must contain arbitrarily large finite complete graphs as topological minors, and an infinite complete graph as a minor. We strengthen this result by showing that the same conclusion holds if G contains every countable planar graph as a topological minor. In particular, there is no countable planar graph containing every countable planar graph as a topological minor, answering a question by Diestel and Kühn. Moreover, we construct a locally finite planar graph which contains every locally finite planar graph as a topological minor. This shows that in the above result it is not enough to require that G contains every locally finite planar graph as a topological minor. PubDate: 2023-11-21 DOI: 10.1007/s00493-023-00073-0