Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
10,563
questions
2
votes
0
answers
90
views
Stricter Notion of Crossing in a Partition
Let $k$ be an integer. Traditionally a partition $\pi=V_1\cup \dots \cup V_n$ of the set $[k]:=\{1,\dots, k\}$ is called crossing when there exist $a,c\in V_i$ and $b,d\in V_j\not= V_i$ such that $a&...
- 255
4
votes
1
answer
450
views
Is barycentric subdivision of a collapsible, regular CW complex collapsible (non-evasive)?
Let $X$ be a finite, regular CW complex, and let $X'$ be its barycentric subdivision (i.e. the order complex of the face poset of $X$). Assume $X$ is collapsible.
Is $X'$ collapsible?
Is $X'$ ...
- 2,074
8
votes
2
answers
1k
views
A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image
I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...
- 191
16
votes
4
answers
757
views
List of integers without any arithmetic progression of n terms
Let's consider a positive integer $n$ and the list of the $n^2$ integers from $1$ to $n^2$. What is the minimum number $f(n)$ of integers to be cancelled in this list so that it is impossible to form ...
- 161
3
votes
0
answers
224
views
On a problem of sphere-packing for Reed-Solomon codes
Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
- 307
9
votes
0
answers
149
views
Why have most maximal cliques of Paley graphs odd size?
I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an explanation ...
- 13.2k
6
votes
0
answers
210
views
Non-trivial bounds for polynomials at a fixed point
Let $f$ be a polynomial of degree $d$. Of course $|f(z)|\sim C|z|^d$ as $|z|\rightarrow\infty$ but also, since any polynomial is completely determined by its values at any $d+1$ points, we may ask how ...
- 2,470
11
votes
3
answers
1k
views
Square filling self avoiding walk
I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...
- 221
3
votes
1
answer
207
views
Expanding graphs from iterated zig-zag product
Let $\Gamma \, zz\, G$ denote the zig-zag product of graphs $\Gamma$ and $G$.
Reingold, Vadhan, and Wigderson proved that the second largest eigenvalue of the normalized adjacency matrix of the zig-...
7
votes
2
answers
184
views
Trees with a maximal convex hull: are the only optimal solutions Steiner trees?
For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take $\dfrac{...
- 13.2k
2
votes
1
answer
130
views
Existence of neighborhood inclusion for 4-chordal graphs
Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$.
A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more ...
2
votes
3
answers
607
views
a colouring / matching problem
While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given n-...
- 5,563
13
votes
0
answers
289
views
Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once
I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...
- 261
3
votes
2
answers
2k
views
ILP for minimum edge coloring problem
We know that for a graph $G=(V,E)$, minimum edge coloring is a coloring of
$E$, i.e., a partition of $E$ into disjoint sets $E_1, E_2, \dots, E_k$ such
that, for $1 \leq i \leq k$, no two edges in $...
- 45
0
votes
1
answer
71
views
Monotonicity of the gap of permutated sequence
Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of $...
- 753
1
vote
2
answers
210
views
Non-DS circulant graphs
Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices.
Which circulant graphs over prime number of vertices ...
- 301
3
votes
1
answer
210
views
Vanishing homology of simplicial complexes with few facets
Let $K$ be a simplicial complex with $n$ vertices and $n-t$ facets, where $t \geq 3$.
Is it true that the $(n-3-j)$th reduced homology (with coefficients in a field) of $K$ vanishes for $0 \leq j \...
- 43
5
votes
2
answers
367
views
Random Vornoi Diagrams (particular measures)
This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...
- 903
10
votes
2
answers
1k
views
Random Voronoi Diagrams
I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...
- 903
2
votes
1
answer
392
views
On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections
Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...
- 307
14
votes
2
answers
1k
views
Flag complexes that are shellable but not vertex decomposable
As the title suggests, I was wondering if anyone can point me to any examples in the literature to flag complexes that are shellable but not vertex decomposable.
It is well-known that if a ...
- 151
6
votes
1
answer
399
views
Counting cyclic binary sequences of length $n$ where ones appear in blocks of length at least $k$
How many binary cyclic sequences of length $n$ exist, where ones only appear in blocks of length at least $k$? We do not consider sequences that result from each other by a cyclic shift equivalent.
...
- 63
16
votes
1
answer
2k
views
A method for making a graph bipartite
Given any graph $G$, can we find a bipartite subgraph of $G$ with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$) by sequentially deleting the edge belonging to the most number of odd ...
- 378
1
vote
1
answer
158
views
Number of points in an intersecting linear hypergraph
I first asked the question below at math.stackexchange.com ( https://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...
- 45.5k
4
votes
0
answers
206
views
More 3-connected cubic graphs with all 2-factors of same cycle type?
The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
- 13.2k
5
votes
1
answer
606
views
Are there number-theoretic graphs that are far from being isomorphic
I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...
- 445
-3
votes
1
answer
784
views
How many sequences of length n satisfy these constraints? [closed]
I want to count the number of unique sequences of length n with the following constraints.
Each element of the sequence is an integer in $\lbrace 1,2,\dots,n\rbrace$.
Each two adjacent elements of ...
- 169
0
votes
1
answer
118
views
Comparing ideals in posets
Consider a partially ordered set $P$, and two upper sets $U_1$, $U_2$ in this poset.
What are some natural ways to measure how equal these two upper sets are?
This question arise naturally in the ...
- 15.6k
5
votes
0
answers
258
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
- 3,522
12
votes
2
answers
751
views
The sum of the carries when adding and multiplying two numbers in base p
Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding
(resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where $...
- 1,961
19
votes
1
answer
944
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 ...
- 13.1k
6
votes
2
answers
164
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 ...
- 13.2k
3
votes
1
answer
215
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 $u ...
- 491
0
votes
1
answer
98
views
reference request for automata of this type [closed]
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)$ ...
- 1,825
6
votes
1
answer
213
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 ...
- 443
4
votes
0
answers
313
views
Is the second smallest eigenvalue of the Laplacian matrix a set function over edges?
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 ...
- 41
1
vote
2
answers
258
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,522
5
votes
1
answer
468
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 ...
- 167
3
votes
0
answers
229
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 ...
- 93
1
vote
1
answer
139
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 ...
- 154
5
votes
1
answer
328
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, ...
- 509
4
votes
2
answers
717
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 ...
- 175
5
votes
0
answers
216
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 ...
- 617
4
votes
2
answers
348
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 $\...
2
votes
0
answers
66
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\}$. ...
- 241
3
votes
0
answers
875
views
Kempe chain color swaps in a partially colored map
Crossposted from math.stackexchange.com:
https://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map
Question: In this partially Tait's colored map, using only ...
- 351
10
votes
2
answers
484
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$?
- 11.2k
2
votes
1
answer
127
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
2
answers
540
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$ ...
- 8,643
1
vote
1
answer
238
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 ...
- 867