**3**

votes

**0**answers

99 views

### Is there a hyperplane avoiding two independent sets?

Let $V$ be a vector space over a field with $5$ elements, $A,B \subseteq V$ independent subsets. Must there be a subspace of $V$ of codimension 1 disjoint from $A \cup B$?

**1**

vote

**1**answer

36 views

### When does a hypergraph represent maximal independent sets?

Let $G = (V,E)$ be a simple graph. Then, we can view the set of maximal independent sets (or the set of maximal cliques) as a hypergraph $H = (V, E')$. This is quite a useful device when connecting ...

**6**

votes

**1**answer

125 views

### How do I find coefficients of a product expansion

Any power series $f(t) = 1 + t \mathbb{Z}[[t]]$ can be uniquely expanded in the following two ways:
$$1 + \sum_{i=1}^\infty f_i t^i =
\prod_{i=1}^\infty (1-t^i)^{-n_i}$$
Here, the $f_i$ and $n_i$ ...

**2**

votes

**1**answer

31 views

### A possible minimal aperiodic set of corner Wang Tile

From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...

**5**

votes

**1**answer

88 views

### Aperiodic set of corner Wang Tile [on hold]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...

**3**

votes

**1**answer

187 views

### A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless
of the starting $n$.
For example, let $n=69$, and consider this partition:
$$
(8,8,7,7,5,5,5,5,5,4,3,3,2,2)
$$
In ...

**7**

votes

**1**answer

163 views

### A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have ...

**0**

votes

**2**answers

109 views

### Terminology for beads/necklace/bracelet problem [closed]

I'm new to mathoverflow but hopefully anyone here can point me in the right direction.
The problem is as follows, imagine you have 4 beads, lets give them numbers 1,2,3,4. Now I want the unique ...

**0**

votes

**0**answers

79 views

### How many possibilities would you have in an android lock pattern, always using all 9 moves? [migrated]

We are doing some research and wanted to know how many possibilities you would have if you would use all 9 dots/options in an (android) swipe lock pattern.
What would the formula be to get to this ...

**-5**

votes

**0**answers

66 views

### Squares in a square grid [closed]

How many $n$ square $a \times a$ permutation are in a grid $b \times b$? (They must never overap themselves)
The question seems simple, but it isn't at all.

**3**

votes

**0**answers

78 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**9**

votes

**2**answers

233 views

### Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let
$$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$
...

**1**

vote

**2**answers

183 views

### Set of distinct real numbers such that all combination of sums are distinct

Let $\Lambda :=\{\lambda_1, \dots, \lambda_n\}$ be a set of $n$ distinct real numbers.
For a given $p \in \mathbb N$, consider further the set
$$I_p := \{ \{i_1, i_2, \dots, i_p\} : i_j \in \{1, ...

**-1**

votes

**0**answers

52 views

### How many turns will it take to draw all cards from a deck with shuffling and replacement? [closed]

Or alternatively, given n marbles, how many random draws with replacement will it take to pick them all out at least once?

**8**

votes

**1**answer

153 views

### Looking for history on a theorem of clique intersections

I have a short paper I'm working on where I prove:
Theorem: Every graph on (2t-1) vertices with no (t+1)-clique has a vertex that is contained in every t-clique.
By "t-clique", I mean a complete ...

**-4**

votes

**0**answers

42 views

### graph and tree problems helps [closed]

Let G = (V,E) be a graph and let H1 = (V1,E1) and H2 = (V2,E2) be two connected subgraphs of G that have at least one node in common. Prove that the graph H = H1∪H2 = (V1∪V2,E1∪E2) is connected.
...

**1**

vote

**2**answers

222 views

### Embed one Coxeter System into another

What is a good reference that explains all the braid relations and diagrams for Coxeter systems concisely?
In particular, how do I embed $H_3$ inside $D_6$, or $H_4$ inside $E_8$? Any hints?

**6**

votes

**1**answer

154 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least ...

**4**

votes

**2**answers

149 views

### Simplicial complices on unlabelled vertices

My question is about (abstract) simplicial complices.
In particular, how many are they if I consider $n$ unlabelled vertices?
For example, if $n=4$, the two complices
$$
\{\varnothing, \{1\}, \{2\}, ...

**5**

votes

**2**answers

222 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**0**

votes

**1**answer

70 views

### Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to:
I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...

**1**

vote

**1**answer

128 views

### Is there a “Bipartite” Szemeredi-Trotter theorem?

One version of the Szemeredi-Trotter theorem states the following:
Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k ...

**0**

votes

**1**answer

40 views

### average number of cycles and closed walks length k in incomplete directed graph

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.
Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple ...

**11**

votes

**1**answer

624 views

### Szemeredi's theorem in the Gaussian integers

Suppose that $S\subseteq\mathbb{Z}[i]$ has the following properties:
For convenience, let $A_n = \{z : z\in\mathbb{Z}[i], \text{Nm}(z)\le n\}$
$$\limsup_{n\rightarrow\infty} \frac{|S\cap ...

**9**

votes

**3**answers

701 views

### What exact number of domino tilings cannot be realizable?

Inspired by some other questions, (this and this),
I wonder what numbers $n$ there are that satisfy
$$p(n)=\text{there is no region that admits exactly } n \text{ domino tilings}.$$
If this is true, ...

**1**

vote

**0**answers

92 views

### Representation of Permutation group: What is the isormorphism between the equivalent descriptions, (1)using schur functions and (2)abstract tensors

I assume that the two ways of describing the representation of the permutation group using abstract tensors (perhaps more naive but widely used in physics) and schur functions are equivalent. If ...

**34**

votes

**1**answer

845 views

### Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...

**6**

votes

**1**answer

231 views

### A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...

**4**

votes

**3**answers

193 views

### Can anyone suggest a text on polyhedral theory?

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes

**13**

votes

**1**answer

445 views

### When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...

**6**

votes

**3**answers

763 views

### A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...

**1**

vote

**0**answers

45 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

46 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**2**

votes

**3**answers

218 views

### Is the reduced plethysm (restricted to 2-columns in Young tableaux) of this Schur funtion known $\mathbb S_{3^1}(\mathbb S_{1^p})$?

I am working on a physical problem, where I need to compute the "reduced plethysm" that is all the irreducibles characterised by the Young tableaux of 2 columns or less. The plethysm problem I want to ...

**1**

vote

**1**answer

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

**0**

votes

**0**answers

45 views

### Calculating the longest Bracelet(s) Common to a Set of Bracelets

I would like to know, if the following problems has been studied before:
let $\{B_1, ..., B_n\}$ be a set of Bracelets with the same set $\{\beta_1, ..., \beta_k\}$ of beads,
what is the ...

**5**

votes

**2**answers

175 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**6**

votes

**1**answer

266 views

### About an identity which gives immediate proof of the permanent lemma

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...

**4**

votes

**0**answers

124 views

### Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in ...

**0**

votes

**1**answer

287 views

### Basketball shots and stopping rule

Moved over from StackExchange.
You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...

**0**

votes

**0**answers

67 views

### asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...

**5**

votes

**1**answer

171 views

### Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...

**5**

votes

**0**answers

87 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

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

**11**

votes

**0**answers

368 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

115 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

580 views

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

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...

**6**

votes

**0**answers

66 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

246 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

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