**25**

votes

**3**answers

588 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

256 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

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

**1**

vote

**2**answers

272 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

41 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

89 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

168 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

104 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

182 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

320 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

173 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

222 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

172 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

372 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

61 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

121 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

137 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

107 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

790 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

611 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

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

**7**

votes

**2**answers

205 views

### An identity in the free associative algebra

Let $V$ be a finite dimensional vector space over a field of characteristic $0$, and let $T(V)$ be the tensor algebra (also called the free associative algebra) on $V$. This is actually a Hopf ...

**0**

votes

**0**answers

78 views

### Transversal theory in ergodic theory

I was taking a glance at the original paper by Donald Ornstein, Bernoulli Shifts with the Same Entropy are Isomorphic, and I came across The Marriage Problem and a paper with the same name by P. ...

**6**

votes

**2**answers

173 views

### Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...

**4**

votes

**1**answer

114 views

### Product of geodesic distances

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...

**8**

votes

**1**answer

310 views

### Combinatorics and symmetric functions

No answers from stackexchange, so I'll try this here:
(The actual questions in this posting are at the bottom.)
Occasionally someone asks on stackexchange how to show that every nonempty finite set ...

**3**

votes

**0**answers

71 views

### Unimodular triangulation and Ehrhart polynomials

Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function.
I am interested in what can be said about the Ehrhart polynomial when
$P$ has any of the properties
is integrally ...

**2**

votes

**2**answers

234 views

### convex polytope integer points

is there a simple proof for the following lemma:
An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.

**0**

votes

**0**answers

62 views

### Toric morphism fiber and kernel dimensions

Given a morphism between two smooth toric varieties $f: X \rightarrow Y$, is the dimension of the kernel of $\mathrm{d}f$ at any point $p \in X$ equal to the dimension of the fiber at $f(p) \in Y$?
...

**0**

votes

**4**answers

111 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**11**

votes

**2**answers

288 views

### When does a set of collinearity conditions imply collinearity of all of the points?

Suppose we have a set of $n$ points $\{X_1,X_2,\dots,X_n\}$ in the real plane and $\mathcal{A}$ a family of subsets of $\{1,\dots,n\}$.
By a "set of collinearity conditions for $\mathcal{A}$" we mean ...

**2**

votes

**1**answer

172 views

### Distribution of area of randomly placed circles

I've searched the web now for ages to try and find a paper on the asymptotic distribution of the area of the union of randomly placed discs on the plane. Ideally, I would be looking for the discs to ...

**4**

votes

**2**answers

193 views

### Intuition for Freiman dimension

Let $A\subset G$ and $B\subset H$ be subsets of abelian groups. We say that a map $f\colon A\to B$ is a Freiman homomorphism if for all $a_1,\dots, a_4\in A$ one has
...

**2**

votes

**1**answer

154 views

### Clique problem for regular graphs

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the ...

**0**

votes

**0**answers

73 views

### Rank function and closure operator for a set system

I would like to trace the concepts "rank function" and "closure operator" back to some structures as primitive as possible.
For a set system $(E,F)$ which is an independence system or a greedoid, I ...

**3**

votes

**0**answers

106 views

### Convex hull of a discrete set of points

If i was to give an $n×n$ grid with each grid point having probability $p$ of being selected, would it be difficult to calculate distributions of various measures regarding the convex hull of all ...

**1**

vote

**1**answer

90 views

### maximal chain in (strong) Bruhat order satisfying constraint

Consider the (strong) Bruhat order, $\leq_B$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma∈S_n$ such that $\pi\geq_B \sigma$. Suppose further that they satisfy the ...

**0**

votes

**0**answers

73 views

### latest classification of difference sets

I am looking for a reference including the last classification of difference sets and almost difference sets. Would you mind letting me know some of them? The recent ones are preferred.

**18**

votes

**3**answers

615 views

### Number of primitive $n$th roots with positive versus negative real parts

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ ...

**3**

votes

**1**answer

451 views

### “Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988:
A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...

**5**

votes

**1**answer

267 views

### Does this matroid have a name?

Sorry if this question is a dumb one.
I used a special family of matroids in my research. One of them, of rank 3, can be represented by the following matrix over $\mathbb F_5$ or over $\mathbb R$:
...

**1**

vote

**0**answers

72 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**3**

votes

**1**answer

192 views

### Geometric RSK correspondece and classical RSK correspondence

In the paper, geometric RSK correspondence is given by
$$
\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \mapsto \left( \begin{matrix} \frac{bc}{b+c} & ab \\ ac & ...

**1**

vote

**1**answer

154 views

### Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case.
I found on arxiv the following interesting articles:
1)Alexander Postnikov: Total ...

**3**

votes

**2**answers

144 views

### Asymptotics of the number of elements in the intersection of two growing sets

Let $[n]:=\{1,\dots,n\}$ and $0\leq p_n\leq n$. Fix any subset $A_n$ of $[n]$ with $p_n$ elements. The number of subsets $B$ of $[n]$ with $p_n$ elements that are disjoint from $A$ is ...

**1**

vote

**0**answers

118 views

### Reduce a Combinatorial problem

It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...

**0**

votes

**1**answer

154 views

### Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...