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)

1
vote
0answers
5 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$. It's a known fact that it's NP-Complete. So I ...
0
votes
0answers
22 views

Distinct determinants of circulants

If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in? If $M$ is symmetric ...
2
votes
0answers
77 views

Distinct Numbers

Let $x_{ij}\in\{0,1\}$ for ${i=1}$ to ${m}$ and for ${j=1}$ to $n$. How many different values does $$\prod_{i=1}^m\sum_{j=1}^nx_{ij}$$ cover? Is there an $a_{ijk}\in\Bbb R$ (there is a $a_{ijk}\neq0$ ...
2
votes
1answer
116 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 ...
7
votes
2answers
192 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
111 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 ...
-1
votes
0answers
98 views

Secret Santa Assignments! [on hold]

I'm trying to figure out how many ways there are to assign Secret Santas to a set of N (distinguishable) people. For those who don't know what this is, it's a gift exchange where each person is ...
11
votes
0answers
216 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
84 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 ...
20
votes
0answers
193 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
51 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 ...
2
votes
0answers
135 views

Combinatorial puzzle involving half-integers [on hold]

Consider an arbitrary collection of vertical lines in $\mathbb R^2$ whose values are either integers of half-integers. $$x=-3,-1.5,0.5,3,4.5,5$$ Consider an arbitrary collection of horizontal lines in ...
5
votes
0answers
61 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
333 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
105 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 ...
8
votes
1answer
368 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 ...
20
votes
3answers
695 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.
9
votes
1answer
212 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
322 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
134 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 ...
-1
votes
0answers
93 views

Maximum connected components $0-1$ matrix

Let the notion of connected matrix be as in here Connected components $0-1$ matrices Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by ...
2
votes
2answers
176 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
84 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
252 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
245 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$?
0
votes
0answers
134 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
101 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
42 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
95 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
419 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
304 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
244 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
156 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 ...
11
votes
2answers
289 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
509 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
287 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
97 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$. ...
11
votes
1answer
591 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
156 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 ...
14
votes
1answer
984 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
158 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
200 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
221 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
162 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
52 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
124 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
103 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
49 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
148 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 ...