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
votes
0answers
25 views

Secret Santa Assignments!

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 ...
4
votes
0answers
85 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 $p(z)$ is rational (and hence a ...
5
votes
1answer
57 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 ...
18
votes
0answers
153 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
45 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
53 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
322 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
83 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
345 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 ...
19
votes
3answers
676 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
0answers
150 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
319 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 ...
7
votes
0answers
104 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
92 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
249 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
243 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
132 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
100 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
41 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
416 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
242 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
288 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
506 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
284 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
96 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
588 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
155 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 ...
13
votes
1answer
979 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
161 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
123 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
48 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 ...
0
votes
0answers
73 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 ...
9
votes
1answer
260 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
158 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
63 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
136 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 ...
29
votes
8answers
2k 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 ...
1
vote
1answer
63 views

The number of orderings of elements with order-of-appearance constraints

Consider $(q_1,q_2,...) \in Q$ non-intersecting sets of distinct elements $(e_{(i,1)},e_{(i,2)},...)\in q_i$. How many ways can one write down an ordering of all of the $\sum_j |q_j|$ elements s.t.: ...