Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

-4
votes
0answers
64 views

can you divide a $4\times 4$ square to six pieces? such every pieces have any two point $A,B$,such $d(A,B)\le\sqrt{5}?$ [on hold]

Question: Today,my math frend ask me this follow question: Let $R$ is square of $4 \times 4$, for any seven points on $R$, there exsits at least 2 of them,namely $\{A,B\}$,with ...
16
votes
1answer
428 views

Recognize this strange expression from linear algebra?

I've come across an odd-looking expression and oh how I wish I had a more elegant description of it. Maybe someone who enjoys symmetric bilinear forms in characteristic two will recognize it? Or ...
3
votes
2answers
83 views

Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?

For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
3
votes
1answer
78 views

Uniformly permutation and the length of a size biased cycle

The cycle containing $1$ of a uniform permutation has length which is uniformly distributed. I was wondering if the converse is true: Suppose $\sigma$ is a permutation on $\{1,\dots,n\}$ and let ...
2
votes
0answers
88 views

reference on aperiodicity and cluster [on hold]

From this image: I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)
0
votes
1answer
70 views

reference request for automata of this type [on hold]

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ ...
5
votes
1answer
115 views

Coloring summands of given n-partition with given weights of colors

Let $\lambda$ and $\sigma$ be partitions of $n$: $\lambda_1+\lambda_2+\cdots+\lambda_l=n$ and $\sigma_1+\sigma_2+\cdots+\sigma_s=n$ Let $M_{\lambda \sigma}$ be the number of ways to colour the parts ...
2
votes
0answers
68 views

second smallest eigenvalue Laplacian - submodular set function

Let $G$ be a connected unweighted undirected graph. In addition, let $\lambda_2(L(G))$ be the second smallest eigenvalue of the Laplacian matrix of graph $G$. Is $\lambda_2(L(G))$ a submodular set ...
0
votes
0answers
132 views

Applications of infinite permutations [closed]

I was looking at approximation in the forlmula of Products of necklaces: $n \to \infty$ we have $\prod_{p=1}^n N(p,a) \approx \frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$. (The number of ...
1
vote
2answers
153 views

Cubic Cayley (undirected) graphs

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...
3
votes
1answer
209 views

Dynamics in the integers - Floor function

Let $\alpha$ be an irrational with $0<\alpha<1$. Consider the function given by \begin{align*} f: &\mathbb{N}\longrightarrow \mathbb{N}\\ &x\longmapsto [ \alpha\cdot x]\end{align*} where ...
2
votes
0answers
46 views

Multi-dimensional permanent of structured tensor

I am facing the multidimensional permanent \begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation} of a 3-tensor $W_{j,k,l}$ of ...
1
vote
1answer
68 views

dual (p,q)-property

If the set system $(X,S)$ has the $(p,q)$-property does its dual system also have the property? (Possibly, for different $p$ and $q$.) Explicitly, I am asking about the equivalence of the following ...
4
votes
1answer
101 views

Maximum sets of lattice points such that only a few points collinear

Consider all the integer points $\in [0,n]\times[0,n]$, I want to find the maximum subset $S$ of which such that there are at most $n^\varepsilon(0<\varepsilon<1)$ points in $S$ collinear. So, ...
4
votes
2answers
125 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
5
votes
0answers
120 views

Operator connected with Hermite polynomials

For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients. $$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$ Monomials $x^k$ are mapped to $n ...
1
vote
2answers
52 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 ...
1
vote
0answers
44 views

Minimal density hitting set for k-length arithmetic progressions

This is problem which came up in the process of designing a game. Thus, I don't know any previous work relevant to the problem. Fix a small set $D$ of a natural numbers. For example, $D=\{1,2,3\}$. ...
1
vote
0answers
83 views

Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com: http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using ...
7
votes
2answers
304 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$?
2
votes
1answer
66 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 ...
8
votes
2answers
220 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
1answer
47 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 ...
6
votes
1answer
95 views

Aperiodic set of corner Wang Tile [closed]

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 ...
6
votes
1answer
246 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
1answer
177 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
2answers
113 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
0answers
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 ...
4
votes
0answers
85 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
2answers
241 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
2answers
194 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, ...
8
votes
1answer
161 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 ...
1
vote
2answers
223 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
1answer
159 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
2answers
153 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
2answers
233 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
1answer
75 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
1answer
133 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
1answer
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
1answer
639 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
3answers
710 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
0answers
93 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 ...
35
votes
1answer
857 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
1answer
240 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
3answers
197 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
1answer
457 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
3answers
766 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 ...
2
votes
0answers
47 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
0answers
47 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
3answers
247 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 ...