Combinatorics (math.CO)

Abstract: We consider the following card guessing game with no feedback. An ordered deck of n cards labeled 1 up to n is riffle-shuffled exactly one time. Then, the goal of the game is to maximize the number of correct guesses of the cards. One after another a single card is drawn from the top, the guesser makes a guess without seeing the card and gets no response if the guess was correct or not. Building upon and improving earlier results, we provide a limit law for the number of correct guesses and also show convergence of the integer moments.

Abstract: The aim of this article is to continue the study of the notion of $\lambda$-quiddity over a ring, which appeared during the study of Coxeter's friezes. For this, we will focus here on situations where the ring used can be seen as a direct product of unitary commutative rings. In particular, we will consider the cases of direct products of rings containing at least two rings of characteristic 0 and we will also consider some products of the type $\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$.

Abstract: This paper introduces the concept of weak$^*$ degeneracy of a graph that shares many nice properties of degeneracy. We prove that for any $f: V(G) \to \mathbb{N}$, if $G$ is weak$^*$ $f$-degenerate, then $G$ is DP-$f$-paintable and $f$-AT. Hence the weak$^*$ degeneracy of $G$ is an upper bound for many colouring parameters, including the online DP-chromatic number and the Alon-Tarsi number. Let $k$ be a positive integer and let $f(v)=\min\{d_G(v), k\}$ for each vertex $v$ of $G$. If $G$ is weak$^*$ $f$-degenerate (respectively, $f$-choosable), then we say $G$ is weak$^*$ $k$-truncated-degree--degenerate (respectively, $k$-truncated-degree-choosable). Richtor asked whether every 3-connected non-complete planar graph is $6$-truncated-degree-choosable. We construct a 3-connected non-complete planar graph which is not $7$-truncated-degree-choosable, so the answer to Richtor's question is negative even if 6 is replaced by 7. Then we prove that every 3-connected non-complete planar graph is weak$^*$ $16$-truncated-degree-degenerate (and hence $16$-truncated-degree-choosable). For an arbitrary proper minor closed family ${\mathcal G}$ of graphs, let $s$ be the minimum integer such that $K_{s,t} \notin \mathcal{G}$ for some $t$. We prove that there is a constant $k$ such that every $s$-connected non-complete graph $G \in {\mathcal G}$ is weak$^*$ $k$-truncated-degree-degenerate. In particular, for any surface $\Sigma$, there is a constant $k$ such that every 3-connected non-complete graph embeddable on $\Sigma$ is weak$^*$ $k$-truncated-degree-degenerate.

Abstract: A graph $G = (\{1, 2, \ldots, n\}, E)$ is $12$-representable if there is a word $w$ over $\{1, 2, \ldots, n\}$ such that two vertices $i$ and $j$ with $i < j$ are adjacent if and only if every $j$ occurs before every $i$ in $w$. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of $12$-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs represented by pattern-avoiding words. Following this research direction, this paper studies $12$-representable graphs represented by words that avoid a pattern $p$. Such graphs are trivial when $p$ is of length $2$. When $p = 111$, $121$, $231$, and $321$, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where $p = 123$, $132$, and $211$, this paper provides forbidden pattern characterizations.

Abstract: We study $k$-star decompositions, that is, partitions of the edge set into disjoint stars with $k$ edges, in the uniformly random $d$-regular graph model $\mathcal{G}_{n,d}$. We prove an existence result for such decompositions for all $d,k$ such that $d/2 < k \leq d/2 + \max\{1,\frac{1}{6}\log d\}$. More generally, we give a sufficient existence condition that can be checked numerically for any given values of $d$ and $k$. Complementary negative results are obtained using the independence ratio of random regular graphs. Our results establish an existence threshold for $k$-star decompositions in $\mathcal{G}_{n,d}$ for all $d\leq 100$ and $k > d/2$, and strongly suggest the a.a.s. existence of such decompositions is equivalent to the a.a.s. existence of independent sets of size $(2k-d)n/(2k)$, subject to the necessary divisibility conditions on the number of vertices. For smaller values of $k$, the connection between $k$-star decompositions and $\beta$-orientations allows us to apply results of Thomassen (2012) and Lov\'asz, Thomassen, Wu and Zhang (2013). We prove that random $d$-regular graphs satisfy their assumptions with high probability, thus establishing a.a.s. existence of $k$-star decompositions (i) when $2k^2+k\leq d$, and (ii) when $k$ is odd and $k < d/2$.

Abstract: Consider Young diagrams of $n$ boxes distributed according to the Plancherel measure. So those diagrams could be the output of the RSK algorithm, when applied to random permutations of the set $\{1,\ldots,n\}$. Here we are interested in asymptotics, as $n\to \infty$, of expectations of certain functions of random Young diagrams, such as the number of bumping steps of the RSK algorithm that leads to that diagram, the side length of its Durfee square, or the logarithm of its probability. We can express these functions in terms of hook lengths or contents of the boxes of the diagram, which opens the door for application of known polynomiality results for Plancherel averages. We thus obtain representations of expectations as binomial convolutions, that can be further analyzed with the help of Rice's integral or Poisson generating functions. Among our results is a very explicit expression for the constant appearing in the almost equipartition property of the Plancherel measure.

Abstract: The $d$-process generates a graph at random by starting with an empty graph with $n$ vertices, then adding edges one at a time uniformly at random among all pairs of vertices which have degrees at most $d-1$ and are not mutually joined. We show that, in the evolution of a random graph with $n$ vertices under the $d$-process, with high probability, for each $j \in \{0,1,\dots,d-2\}$, the minimum degree jumps from $j$ to $j+1$ when there are $\Theta(\ln(n)^{d-j-1})$ steps left. This answers a question of Ruci\'nski. More specifically, we show that, when the last vertex of degree $j$ disappears, the number of steps left divided by $\ln(n)^{d-j-1}$ converges in distribution to the exponential random variable of mean $\frac{j!}{2(d-1)!}$; furthermore, these $d-1$ distributions are independent.

Abstract: In 1975, Erd\H{o}s asked the following natural question: What is the maximum number of edges that an $n$-vertex graph can have without containing a cycle with all diagonals? Erd\H{o}s observed that the upper bound $O(n^{5/3})$ holds since the complete bipartite graph $K_{3,3}$ can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this old problem. We prove that there exists a constant $C$ such that every $n$-vertex with $Cn^{3/2}$ edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without a four-cycle based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an `almost-spanning' robust expander which might be of independent interest.