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)

5
votes
0answers
75 views

Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
12
votes
2answers
508 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
2
votes
0answers
39 views

Euclidean minimum spanning trees intersecting each unit square

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an ...
10
votes
2answers
490 views

Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is: For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...
-2
votes
1answer
53 views

How does deletion-contraction affect chromatic number? Can it increase chromatic number? [on hold]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...
9
votes
1answer
263 views
+150

Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$. I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...
5
votes
0answers
95 views

Representing one diagonal of Pascal's triangle using special sums coming from a different diagonal

Let $m, n$ be any fixed natural numbers. Is it true that infinitely many elements of the sequence $\left(\begin{array}{c} m+k \\ m \\ \end{array}\right)_{k=1,2,3,...}$ ( as well as of the sequence ...
8
votes
1answer
183 views

Determinant of a checkerboard Hankel matrix with Catalan numbers

My goal is to compute \begin{equation} I = \det \left(\mathbf{I} + \mathbf{A}\right) \end{equation} where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers: $$ \left\{ ...
10
votes
0answers
144 views

How long can a cycle of antichains in a finite partial order be?

Suppose that $X$ is a finite partially ordered set. Then a subset $A\subseteq X$ is said to be an antichain if there do not exist elements $a,b\in A$ with $a<b$. Let $\mathcal{A}_{X}$ be the set of ...
0
votes
1answer
78 views

Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties: The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it). $T$ has a ...
4
votes
1answer
217 views

Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...
10
votes
0answers
147 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
10
votes
1answer
232 views

Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?
3
votes
1answer
307 views

Is this version of van der Waerden's Theorem consistent with ZFC?

One way to phrase van der Waerden's Theorem is: For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...
8
votes
1answer
683 views

When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, ...
5
votes
3answers
407 views

Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...
0
votes
0answers
51 views

Sum of weighted permutations over natural numbers [on hold]

If we consider the sum $\sum\limits_{i=1}^n i\sigma(i)$ where $\sigma$ is a permutation of the first $n$ natural numbers, then this sum has a few interesting properties for various values of $n$. My ...
0
votes
0answers
16 views

Binary strings and one-to-one correspondence [on hold]

Assume T be the set of binary strings of length 30 with 10 1’s and 20 0’s. Let X be the set of the first 30 positive integers {1,2,3,…,30}. Let Y be the set of all subsets of X containing 10 numbers. ...
1
vote
1answer
67 views

Coxeter Isometry groups whose center has torsion

I'm looking for examples of Riemannian manifolds M of dimension $\geq 2$ such that the isometry group $Isom(M)$ contains as subgroup a finite Coxeter group $G$ such that $Tor(Z(G))$, the torsion group ...
7
votes
1answer
1k views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
2
votes
0answers
58 views

A basic minimization problem over finite fields

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod ...
1
vote
1answer
136 views

Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set $$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$. and $$ Q_d := [-1,1]^d.$$ I am interest in ...
1
vote
1answer
80 views

Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph. It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...
0
votes
0answers
66 views

Counting ways to Arrange Variable Sized Objects into Fixed Number of Spaces [on hold]

I scoured the web for a generalized notion of balls and bin that encompasses the needs of my questions. Essentially, I'm looking for a way count the number of ways to fit i different types of objects, ...
5
votes
1answer
143 views

A generalization of Erdős–Newman–Mirsky?

Given a sequence $S$ of natural numbers, write ${\bf Gap}(S)$ for the set of differences between consecutive terms. (So $|{\bf Gap}(S)|=1$ precisely for arithmetic progressions, hence the connection ...
9
votes
0answers
131 views

No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that: An important difference between the Plancherel measures and ...
6
votes
3answers
406 views

Conditions for an analogue of Cauchy-Davenport for simple groups

What conditions would be sufficient for a generalization of Cauchy-Davenport for simple groups? I can see two possible difficulties with a generalization for general groups: The sets could both be ...
1
vote
0answers
47 views

Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...
0
votes
0answers
31 views

the number of $n\times n$ matrices of 0's and 1's such that every row and column has three 1's [migrated]

In the Example 1.1.3 of Stanley's book Enumerative Combinatorics Vol 1 (2nd edition), an explicit formula for the number of $n\times n$ matrices of 0's and 1's such that every row and column has three ...
5
votes
1answer
126 views

Integer decomposition of dilated integral polytopes

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$. Question: Given $d > n + 2$ is it true that $$ ...
1
vote
1answer
193 views

A Bernstein-like Combinatorial Sum

Do sums of the "convoluted Bernstein" form $$ \sum_{j=1}^m {m\choose j} q^j (1-q)^{m-j} {n \choose k} \left(\frac j m\right)^k \left(1- \frac j m\right)^{n-k} $$ admit closed forms? My attempts to ...
34
votes
1answer
1k views

(Approximately) bijective proof of $\zeta(2)=\pi^2/6$ ?

Given $A,B\in {\Bbb Z}^2$, write $A \leftrightarrows B$ if the interior of the line segment AB misses ${\Bbb Z}^2$. For $r>0$, define $S_r:=\{ \{A, B\} | A,B\in {\Bbb Z}^2,||A||<r,||B||<r, ...
1
vote
1answer
193 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
5
votes
1answer
80 views

Sum identities with immanants

For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show $$ \sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} ...
1
vote
2answers
256 views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
26
votes
16answers
7k views

Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
3
votes
1answer
191 views

Dehn-Sommerville relations for $\Delta$-complexes

Let $M$ be a closed, triangulated manifold of dimension $m$ and $K(M)$ be its triangulation. Let $f_i$ denote the number of $i$-simplices of $K(M)$. As proved by Klee the face numbers satisfy the ...
59
votes
6answers
2k views

Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer. A polyomino is usually defined to ...
2
votes
0answers
33 views

Uniform generation of Symmetric Plane Partitons

In the conclusion of An Involution Principle-Free Proof of Stanley's Hook-Content Formula Krattenthaler notes that the techniques of the paper might be useful for finding bijective proofs of the ...
6
votes
0answers
249 views

What can I further assume about the speeds of runners of Lonely Runner Conjecture WLOG?

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$: Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ ...
7
votes
1answer
697 views

A Question about Palindromic Numbers and System of Arithmetic Progression

Based from Harminc and Sotak's result, www.fq.math.ca/Scanned/36-3/harminc.pdf We know that under certain condition, an arithmetic progression can contain an infinitely many palindromes. My question ...
8
votes
0answers
390 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
7
votes
0answers
144 views

What is known about the number of permissible simplicial complexes given the number of k-cells?

Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of ...
12
votes
1answer
801 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
1
vote
1answer
163 views

Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by $(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers, and $i=0,1,\dots,n+1$. Does this simplex admit a regular, ...
10
votes
1answer
303 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
7
votes
2answers
1k views

mnev's universality corollaries, quantitative versions?

Mnev's universality theorem claims that any semialgebraic set is the realization space of some oriented matroid. Moreover, the rank of the or matroid can be prescribed in advance. 1.-Are there ...
0
votes
1answer
150 views

Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane. $A(n):$ # of squares with vertices on the grid. It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...
1
vote
1answer
164 views

Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
22
votes
1answer
1k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...