Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

6
votes
0answers
96 views

Inequality among domino tilings of large triomino shapes

Inspired by this question, which asks for what shape maximizes the number of domino tilings, I want to ask the following seemingly simpler question, which I have been thinking about for a while: ...
15
votes
5answers
587 views

The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect. What is the ...
14
votes
2answers
564 views

A conjecture about $\lfloor n!\cdot q/e\rfloor-\,!n\cdot q$

I was thinking about this question asked at Math.SE, when I came up with the following conjecture. For every $q\in\mathbb Q$ consider a sequence $s_n^{(q)}$ (terms within the sequence are indexed by ...
3
votes
1answer
102 views

Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...
0
votes
1answer
107 views

An asymptotic intersection problem

Given a set of $n\in\Bbb N$ integers $\mathcal S$ and $\mathsf s,\mathsf t\in\big(0,1\big)$, suppose we choose two sets: $$\mathcal S_{\mathsf{1}}\subseteq\mathcal S$$ $$\mathcal ...
0
votes
0answers
39 views

Is the laplacian spectral radius of a directed grpah a non-decreasing function?

Given a directed graph G and its respective laplacian matrix $L = D-A$ where $A$ is the adjacency matrix ($A_{ij}=1$ if there is a link from $j$ to $i$ and $A_{ij}=0$ otherwise) and D is the diagonal ...
5
votes
1answer
232 views

$(n-2)$-blocking sets in $AG(n,2)$

Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$. I have seen a lot work related to minimal $(n-1)$-blockings set. ...
4
votes
2answers
310 views

Can you simplify (or approximate) $\sum_{n=0}^{N-1}\begin{pmatrix}N-1\\n\end{pmatrix}\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\begin{pmatrix}x\\y\end{pmatrix}$ be the binomial coefficient. I am trying to get a better understanding of the sum \begin{equation} ...
2
votes
3answers
203 views

Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...
7
votes
1answer
93 views

When is the diagonal of a rational bivariate power series again rational

Given a rational bivariate power series $F(x,y)=\sum{a_{n,m}x^ny^m}$, the diagonal function $G(t):=\sum{a_{n,n}t^n}$ is known to be algebraic, although not rational in general. I was wondering if ...
19
votes
0answers
306 views

Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
8
votes
1answer
312 views

Removing singularities in generating functions

This is a problem about the practicalities of removing singularities in multivariable complex functions. In trying to derive the generating function (in two variables) for a certain problem in ...
1
vote
2answers
72 views

Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example. Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...
4
votes
0answers
71 views

A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...
6
votes
2answers
262 views

extremal bipartite graph

I'm facing the following question: Given a bipartite graph $G = (L \cup R, E)$. Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$. What is a minimal possible number ...
6
votes
1answer
243 views

Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...
4
votes
1answer
87 views

Is there a nice form for the Frobenius characteristic of a border shape character?

Let $\chi^V$ be the character of a border strip Specht module, i.e. a Specht module for a skew tableau that contains no $2 \times 2$ square. I know that the Frobenius characteristic of $\chi^V$ is ...
2
votes
0answers
131 views

On sets of coprime numbers

We know that from prime number theorem that the number of primes below $n$ and above $\frac n2$ (denoted by $\pi_{n,\frac n2}$ is approximately $$\pi_{n,\frac n2}\approx\frac{n}{2\ln n}.$$ Denote by ...
2
votes
3answers
294 views

An identity involving a product of two binomial coefficients

I'm trying to find a closed formula (in the parameters $q,N$) for the following sum: $$ \sum_{k=q}^{N} {{k-1}\choose{q-1}} {{k}\choose {q}} $$ Can anybody give me a lead? Lior
7
votes
2answers
239 views

A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891). My question is in ...
-1
votes
2answers
73 views

Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves. Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...
1
vote
1answer
107 views

Strongly connected graph and the eigenvalues of the laplacian matrix

Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. Reformulation of this definition: $G$ is strongly connected iff for any ...
0
votes
1answer
67 views

An asymptotic set containment problem [closed]

Given a set of $n\in\Bbb N$ integers $\mathcal S$, suppose we choose two sets: $$\mathcal S_{\mathsf{small}}\subseteq\mathcal S$$ $$\mathcal S_{\mathsf{big}}\subseteq\mathcal S$$ with cardinalities ...
4
votes
1answer
264 views

Number of different positions of rooks on chessboard

I know that this topic as been mentioned before, but no accurate answer has been provided. Suppose we have to place $n$ rooks on $n \times n$ chessboard so that no one attacks another. How to count ...
7
votes
2answers
254 views

Distribution of $\max_{n \ge 0} S_n$, random walk

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
0
votes
2answers
106 views

Infinite k-connected planar graphs

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces. I know that to construct such graph, For $k ...
4
votes
1answer
198 views

Combinatorial description of a 120-cell

I'd like a combinatorial description of the 1-skeleton of the 120-cell (roughly) along the lines of the following description of the 1-skeleton of a dodecahedron. (View all elements of product sets ...
19
votes
1answer
622 views

Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$

When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following: Problem. We have a surface of a cube $n\times n \times n$ such that each ...
4
votes
1answer
80 views

Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders? Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...
2
votes
1answer
130 views

Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that (Hadw): $K_{\chi(G)}$ is a minor of $G$. It turns out that for finite graphs, (Hadw) is equivalent to the ...
4
votes
1answer
120 views

Existence of an infinite word with a predetermined asymptotic for the word complexity

Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$ Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of ...
1
vote
1answer
50 views

Summation of multinominal coefficients with extra bounds on summation indices

My question is related to the sum \begin{equation} S(n,N) = \sum_{k_1+k_2+...+k_N=n}\frac{n!}{(k_1!)\cdot(k_2!)\cdot...\cdot(k_N!)} = N^n, \end{equation} which is comes from the multinomial ...
2
votes
0answers
51 views

The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...
3
votes
1answer
90 views

Number and asymptotic for cyclic sequences

Cyclic sequence is equivalence class of cyclic shift action. If $a = (a_1, ... , a_i)_c$ is cyclic sequence then $(a_1, a_2, \ldots a_{i-1}, a_i)_c = (a_2, a_3, \ldots, a_i, a_1)_c = \ldots = (a_i, ...
0
votes
1answer
124 views

For a set of positive integers, is this inequality always true?

The input consists of a set of positive integers $\{b_1,...,b_2\}$ such that $$\sum_{i=1}^nb_i=CK,$$ with $C$ and $K$ two positive integers. The question is the following, is there $k\in\{1,...,n\}$ ...
3
votes
1answer
134 views

Asymptotic for binomial sums

Let $S(n, t) = \sum_{k = 0}^n {n \choose k} ^t$. The task is to find asymptotic behavior of $S(n,5)$, $n \to \infty$. Asymptotic for $S(n,0)$ and $S(n,1)$ is very simple. For $S(n,2)$ we can use ...
5
votes
1answer
75 views

Reference for restriction formula in terms of double Schubert polynomials

Everyone (that is, everyone who cares) knows that double Schubert polynomials represent Schubert classes in equivariant cohomology in type $A$. We also know that we can restrict Schubert classes to ...
4
votes
1answer
201 views

Summation of an infinite q-series

When calculating a Partition function, I encounter the following summation $$\sum_{n=0}^{\infty} x^n q^{n^2}.$$ I know that the sum $\sum_{n=-\infty}^{\infty} x^n q^{n^2}$ is a Theta function, but I ...
6
votes
0answers
87 views

By replacing the Laver tables with nearly distributive fake Laver tables, can one produce algebras where the period of 1 grows fast?

I am now generalizing the notion of the classical Laver table and the fake Laver table to a larger class of algebras. A sequence of algebras $(\{1,...,2^{n}\},*_{n})_{n\in\omega}$ is said to be a ...
6
votes
0answers
115 views

How distributive are the fake Laver tables?

The Laver table $A_{n}$ is the unique algebra $(\{1,...,2^{n}\},*)$ such that $x*1=x+1$ for $1\leq x<2^{n}$, $2^{n}*1=1$, and $x*(y*z)=(x*y)*(x*z)$. Let's now replace the Laver table $A_{n}$ with ...
5
votes
1answer
168 views

Is this subset-sum-type problem discussed in the literature?

Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least ...
3
votes
0answers
120 views

How to prove $\prod_{\lambda\vdash n}\prod_im_i(\lambda)!=\prod_{\lambda\vdash n}1^{m_1(\lambda)}2^{m_2(\lambda)}\cdots$

Let $\lambda$ be a partition of an positive integer $n$, it can be presented as $\lambda=(\lambda_{1},\lambda_2,\cdots,\lambda_l)$ such that $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_l>0$, or ...
3
votes
0answers
47 views

How to prove that $\sum_{i=0}^n\frac{(a;q)_i}{(q;q)_i}\frac{(b;q)_{n-i}}{(q;q)_{n-i}}a^{n-i}=\frac{(ab;q)_n}{(q;q)_n}$?

By Cauchy identity, $${}_1\phi_0(a;—;q,z)=\sum_{n\geq0}\frac{(a;q)_n}{(q;q)_n}z^n=\frac{(az;q)_{\infty}}{(z;q)_\infty},\quad|z|<1,|q|<1,$$ we can obtain the $q-$analogue of ...
5
votes
0answers
97 views

(Double) Crystal reflection operators on SSYTs

I am not that familiar with the language of crystals, but this is what I know: Let $SSYT(\lambda, \mu)$ be the set of semi-standard Young tableaux with shape $\lambda$ and weight $\mu$. There are ...
6
votes
2answers
333 views

Sums of reciprocals of products of factorials

Let $d,m, r$ be positive integers, and define $$ S = \left\{ (i_1, i_2, \dots, i_m) \in {\bf Z}_{+}^{m} \left | \sum_j i_j = d; \& \forall j, i_j \leq r \right. \right\}; $$ Here ${\bf Z}_+$ ...
8
votes
0answers
101 views

Product of Partial Orders

Define the transpose product of a partial order $P$ over a set $S$ in the following way. The direct product of a partial order $P \subseteq S \times S$ and its converse, $P^{op}$, gives a partial ...
7
votes
2answers
137 views

$f$-vector of simple convex polytope via directions of facets

Let $P$ be a simple convex polytope in $\mathbb{R}^d$ (that is, any vertex belongs to exactly $d+1$ facets). Given the collection of outer normals to facets of $P$, combinatorics of $P$ may be ...
1
vote
1answer
73 views

Probability of paths to the boundary of a tree

Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...
5
votes
1answer
154 views

Intersection of rotating regular polygons

This question has a recreational flavor, but may not be entirely uninteresting. Let $P_k$ be a unit-radius regular polygon of $k$ sides, and $P_n$ a unit-radius regular polygon of $n \ge k$ sides. ...
12
votes
2answers
833 views

On Hamkins' answer to a problem by Michael Hardy

Based on a post by Michael Hardy and Hamkins' answer to it Andreas Blass, Will Brian, Joel Hamkins, Michael Hardy and Paul Larson introduced a new cardinal characteristic of the continuum ...