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)

3
votes
1answer
149 views

Stable Household Formation

I want to model the problem of household formation by a finite number of individuals, each of whom has preferences over sets of housemates. A collection of households is unstable if there is a set ...
9
votes
3answers
401 views

Cubic-exponential enumerative combinatorics

There are many quantities in enumerative combinatorics that grow roughly exponentially, like the Fibonacci numbers, the Catalan numbers, and the factorials; indeed, most of the functions that arise in ...
2
votes
1answer
201 views

Trying to prove a congruence for Stirling numbers of the second kind

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement. Proposition: When $n$ and $m$ are ...
11
votes
0answers
285 views

Evaluating products of cyclotomic polynomials at roots of unity

Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...
5
votes
1answer
101 views

Measuring how closely a missing projective plane can be approached by an equivalent structure

It is well known that for a number of structures, their existence is equivalent to the existence of a projective plane for a given order. Some of them depend on more than one parameters, which means ...
31
votes
2answers
614 views

How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...
2
votes
0answers
56 views

Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...
5
votes
0answers
81 views

Families of Sets with Two Intersection Numbers

Let $k$ and $n$ be natural numbers. Let $I$ be a set of natural numbers. Let $\mathcal{F}$ be a family of $k$-element subsets of $\{ 1, \ldots, n\}$ such that $A, B \in \mathcal{F}$, $A \neq B$, ...
2
votes
5answers
348 views

Mean of a vector

Be a set of numbers $v=(a_1, a_2, \ldots, a_n)$ I want to form the following average vector $\mu = (\frac{\sum a_i}{n}, \frac{\sum a_i}{n}, \ldots, \frac{\sum a_i}{n})$. If I do it iteratively step ...
0
votes
2answers
140 views

Diagonal asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
10
votes
2answers
691 views

What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify. (1) The Hoory-Linial-Wigderson review on ...
22
votes
4answers
931 views

Number of elements of “$\mathrm{SL}_n(\mathbb{F}_p^\times)$” mod $p$

How many elements of $\mathrm{SL}_n(\mathbb{F}_p)$ have all nonzero entries? Just the answer mod $p$ would be fine as well. This seems like it should be easy/in the literature but I couldn't find it.
10
votes
1answer
248 views

Are there non-trivial graphs that uniquely embed to hypercubes?

The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place. The weight of a sequence is the number of $1$'s ...
6
votes
2answers
391 views

Generalization of Sylvester-Gallai theorem

The Sylvester-Gallai theorem states that it is not possible to arrange a finite number of points so that a line through every two of them passes through a third unless they are all on a single ...
8
votes
1answer
199 views

For any two noncrossing partitions $p, q$ of $n$, is the graph of geodesics from $p$ to $q$ in $NC(n)$ connected?

Let $NC(n)$ denote the lattice of noncrossing partitions of $n$, and let $G$ denote the Hasse diagram of $NC(n)$ with respect to covering relations, viewed as an undirected graph. I'm interested in ...
2
votes
2answers
200 views

Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that: $G$ has no complete subtrees (the graph below any ...
1
vote
1answer
90 views

Combinations Question about the construction of some special sets [closed]

Let n and k be two given numbers. The goal is to choose n subsets from {1,2,…,n} such that the union of any k of these subsets is the set {1,2,…,n} and the union of any m < k of ...
3
votes
1answer
310 views

Open problems in compressed sensing

What are the main open problems in compressed sensing? I am interested in theoretical as well as in numerical point of view.
1
vote
2answers
280 views

How many k-subsets of the integers {1,…,n} sum to N?

Given the set of integers $S = \{1,..n\}$, how many subsets of $S$ with $k$ elements sum to $N\in \mathbb Z$?
1
vote
0answers
174 views

On matrix rank inequality

Let $A$ be a $\{0,1\}$ square matrix. Let $J$ be all $1$ matrix. Let $\bar{A}=J-A$. Is it possible for $rk_+(A)\geq c\cdot rk_+(\bar{A})^d-1$ and $rk_+(\bar{A})\geq c\cdot rk_+({A})^d-1$ for some ...
2
votes
1answer
120 views

Hopf structures on “pictorial” descriptions of permutations

There is a well-known Hopf structure on permutations, due to Malvenuto and Reutenauer. Here, the F basis elements are permutations in one-line notation, the product of two permutations is their ...
1
vote
0answers
56 views

Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem

There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...
3
votes
1answer
109 views

Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...
11
votes
1answer
482 views

Connected components $0-1$ matrices

Let $M$ be a $0-1$ matrix. Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where ...
7
votes
2answers
466 views

Numbers with all N-digit prefixes divisible by N

In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. ...
4
votes
1answer
256 views

Endomorphisms and almost all graphs

Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs ...
1
vote
2answers
167 views

Generalization of Bracketing (or one of its many equivalences)

I asked the following question on MathStackExchange, but I have not received any answers after almost 3 days. Although it may not be a research level question, I thought I could ask it here. *"Is ...
12
votes
4answers
482 views

What is the number of equitriangulations of the n-cube?

I wonder if this question has been considered before and if anything is known. My search attempts have failed so far. Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with ...
11
votes
2answers
566 views

Conjecture on maximum of symmetric combinatoric function

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). (The question was first asked at math.SE, ...
3
votes
0answers
327 views

On a positivity property of Hall-Littlewood polynomials

Here's the new, more thought through version. Consider a sequence of nonnegative integers $\lambda=(\lambda_1,\ldots,\lambda_n)$ with $\lambda_i\ge \lambda_{i+1}+2$ (the weight $\lambda-2\rho$ is ...
4
votes
1answer
108 views

Determining the number of hamiltonian paths of $K_n-C_n$

I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...
12
votes
1answer
647 views

Lots of combinatorial interpretations of Catalan numbers

During a lecture I gave on Catalan numbers, I pointed out that that it is possible to give a continuum number of combinatorial interpretations of these numbers. See the solution to (f$^5$) on page 54 ...
2
votes
1answer
177 views

Edge density of triangle-free graphs

Let $G$ be a finite, simple, loopless graph with $|V(G)|=n$. We define its edge density as $$ed(G) := \frac{|E(G)|}{n \choose 2}.$$ Moreover we set $$d_n := \text{max}\big\{ed(G): G \text{ is a ...
16
votes
1answer
1k views

How to prove that the following double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
7
votes
1answer
171 views

A polytope with a bound on the sum of any $k$ variables

Let $2\le k\le n-1$ and define the polytope $$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n : -1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$ There ...
10
votes
1answer
220 views

Partitions of $\mathbb{R}^+$ into subset closed by sum and product

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a "non trivial" solution of the Cauchy functional equation, i.e. $f$ is not of the form $f(x)=cx$ for any $c\in\mathbb{R}$ and satisfies the relation ...
4
votes
2answers
231 views

Marked chain polytope, has this been studied?

Fix $n$ and consider the polytope given by the inequalities $$x_i\leq x_j, \text{ and } 0 \leq x_i \leq a_i \text{ for all } 1\leq i<j \leq n,$$ where $a_i \leq a_i\leq \dots \leq a_n$ are fixed ...
7
votes
1answer
170 views

Universal graph homomorphisms

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such ...
0
votes
0answers
55 views

Colorful version of Fisher's inequality for block designs

Is there such a thing? I am thinking of Karatheodory and Tverberg analogues here.
3
votes
1answer
133 views

How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
2
votes
1answer
128 views

a question about points and line segments in the plane

Let $P=\{P_1,P_2\cdots P_n\}$ be a set of $n\geq 4$ points in the plane and $P_iP_j$ be the line segment connecting $P_i$ and $P_j$ that satisfy: $(1)$Any three points of $P$ are not on a line; ...
1
vote
1answer
55 views

Number of different normalized inner products

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components. Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$. How many different values can $$I'=\frac{\langle u,v ...
2
votes
0answers
164 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 ...
0
votes
0answers
60 views

Upper bound on number of cells created by varieties of co-dimension 1

Say I have polynomials $p_1,p_2,\dots,p_m$ in $\mathbb{R}^n$ (ie. over $n$ variables), each of degree $d$. Is there an upper bound on the number of "regions" created by the surfaces $p_i = 0$? Let's ...
0
votes
0answers
96 views

Explicit basis/weight vectors for irreducibles inside the plethysm $Sym^m(\bigwedge^p \mathbf(V))$

This is a follow up to this question about finding the multiplicities of irreducible representations restricted to Young diagrams of 2-columns or less, inside the plethysm $Sym^m(\bigwedge^p ...
10
votes
1answer
380 views

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality? Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...
11
votes
1answer
169 views

Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...
0
votes
0answers
68 views

Counting path generating sentences in a specific formal language

Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language? For example, we know that if the grammar is context-free ...
1
vote
2answers
165 views

Proving a random bipartite graph contains a perfect matching

I have the following problem consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...
31
votes
9answers
3k views

Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...