# Tagged Questions

**3**

votes

**1**answer

37 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**6**

votes

**1**answer

393 views

### Surveys of the items of Erdős' “toolbox”

Could you point out some survey papers and monographs that highlight the kernel of tricks, techniques, and tools that Paul Erdős employed the most in his research work (in particular in graph theory, ...

**2**

votes

**1**answer

50 views

### Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$?

**5**

votes

**1**answer

81 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**5**

votes

**3**answers

342 views

### Identity for Power Series and Binomial Coefficients

This question concerns a combinatorial identity obeyed by power series coefficients. Throughout we let $[x^{M}]\{\phi(x)\}$ denote the coefficient of $x^{M}$ in a power series $\phi(x)$.
Let $k$ be ...

**5**

votes

**1**answer

365 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**0**answers

108 views

### Numbers summing to distinct integers

We want to find $r$ positive integers $\{a_i\}_{i=1}^r$ such that of atmost $(2s+1)^r$ values obtained from $$\sum_{i=1}s_ia_i$$ where $s_i\in\{-s,-s+1,\dots,0,\dots,s-1,s\}$ with $s\leq r$, we insist ...

**2**

votes

**1**answer

85 views

### How many expressions can be formed with $k$ commutative and associative functions?

This is a generalization of a question I posted to Math.SE here.
Suppose we have $k$ binary functions $f_1, f_2, \ldots, f_k$, all of which are commutative and associative, and $n$ indeterminates ...

**0**

votes

**0**answers

46 views

### Decomposing matrices to lower ranks

Given real matrix $M\in\{0,1\}^{n\times n}$ of rank $r$. How many $M_i\in\{0,1\}^{n\times n}$ of rank $s$ does one need to write $M'=\sum_{i=1}^ta_iM_i$ for some $a_i\in\Bbb R$ where maximum absolute ...

**0**

votes

**1**answer

252 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**3**

votes

**1**answer

266 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**13**

votes

**1**answer

239 views

### A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I
state it in a different but equivalent form. Let $a(n)$ be the sequence
at http://oeis.org/A131868, that is,
$$ a(n) ...

**16**

votes

**2**answers

593 views

### A possibly surprising appearance of Lucas numbers

Let $S$ be the set of polynomials defined as follows: $0$ is in $S$, and if $p$ is in $S$, then $p + 1$ is in $S$ and $x \cdot p$ is in $S$, so that $S$ "grows" in generations: $g(0)=\{0\}$, ...

**40**

votes

**2**answers

5k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**11**

votes

**3**answers

271 views

### Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...

**0**

votes

**3**answers

282 views

### On independent sets of graph

Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number.
Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality ...

**3**

votes

**1**answer

86 views

### A multinomial-type sum over compositions of an integer

I find myself needing to compute (or asymptotically estimate) the following sum over the $2^{S-1}$ compositions of $S$. I am hoping an expert in combinatorics (I am a computer scientist) will ...

**1**

vote

**0**answers

143 views

### Polynomial existence over finite field

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote ...

**1**

vote

**1**answer

98 views

### Combinatorics problem involving counting the number of certain substrings

I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere ...

**6**

votes

**1**answer

205 views

+100

### Induced subgraphs of small strongly regular graphs

Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed ...

**18**

votes

**1**answer

612 views

### What are the products $\prod_{A\subset{\mathbb F}_p\colon |A|=n} \sum_{a\in A} \zeta^a$ equal to?

This is a somewhat more explicit version of a question I have recently asked.
Let $p$ be an odd prime, and write $\zeta:=\exp(2\pi i/p)$ (any other primitive $p$th root of unity will do as well). For ...

**1**

vote

**1**answer

168 views

### Probabilistic statement on matrix ranks

Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.
Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.
Does
...

**2**

votes

**1**answer

73 views

### When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.
As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...

**4**

votes

**3**answers

88 views

### Linear intersection number and vertex covering number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then ...

**4**

votes

**0**answers

70 views

### Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries).
Can we partition this union into at most $n$ rectangles?
I think it's pretty ...

**0**

votes

**1**answer

127 views

### Term for number of crossings of smooth curves

Two smooth oriented finite curves $g_1, g_2$ on e.g. the 2-dimensional torus can intersect each other transversally in two ways: either the pair $(Tg_1(x),Tg_2(x))$ of tangent vectors in the ...

**1**

vote

**0**answers

24 views

### Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...

**55**

votes

**2**answers

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

**4**

votes

**1**answer

75 views

### Compiling self-referential forms

Fix $1\leq d\in\mathbb{N}$ and set $D:=\{0,1,\ldots,d-1\}$.
Consider the system of equations
\begin{equation}
x_i=c_i + \sum_{j\in D}\delta_{x_j,i}
\end{equation}
with $c_i\in D$ given and $x_i\in D$ ...

**0**

votes

**0**answers

28 views

### About adjacency matrices of $k-$shift lifts of graphs

I am finding the notation of cyclic lifts of graphs to be very confusing.
Lets say one is looking at a cyclic $k-$lift of a $\vert V \vert$ sized graph.
I would like to understand what is the ...

**18**

votes

**13**answers

3k views

### Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...

**16**

votes

**2**answers

921 views

### Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

For the notations I am using, I refer to the Appendix at the end of this post.
Here is what, for the sake of this post, I consider to be Reifegerste's theorem:
Theorem 1. Let $n\in\mathbb N$ and ...

**5**

votes

**1**answer

134 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$, where $x$ is real and has no additional ...

**3**

votes

**0**answers

33 views

### Signatures of latin squares: what about the extremal cases?

For a latin square (LS) of order $n$, we will define a cut (or maybe general transversal, I don't know whether there is an entrenched name for this) as a collection of $n$ cells such that no two share ...

**4**

votes

**1**answer

176 views

### Continuous-piecewise-linear versus piecewise-linear

Some authors use the term "continuous piecewise-linear" where other authors use the shorter term "piecewise-linear" (with continuity tacit).
I'd be interested in people's thoughts about this ...

**14**

votes

**0**answers

278 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**7**

votes

**1**answer

146 views

### A positivity problem involving the number of ways of expressing $n$ as a product of $k$ factors

Let $d_k(n)$ denote the number of ways of expressing $n$ as a product of $k$ factors, and let $$D_k(x)=\sum_{n\leq x}d_k(n)$$ be the summatory function. During a study of Mertens' function I was lead ...

**15**

votes

**2**answers

356 views

### Can all unit-distance graphs have their vertices at algebraic integers?

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...

**4**

votes

**2**answers

133 views

### Largest eigenvalue adjacency matrix-link deletion

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is ...

**4**

votes

**0**answers

129 views

### Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series;
1) multiplicative inversion for quadratic algebras,
2) compositional inversion for quadratic operads,
3) ...

**6**

votes

**3**answers

416 views

### Number of perfect matchings of the Dodecahedron

This question seems just to be an elementary enumeration problem, but I believe something deeper might be involved:
How many perfect matchings does a dodecahedron graph have?
Here the ...

**8**

votes

**2**answers

221 views

### Certain signed sum over $S_n$

The following question appeared in my research:
Let $G_1,G_2,G_3$ all be subgroups of $S_n$, and consider the sum
$$
\sum_{g_i \in G_i, g_1g_2g_3 = id} \epsilon(g_1)
$$
that is, we only consider ...

**2**

votes

**1**answer

78 views

### Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers

Given $d\in \mathbb{N}$, let $X_d:= \{(\ell_1, \ldots , \ell_d): 0 \le \ell_1 \le \ldots \le \ell_d \le d\}\subset \mathbb{Z}^d$, and endow $X_d$ with the (usual) partial order, namely, $x\le y$ if ...

**2**

votes

**0**answers

67 views

### Asymptotic expansion for the Bell numbers

The Bell numbers $B(n)$ (that is, the numbers that count the set partitions of a set, and have exponential generating function $\exp(e^x -1)$ ) admit the asymptotic expansion
$$\frac{\log B(n)}{n} = ...

**6**

votes

**3**answers

380 views

### Complexity of high-order differentiation

Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the ...

**2**

votes

**0**answers

86 views

### Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...

**2**

votes

**0**answers

252 views

### Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for ...

**9**

votes

**2**answers

323 views

### Can a graph be reconstructed from its cycle lengths?

All graphs discussed are finite and simple. The cycle sequence of a graph $G$, denoted $C(G)$, is the nondecreasing sequence of the lengths of all of the cycles in $G$, where cycles are distinguished ...

**3**

votes

**1**answer

269 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

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