# Tagged Questions

**5**

votes

**0**answers

95 views

### Subplanes of Finite Projective Planes

If a finite projective plane $\pi_1$ of order $m$ contains, as a sub plane, a
finite projective plane $\pi_2$ of order $n$, then $m \geq n^2$ with equality holding only in the case of a Baer sub ...

**2**

votes

**1**answer

144 views

### Covering by subsets

There is set $A$ with cardinality $2^n$. For every $x \in A$ there is $A_x$ - subset of $A$ with cardinality $2^m$, $x \in A_x$. $M=\{A_x|x \in A \}$. Are there $B \subset A$ with cardinality $\ge ...

**25**

votes

**2**answers

791 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**0**

votes

**0**answers

123 views

### a question on sum of Gaussian binomial coefficients

I was trying to calculate something and at some point I get the following sum:
\begin{equation}
\sum_{t=0,t \text{ even}}^{s}{s+3n \brack s-t}\sum_{i = 0}^{t/2}q^{2i^2}{t/2+2n-i \brack t/2-i}{n ...

**7**

votes

**3**answers

694 views

### A conjecture about the entropy of matrix vector products

Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...

**7**

votes

**0**answers

75 views

### Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?
In ...

**7**

votes

**2**answers

286 views

### What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...

**0**

votes

**1**answer

156 views

### Maximize combinatorial sum for boolean function

I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...

**5**

votes

**1**answer

130 views

### Graphs where each edge belongs to the same number of 1-factors

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of ...

**2**

votes

**0**answers

43 views

### Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$.
The configuration space of Tverberg's theorem is the simplicial complex ...

**1**

vote

**0**answers

172 views

### Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1].
Is there a known tight upper bound in the number of polytopes in ...

**1**

vote

**2**answers

137 views

### Identity involving shifted Legendre coefficients

For small values of $n$ ($2\leqslant n\leqslant 5$), the coefficients $a_k = (-1)^k{n\choose k}{n+k\choose k}$ of the shifted Legendre polynomial $\tilde{P}_n(x)$ satisfy the identity ...

**1**

vote

**0**answers

109 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...

**4**

votes

**1**answer

230 views

### Non-vanishing of elements in cohomology of full Flag varieties

Consider the full flag variety $F_n$ consisting of full flags in $\mathbb C^n$. There is a collection of tautological bundles on $F_n$:
$0=U_0\subset U_1\subset ...\subset U_{n-1}\subset U_n=\mathbb ...

**11**

votes

**0**answers

354 views

### Erdos multiplication problem revisited

The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further ...

**3**

votes

**3**answers

304 views

### How to find an integer set, s.t. the sums of at most 3 elements are all distinct?

How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different.
Example with $|A|=3$: Out of the set $A ...

**1**

vote

**1**answer

129 views

### Vertex transitive and edge transitive and line graph

How can we find the proof of the following statement:
An undirected graph is edge transitive if and only if its line graph is vertex transitive.

**5**

votes

**3**answers

483 views

### Is the Manickam-Miklós-Singhi Conjecture solved?

This arXiv paper is claimed to contain a proof for the MMS conjecture. But it seems that this manuscript is not yet peer reviewed by other mathematicians. I personally tried to follow the paper, but ...

**7**

votes

**1**answer

206 views

### Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols,
and $p$ a pattern.
An example of a pattern is $p=XX$, where $X$ is any finite
string of symbols from $A^+$.
Avoiding $p$ is avoiding any subword repeated twice ...

**3**

votes

**2**answers

259 views

### Magic squares with specific properties

For what $n \geq 3$ does there exist an $n \times n$ matrix such that:
All entries are in $(0, 1)$.
Each row and column sums to $1$.
Aside from the rows and columns, no other subsets of the entries ...

**9**

votes

**3**answers

425 views

### Combinatorial interpretation of composition of power series?

This is a minor curiosity that came up in a joint project recently.
Consider the sequence $a_n=3\frac {(2n)!}{(n+2)!(n-1)!}$ (A000245 in OEIS).
It has multiple combinatorial descriptions.
One can ...

**3**

votes

**5**answers

256 views

### Given A set $U$ and a set $\mathcal O$ of subsets of $U$, how many subsets of $\mathcal O$ have union $U$?

Let $U$ be a finite set and $\mathcal O$ a set of subsets of $U$, how many subsets $\mathcal S$ of $\mathcal O$ satisfy the union of the elements of $\mathcal S$ is equal to $U$?
I think the problem ...

**14**

votes

**0**answers

482 views

### What's the big deal about $M_{13}$?

$M_{13}$ is the Mathieu groupoid defined by Conway in
Conway, J. H. $M_{13}$. Surveys in combinatorics, 1997 (London), 1–11,
London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, ...

**2**

votes

**0**answers

62 views

### Reference for MacMahon on Overpartitions

In the literature on overpartitions Percy A. MacMahon is usally cited as the genesis of the theory. Often the reference is to his 1916 textbook -- but, having recently checked this out of my school's ...

**5**

votes

**1**answer

212 views

### Continued fraction expansion of an algebraic number and its conjugates

Let $w$ be an element of a Galois extension $L:\mathbb{Q}$ such that $\text{Gal}(L/\mathbb{Q})=\langle g\rangle$ is cyclic of order $n$ (here $\mathbb{Q}$ is rationals). Suppose we know the continued ...

**1**

vote

**1**answer

191 views

### A problem in symbolic dynamics

I got a fun problem.
Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$
...

**24**

votes

**3**answers

599 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**5**

votes

**2**answers

269 views

### Balls and bins with color

Say I have $n$ balls each of $k$ different colors (i.e. $nk$ balls altogether), and I throw these balls independently into $N$ bins. Is there anything that can be said (in expectation, limits with ...

**2**

votes

**1**answer

142 views

### counting the number of ordered pairs in a permutohedron

Recall that a permutohedron is a graph on the set of permutations $S_n$ with an edge between $\sigma$ and $\tau$ if they differ by one adjacent transposition: $\tau = (i,i+1) \circ \sigma$ for some $i ...

**0**

votes

**2**answers

281 views

### Mixed integer programming formulation for Ising model

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...

**0**

votes

**0**answers

43 views

### Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving
transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs.
What is the complexity of graph isomorphism in $(P_4 ...

**0**

votes

**1**answer

97 views

### An upper bound on families of subsets with a small pairwise intersection

Given integers $ n,r,s $, we can define $M(n,r,s)$ to be the maximal size of a family $F$ of $r$-subsets of $\{1,...,n\}$ such that the pairwise intersection between any two subsets is at most $s$. Is ...

**5**

votes

**2**answers

173 views

### What is known about tiling a rectangle in an irreducible way by smaller rectangles?

Given two naturals $s<t$. Is there always a square (or at least a bigger rectangle) that can be tiled with $s\times t$ rectangles in an irreducible way (i.e. any grid line splitting it cuts at ...

**3**

votes

**1**answer

108 views

### Graph transformation related to graph isomorphism

Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...

**6**

votes

**1**answer

185 views

### Subset of $F_2^n$ that must contain some subspace of dimension $k$

This question has practical meanings in algebraic attack of stream ciphers in cryptography. It can be stated as follows:
Suppose $V$ is a $n$ dimensional vector space over the field $F_2$, where ...

**15**

votes

**0**answers

325 views

### Spencer's “six standard deviations” theorem - better constants?

This question is about Joel Spencer's famous "six standard deviations" theorem. The theorem says that when
$$
L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{in} x_n, \quad 1 \leq i \leq n,
$$
are $n$ ...

**2**

votes

**1**answer

174 views

### A parametrization of subsets

Suppose $I\subseteq\{1,\dots,n\}$, and let $\{1,\dots,n\}\setminus I=\{j_1,\dots,j_m\}$ be an enumeration of the complement of $I$ with $j_r<j_{r+1}$ for each $r\in\{1,\dots,m-1\}$. To $I$ I can ...

**2**

votes

**2**answers

223 views

### Finding the set of all $0-1$ vectors in an affine subspace

We are given a $0-1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0-1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) ...

**4**

votes

**1**answer

173 views

### Is the monoid of taking iterated images and inverse images freely generated by the image and inverse image operation?

Let $\mathcal{F}$ denote the class of all functions. Let $U,L:\mathcal{F}\rightarrow\mathcal{F}$ denote the mappings where if $f:X\rightarrow Y$, then $U(f):P(X)\rightarrow P(Y),L(f):P(Y)\rightarrow ...

**1**

vote

**0**answers

32 views

### Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances

To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...

**11**

votes

**2**answers

375 views

### how to find cubic polynomial that an unknown subset of a set of integers satisfies

I have a set, $S$, of positive integers and I have reason to believe that some infinite subset of them may be parametrized by a cubic polynomial with integer coefficients evaluated at integer ...

**4**

votes

**1**answer

62 views

### Is it true that every hypergraph with a large “semi-shattered” set has large VC dimension?

Given a hypergraph $H=(V,E)$ and a set $X\subseteq V$ of vertices, let $int(X)$ be the number of distinct intersections of edges with $X$, i.e.
$$int(X)=|\{S\subseteq X, \exists e\in E, e\cap ...

**4**

votes

**1**answer

122 views

### Transalate of a Richardson Variety

For $v \leq w$ are Weyl group elements, the intersection of a Schubert variety $X^w$ and the opposite Schubert variety $X_v$ is called a Richardson variety. It is denoted by $X_v^w$. It is well know ...

**0**

votes

**1**answer

203 views

### two correlated processes

I apologize if this question is not placed in the right place. But I am having a hard time to figure it out. It would be greatly appreciated if some one could help me out.
Assume that there are two ...

**4**

votes

**1**answer

150 views

### Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...

**7**

votes

**0**answers

130 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**9**

votes

**4**answers

812 views

### Ordinary Generating Function for Bell Numbers

In the OEIS entry for Bell numbers, there appears a generating function
$$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$
However, I could not locate any proof of ...

**0**

votes

**0**answers

97 views

### Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix ...

**5**

votes

**2**answers

616 views

### Combinatorics Problem: $\sum _{k=0}^{s-1} \binom{n}{k}=\sum _{k=1}^s 2^{k-1} \binom{n-k}{s-k}$

The question is whether the below is true.
$$\sum _{k=0}^{s-1} \binom{n}{k}=\sum _{k=1}^s 2^{k-1} \binom{n-k}{s-k}$$
Mathematica can simplify as follows, but it fails to Reduce[] or Solve[].
...

**3**

votes

**1**answer

155 views

### Switching representatives of right coset in a paper on fundamental domain of tree of GL(2)

I have a question concerning the following paper: "The fundamental domain of the tree of GL(2) over the function field of an elliptic curve" by Shuzo Takahashi. (1993, Duke Math. J., Vol. 72, No. 1). ...