# Tagged Questions

**11**

votes

**2**answers

294 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

184 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

158 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

109 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

93 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

619 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

460 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

271 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

194 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

161 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

145 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

119 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

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

**8**

votes

**0**answers

165 views

### Consequences of Zeeman's conjecture

Recall the Zeeman's conjecture: if $K$ is a contractible polyhedron of dimension 2, then $K\times I$ has a collapsible subdivision.
Zeeman showed that this implies the Poincaré conjecture in ...

**6**

votes

**2**answers

200 views

### Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...

**1**

vote

**1**answer

101 views

### Ratio of expected diameter and height of a conditioned Galton-Watson tree

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...

**2**

votes

**1**answer

93 views

### Estimate for the travelling salesman problem for balls inside a grid

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...
The question concerns the TSP problem (with ...

**3**

votes

**2**answers

149 views

### Finite lattices whose number of join-irreducibles does not exceed its height

In a finite distributive lattice $L$ one has $height(L) = |J(L)|$ i.e. the size of the largest chain equals the number of join-irreducible elements.
Briefly, this follows by arranging the subposet ...

**3**

votes

**0**answers

105 views

### Number of k-generated semigroups

Given some $k>1$, I am interested in the number of $k$-generated semigroups of order $n$ (either up to isomorphism or all associative binary operations on an n-element set). At first I thought ...

**5**

votes

**2**answers

248 views

### A bound on a set

Let $x_1,\cdots , x_n$ be a sequence of real number such that $x_i\geq 1$ for all $1\leq i\leq n$, $S=\{\alpha_1x_1+\cdots +\alpha_nx_n | \alpha_i\in\{0,+1,-1\}\}$ and $I=[a,b)$ be a Interval with ...

**21**

votes

**2**answers

459 views

### Convex hull of total orders

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...

**1**

vote

**1**answer

167 views

### Existence of certain probability distributions on the set of all partitions of a finite set

Conjecture: Let $N$ be a non-empty and finite set. There exists a probability distribution $p$ on the set of all partitions of $N$, $Z(N)$, such that $$\sum_{P\in Z(N):S\in P}p(P)= {1 \over n\cdot ...

**5**

votes

**0**answers

125 views

### Which Graeco-Latin hypercubes are impossible?

Define a Graeco-Latin hypercube of dimension $n$ and order $k$ as an $n$-dimensional grid, with $k$ cells in each direction (for a total of $k^n$ cells), where:
Each cell contains an ordered tuple ...

**5**

votes

**2**answers

221 views

### Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...

**7**

votes

**0**answers

474 views

### How many ways can a snake lie?

This is essentially a question about counting nonintersecting short paths in a
cubic lattice, but with a twist. (One constraint that I did not make clear below
is that when to turn is already ...

**5**

votes

**1**answer

182 views

### Estimate the rank of a vector

Consider {0,1}-vectors $v$ with $n$ elements. For each $i\in[n]$ we are given $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. We can therefore associate a probability to each of the ...

**1**

vote

**0**answers

52 views

### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
...

**2**

votes

**1**answer

218 views

### Examples of functors $\mathbf{Set} \to \mathbf{Set}$ which are not analytic

Let $\mathbb{B}$ denote the groupoid of finite sets and bijections.
A functor $F : \mathbf{Set} \to \mathbf{Set}$ is analytic if it is the left Kan extension of some functor $G : \mathbb{B} \to ...

**10**

votes

**1**answer

220 views

### On the Steiner System S(4,5,11)

Is there a nice way to partition the edges of the complete 5-uniform hypergraph
on 11 vertices into 7 copies of the Steiner system S(4,5,11)? If this is
obvious or elementary, I apologize in advance.
...

**3**

votes

**1**answer

312 views

### “the” random permutation

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability.
The random permutation is ...

**1**

vote

**0**answers

53 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**8**

votes

**1**answer

327 views

### Postnikov's approach to perfect matchings of graphs

Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...

**6**

votes

**0**answers

100 views

### Littlewood-Richardson coefficients for Jack symmetric functions

Let $\Lambda$ be the algebra of symmetric functions over $\mathbb{Q}(\alpha)$.
We define a scalar product $\langle \cdot,\cdot\rangle_\alpha$ on $\Lambda$ by setting $\langle ...

**6**

votes

**0**answers

135 views

### The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...

**5**

votes

**1**answer

408 views

### A generalized Burnside's lemma

Let $G$ be a finite group acting on a set $X$, and let $S\subseteq G$ be a union of conjugacy classes. Then I believe I can prove:
$$ \sum_{[x]\in X/G} \frac{|G_x \cap S|}{|G_x|} = \sum_{g\in S} ...

**11**

votes

**2**answers

262 views

### Set system with different differences

What is the maximal number of sets in a set system $\mathcal{A}$ of subsets of an $n$ element set such that for every $i \neq j $ and $A_i,A_j \in \mathcal{A}$ the difference $A_i \setminus A_j$ is ...

**4**

votes

**0**answers

155 views

### To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

This is a cross-post from MSE.
In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees.
The idea to construct such a ...

**3**

votes

**1**answer

186 views

### d-regular partitions and permutations

A $d$-regular partition is a partition of an $n$ element set with the additional restriction that $x,y$ with $|x-y|<d$ cannot be in the same block. So, if $d=2$, say, then the partition ...

**5**

votes

**1**answer

258 views

### Parking Functions and the Binomial Theorem

Cross-post from http://math.stackexchange.com/questions/808490/parking-functions-and-the-binomial-theorem
A parking function is a function $f: \{1, \ldots n\} \rightarrow \{1, \ldots n\}$ which has ...

**2**

votes

**0**answers

207 views

### Hook Content Formula: Has anyone seen this proof?

Below is the outline of a proof idea I have for the Hook Content Formula. I'm wondering whether anyone is aware of whether this technique has been used before, and if so, if they could give me a ...

**8**

votes

**2**answers

347 views

### Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...

**11**

votes

**1**answer

587 views

### Colourings of $\mathbb Q\times \mathbb Q$ in three colours

Using two-adic valuation Monsky coloured $\mathbb Q\times \mathbb Q$ in red, blue, and green, so that on each line points of at most two colours are present.
Question. I would like to know if there ...

**1**

vote

**1**answer

163 views

### How is this combinatorial structure called?

Here is a "colourful" description of what I would like to count. Suppose you have one of those tables you see in a casino. I think they are for roulette, with $m$ squares, each of them with a number ...

**5**

votes

**1**answer

219 views

### “strongly mixing” action on dimers?

In Local Statistics of Lattice Dimers we study a nice familiar object, domino tilings in the plane extending out to infinity.
His paper is going to discuss the frequency of various "motifs" in ...

**8**

votes

**1**answer

168 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**0**

votes

**0**answers

82 views

### Resources about integral maximization problem

I am looking at the following problem. Given an interval I, and a function f over that interval, find sub-intervals for which:
The sum of the length of the sub-intervals is < k;
The sub-intervals ...