# Questions tagged [co.combinatorics]

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

791 questions

**6**

votes

**0**answers

177 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 ...

**6**

votes

**1**answer

265 views

### Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?

Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...

**6**

votes

**1**answer

317 views

### Bichromatic pencils

A pencil is a collection of some lines through a point, called the center of the pencil.
If the points of the plane are colored, then call a pencil bichromatic if there is a color that is present on ...

**5**

votes

**0**answers

296 views

### 0-1 matrix combinatorial problem

Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the ...

**5**

votes

**1**answer

262 views

### hooks and contents: Part I

For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R Stanley proved the following ...

**4**

votes

**1**answer

1k views

### Estimate on sum of squares of multinomial coefficients

I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
$a_\...

**4**

votes

**2**answers

319 views

### Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A \...

**4**

votes

**1**answer

226 views

### Graphs with constant edge imbalance

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997)
I'm interested in the set of ...

**4**

votes

**1**answer

223 views

### Generalizing Kasteleyn's formula even more?

Inspired and intrigued by this question, I decided just for fun to throw in another integer into the factors and look what happens. So for $k\in\mathbb Z$, let us define $$K_r(n,k):=\prod_{\ell_1=1}^...

**2**

votes

**1**answer

182 views

### Proof and interpretation of the following percolation theory result for $n\times n$ square grid

While I was discussing this question with @JamesMartin, he mentioned a result here that:
In a $n\times n$ finite square grid, if $p\geq p_c+\epsilon$, such
that $\epsilon>0$ and $p_c$ is the ...

**2**

votes

**1**answer

194 views

### How many lines of exactly n points can be placed in a discrete, square grid of size m x m?

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of ...

**1**

vote

**1**answer

428 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...

**9**

votes

**1**answer

210 views

### How many positions of a tiling polygon can occur simultaneousy?

Let $T$ be a polygon which tiles the plane. For an instance of $T$ (mirrored or not), call the set of its translates a position of $T$.
My question:
How many different positions can occur in ...

**8**

votes

**2**answers

578 views

### Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$?
Are examples of such extremal ...

**8**

votes

**1**answer

262 views

### “Almost Hankelized” numerical Vandermonde

One of the more utilized determinant is that of Vandermonde's
$$\begin{vmatrix}
1&x_1&x_1^2&\dots&x_1^{n-1}\\
1&x_2&x_2^2&\dots&x_2^{n-1}\\
\ldots&\ldots&\...

**8**

votes

**2**answers

1k views

### Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...

**6**

votes

**1**answer

464 views

### Is every polynomial a factor of a trinomial?

We say that $T(X) \in \mathbb{Q}[X]$ is a trinomial if there exist $A,B,C \in \mathbb{Q}$ such that $T(X) = AX^n + BX^m + C$ for some $n \geq m \in \mathbb{N}$.
Is it true that for each irreducible ...

**6**

votes

**2**answers

222 views

### Permanent of Nakayama algebras

See https://en.wikipedia.org/wiki/Nakayama_algebra for the definition of Nakayama algebras and define the permanent of such an algebra to be the permanent of its Cartan matrix.
(all algebras are ...

**4**

votes

**1**answer

350 views

### Rigid Strongly Regular Graphs

I need a few examples of graphs that are strongly regular as well as rigid, i.e., have only the trivial automorphism. Any references to relevant literature would be appreciated. Thanks.

**4**

votes

**1**answer

254 views

### Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...

**4**

votes

**1**answer

168 views

### Strongly minimal covers

Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$.
A cover $M\subseteq E$ is said to be strongly ...

**3**

votes

**1**answer

461 views

### Automorphism groups of indefinite non-unimodular integer lattices

Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite non-unimodular integral lattice are calculated? The exact lattice isn't so important and they don'...

**3**

votes

**0**answers

150 views

### Matrices with only two different entries and maximal determinant

Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$.
I am interested in how big the determinant of such a matrix can be. For this, we define in a ...

**2**

votes

**2**answers

205 views

### Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**2**

votes

**0**answers

277 views

### Counting / characterizing the isolated points of a particular algebraic variety

I'm not a professional geometer / topologist, so please thanks for your patience :)
Setup
The following questions are the first in a series of steps I'm undertaking in an attempt to break down a ...

**2**

votes

**2**answers

151 views

### Existence of 3-distributed subsets

Denote $[n]=\{1,2,\dots,n\}$. Assume $n\geq2$.
Question. Is it true that given any $S_1,S_2,\dots,S_{2n}$ (repetition allowed) subsets of $[2n]$ with $a\in S_a$ and $\# S_a=n$ for all $1\leq a\leq ...

**2**

votes

**0**answers

840 views

### Necklaces and the generating function for inversions

The problem of Necklaces is well-known, i.e "The number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$" can be calculated:
http://mathworld.wolfram.com/Necklace.html
Let us ...

**1**

vote

**0**answers

137 views

### Non-trivial lower bound on the number of “Graph Diagonals”

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...

**1**

vote

**0**answers

410 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**1**

vote

**1**answer

168 views

### Covering a finite ring with arithmetic progressions

Let $n\geq 2$ be a positive integer and $k$ be a number between $1$ and $n$. Recently, I came across the following question about $\mathbb Z/n\mathbb Z$ and I wonder if it was studied before. I'd be ...

**1**

vote

**1**answer

208 views

### Combinatorial 0-1 vector problem

Let $M \in \{0, 1\}^{n\times n}$.
Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $\frac{n}{c}$ (assuming $c$ is a divisor of $n$). Let $\mathcal{M}_c$ be the set of ...

**1**

vote

**2**answers

181 views

### Is the Erdős–Rényi giant component result applicable here?

Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$.
Define a cluster of cells as a maximal connected component in the ...

**1**

vote

**1**answer

173 views

### Will this greedy algorithm always work?

Let p(n) be the number of unrestricted partitions of n. p(0) is taken to be 1.
Let set 1 and set 2 be two empty sets.
Here's an algorithm. Put p(n) into set 1. On each successive step, k=1,2,3,..., ...

**1**

vote

**1**answer

109 views

### Does there exist any analogous result for site percolation?

This is a sequel to the question: Proof and interpretation of the following percolation theory result for $n\times n$ square grid
In the paper: The Birth of the Infinite Cluster:Finite-Size Scaling ...

**0**

votes

**1**answer

104 views

### Critical coverings of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ...

**79**

votes

**17**answers

87k views

### Google question: In a country in which people only want boys [closed]

Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...

**62**

votes

**8**answers

11k views

### What is Lagrange Inversion good for?

I am planning an introductory combinatorics course (mixed grad-undergrad) and am trying to decide whether it is worth budgeting a day for Lagrange inversion. The reason I hesitate is that I know of ...

**53**

votes

**7**answers

5k views

### Euler-Maclaurin formula and Riemann-Roch

Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = ...

**61**

votes

**7**answers

6k views

### Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...

**69**

votes

**3**answers

5k views

### Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar with....

**42**

votes

**12**answers

6k views

### Combinatorial results without known combinatorial proofs

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell ...

**65**

votes

**4**answers

5k views

### What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...

**48**

votes

**37**answers

5k views

### Structures that turn out to exhibit a symmetry even though their definition doesn't

Sometimes (often?) a structure depending on several parameters turns out to be symmetric w.r.t. interchanging two of the parameters, even though the definition gives a priori no clue of that symmetry. ...

**43**

votes

**4**answers

7k views

### Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...

**35**

votes

**6**answers

3k views

### Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

I'm looking for a "conceptual" explanation to the question in the title. The standard proofs that I've seen go as follows: use the Schubert cell decomposition to get a basis for cohomology and show ...

**34**

votes

**14**answers

18k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...

**40**

votes

**15**answers

6k views

### What does the generating function $x/(1 - e^{-x})$ count?

Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series
$$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty \frac{(-x)^n}{(n+1)!}...

**54**

votes

**1**answer

2k views

### Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...

**47**

votes

**4**answers

8k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...

**41**

votes

**2**answers

2k views

### Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways.
...