# Tagged Questions

**10**

votes

**2**answers

581 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

**4**answers

868 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

**1**answer

238 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

**2**answers

364 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

**1**answer

193 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

**2**answers

191 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

**1**answer

88 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

**1**answer

278 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

**2**answers

257 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

**0**answers

169 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

**1**answer

107 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

**0**answers

50 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

**1**answer

103 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

**1**answer

452 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

**2**answers

414 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

**1**answer

249 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

**2**answers

159 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

**2**answers

304 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

**2**answers

540 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

**0**answers

316 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

**1**answer

103 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

**1**answer

616 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

**1**answer

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

**15**

votes

**1**answer

1k views

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

I have veriﬁed 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

**1**answer

166 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

**1**answer

210 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

**2**answers

226 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

**1**answer

163 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

**0**answers

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

**1**answer

126 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

**1**answer

108 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

**1**answer

52 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

**0**answers

159 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

**0**answers

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

**0**answers

82 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

**1**answer

317 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

**1**answer

165 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

**0**answers

65 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

**2**answers

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

**30**

votes

**9**answers

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

**1**

vote

**1**answer

65 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.:
...

**6**

votes

**3**answers

497 views

### A question about symmetric matrix

Let $A= (a_{ij})_{ij}, 1 \leq i, j \leq n$ be a symmetric $n \times n$ matrix. Suppose
(1) $a_{ij} \geq 0$ are real numbers;
(2) The sum of each row $\sum_{j=1}^{n} a_{ij} = 1$ for $1 \leq i \leq ...

**1**

vote

**0**answers

84 views

### A natural sum over multisets (expectation over multinomial)

I think this is a natural question but am not sure where to find resources.
Consider the possible multisets arising from choosing $n$ times an item from one of $k$ categories. We can represent one ...

**0**

votes

**0**answers

52 views

### Computation on Random Bipartite graphs

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...

**4**

votes

**2**answers

138 views

### Matroids relaxations of a given matroid

Let $\mathcal{M}$ be a rank-$d$ matroid on $[n]$. Say a matroid $\mathcal{N}$ is a relaxation of $\mathcal{M}$ if $\mathrm{rank}(\mathcal{N})=d$, $\mathrm{groundset}(\mathcal{N})=[n]$, and every ...

**1**

vote

**0**answers

59 views

### Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem
Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...

**6**

votes

**0**answers

174 views

### Minimal “basis” in $n$ dimensional unit cube

Let's
$$
B^n=\{\bar\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)|\alpha_i\in \{0,1\}\};~~~~n=1,2,\ldots
$$
and let's
$$
C\subseteq B^n,
$$
$$
S(C)=\{\bar\alpha\oplus\bar\beta\ | \bar\alpha,\bar\beta\in ...

**2**

votes

**2**answers

128 views

### Number of *distinct* dot products of an integer vector by elements of a hyper-rectangle

Imagine a vector $\boldsymbol{v}$ composed of integers, and the set $S$ of all integer vectors within a hyper-rectange, with one corner at the origin and other at $\boldsymbol{m}$. In other words: $S ...

**3**

votes

**1**answer

94 views

### Sum over integer compositions of $m$ with $n$ parts of a fixed monomial in the parts

Is there an explicit formula for the following quantity?
$$f_m(a_1,\ldots,a_n):=\sum_{\substack{k_1+\ldots+k_n=m \\ k_1,\ldots,k_n\in \mathbb{N}}} k_1^{a_1}\ldots k_n^{a_n}\ ,\hspace{1cm} ...

**0**

votes

**1**answer

87 views

### The weighting function for the infinite product of necklaces

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$ where $N(n,a)$ is the number of fixed necklaces of length $n$ composed of $a$ types of beads.
Let's rewrite the product in a way ...