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,515
questions
5
votes
2
answers
451
views
f-vectors of Pure Complexes and Eulerian Complexes
Let $\Delta$ be a simplical complex.
Call $\Delta$ pure if all the maximal faces have the same dimension.
Call $\Delta$ Eulerian if it is pure and $\chi (lk (F))= \chi (S^{dim (lk(F))})$ for any $...
8
votes
2
answers
320
views
Perfect matchings between levels in products of posets
Let $P$ be a finite poset. Assign the following diagram to it - put the maximal element of $P$ on the first level, the maximal of the rest to the second level, etc. Assume that the diagram is ...
24
votes
1
answer
1k
views
Combinatorial spin structures
I would like to know how to define spin structures combinatorially, for an oriented smooth manifold equipped with a triangulation. In the case of a 2d manifold, spin structures correspond to ...
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
1
vote
0
answers
157
views
Indecomposability of image transformations (pure algebra). Open questions
W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
50
votes
8
answers
3k
views
Puzzle on deleting k bits from binary vectors of length 3k
Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$. You are allowed to delete exactly $n/3$ bits from each of the binary vectors, leaving vectors ...
2
votes
1
answer
681
views
Geometric van der waerden theorem
Van der Waerden theorem states that sufficiently long initial segment of the natural numbers when divided into $r$ parts contains an arithmetic progression of length $k$. The length of the initial ...
2
votes
1
answer
164
views
the space of noncrossing partitions of S^1
A non-crossing partition of the set $\mathbb{Z}_{mn}=\{ 1, 2,\dots,m n\}=\bigcup X_i$ is a disjoint union of sets such that
if $ a < b \in X_1$ and $ c < d \in X_2$ then we can't have $a < ...
6
votes
4
answers
2k
views
Sum over integer compositions
Sorry if the question is trivial - are there closed form expressions or good approximations for the sum of a symmetric function taken over all integer compositions (into given number of parts) of a ...
2
votes
1
answer
87
views
Commensurability of 2-colorings of finite 4-valent graphs
It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph $X''$...
12
votes
7
answers
758
views
Does the notion of graphs with vertex multiplicity exist?
I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...
1
vote
1
answer
181
views
Converse of Petersen's 2-Factorization Theorem
Definition: A $k$-factor of a graph is a spanning $k$-regular
subgraph.
Definition: A $k$-factorization of a graph is a partition of the edge
set into $k$-factors.
Petersen's celebrated ...
15
votes
3
answers
4k
views
An analysis proof of the Hall marriage theorem
The Hall marriage theorem has several relatively easy combinatorial proofs. Are there short analytical or topological reformulations and proofs of that theorem?
28
votes
6
answers
2k
views
Multiplying by irrational numbers in combinatorial problems
This is getting no attention on stackexchange.
Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.
It had escaped my attention until last week, ...
6
votes
2
answers
381
views
Overlapping sets
Consider the following problem:
Let $F \subseteq 2^{I}$ be a finite family of finite subsets of some index set $I.$
Let $F_x$ be defined as the number of elements of $F$ that contains $x.$
Assume ...
22
votes
2
answers
1k
views
Laws of Iterated Logarithm for Random Matrices and Random Permutation
The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, $...
7
votes
1
answer
435
views
Cospectrality and dimension of graphs
Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set $V=\left\{v_1,v_2,\...
2
votes
1
answer
282
views
Lattice automorphisms of finite order
Are there any known examples of lattice automorphisms of finite order in indefinite lattices being classified up to conjugacy?
9
votes
0
answers
244
views
Degree of a cone over the set of rank $r$ $n\times n$ matrices
Let $X_r\subset Mat_{n\times n}(C)$ denote the variety of rank at most $r$ matrices, set $k=n-r$ and assume $n\geq k^2-1$. Consider the cone over $X_r$ with vertex spanned by the first $k^2-1$ entries ...
11
votes
3
answers
1k
views
A problem on a specific integer partition
Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$...
5
votes
1
answer
205
views
a question on lattice invariants
Let $V$ be an $n$-dimensional vector space and $L$ be a lattice in $V$, i.e. a free $\mathbb{Z}$-module of full rank. Define the following two numbers. Let $\lambda$ be the minimal positive real ...
24
votes
2
answers
2k
views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
2
votes
0
answers
88
views
Group actions on polytopes in indefinite integer lattices
Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, I'...
10
votes
1
answer
401
views
What is the relationship between the bramble number and the strict bramble number of a graph?
A bramble in a graph $G$ is a set of connected subgraphs $H_1, \dots, H_m$ such that for every $i, j$, either $H_i$ intersects $H_j$ in a vertex, or there exists an edge of $G$ with one end in $V(H_i)$...
2
votes
1
answer
219
views
String transformer : Polynomial time approximation schemes?
A program P takes a string as an input and returns a string of same length as output.
Q Given two strings A and B how fast can a program tell weather string B cannot be obtained by a recursive ...
12
votes
3
answers
2k
views
How to efficiently sample uniformly from the set of $p$-partitions of an $n$-set?
Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?
13
votes
1
answer
691
views
Counting representations of $k[x,y]$ when $k$ is finite
$\newcommand{\GFq}{\mathbf F_q}$
Let $r_n(q)$ denote the number of isomorphism classes of $n$-dimensional modules of the $\GFq$-algebra $\GFq[x,y]$. Is it known whether there exists a polynomial $p_n(...
1
vote
3
answers
4k
views
Number of subsets with fixed cardinality k, and sum of elements a multiple of m
I need some help on a problem on combinatorics.
Let $n$ be a natural number greater than $1$ and $k,m$ be two fixed natural numbers not exceeding $n$ with $m\leq\frac{k(k+1)}{2}$.
Let $N=\{{1,2,...,...
12
votes
2
answers
2k
views
calculating Littlewood-Richardson coefficients
It is known that if $\alpha,\beta,\gamma$ are three partitions then the Littlewood-Richardson coefficient $c_{\alpha \beta}^{\gamma}$ is positive when the triple ($\alpha,\beta,\gamma$
) occurs as ...
2
votes
1
answer
145
views
Recognizing parallelogram tilings from their vertex set
Suppose I have a tiling of the plane with parallelograms where the sides of the parallelograms come from a specified finite set of vectors. If I only have access to the vertices of this tiling I may ...
4
votes
2
answers
620
views
What is the state of the art on triangle-free strongly regular graphs?
From what I've read I've gathered the following facts:
There are seven known such graphs.
Certain parameter sets are ruled out by the Krein conditions and the absolute bound.
Beyond that, little or ...
2
votes
0
answers
277
views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of $...
1
vote
1
answer
172
views
Linear combinations of basic cubes on a torus board
Consider an $n \times n \times n \times\dots\times n$ torus board of total size $n^k$ with $n > 4$ either even or odd.
Consider the basic cube of size $1 \times 1 \times \dots \times 1$ at a ...
2
votes
1
answer
331
views
Simple approximation to a sum involving Stirling numbers?
I have also posted this question at https://math.stackexchange.com/questions/486917/simple-approximation-to-a-sum-involving-stirling-numbers. I have an exact answer to a problem, which is the function:...
2
votes
1
answer
162
views
Estimates on the number of vertices of reflexive polytopes
Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...
3
votes
0
answers
204
views
Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges
Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of edge induced subgraphs of $H$ having $w$ vertices and an odd ...
2
votes
0
answers
251
views
A problem in Galois Geometry
Given a prime $p$, out of $N$ vectors of length $p^k$ over $\Bbb F_2$ of Hamming weight $w^{k}$ that are chosen, how many vectors can there be with pairwise Hamming distance at least $2w^{k}$ given ...
1
vote
1
answer
2k
views
Reachability in graphs using adjacent matrix
Assuming a graph $G$ with $N$ nodes distributed in a $\mathcal{L}\times\mathcal{L}$ area randomly. There is an edge between two nodes if and only if the Euler distance between them is equal or less ...
11
votes
0
answers
344
views
Right-angled polytopes
%This question is motivated by the little discussion here at the bottom.
The following thing are known about hyperbolic right-angled polytopes:
Compact hyperbolic right-angled polytopes do not exist ...
3
votes
0
answers
86
views
Perfect Matching for Edge-transitive Hypergraphs
I'm new to this subject, but I've noticed that a lot of work has been done on perfect matching in k-uniform hypergraphs. I'm curious to know if there are any results on perfect matching in the more ...
1
vote
1
answer
145
views
Submodular measures on the hypercube
By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the ...
2
votes
0
answers
168
views
When does the induced directed graph of a directed multigraph preserve information?
Let G be a directed multigraph, and let H be the induced directed graph whose vertices are the edges of G, and whose edges are given by pairs of consecutive edges in G; i.e., there is an edge from v ...
5
votes
1
answer
211
views
Reconstructing the number of Hamiltonian cycles
As is common terminology in graph reconstruction, given a graph $G$, we call a vertex deleted subgraph of $G$, a card, and call the multiset of all cards, the deck of $G$. The graph reconstruction ...
3
votes
1
answer
384
views
Counting discrete functions
For $1\leq k \leq n+1$, consider the set $S_k$ of functions $f:\{1,\ldots,n\} \rightarrow \{1,\ldots,n+1\}$, with the property that $|f^{-1}\{1,\ldots,k\}| < k$. Note that $|S_1|=n^n$, and $|S_{n+1}...
8
votes
2
answers
453
views
Embedding of a "quotient graph"
Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.
Define a "...
2
votes
1
answer
226
views
Generating k-partite graphs
Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...
14
votes
2
answers
874
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
3
votes
1
answer
192
views
Multipartite Ramsey theorem
Given $c<\infty$ colors, positive integers $k_1,\dots,k_n$ and positive integers $N_1,\dots,N_n$. Then there exist positive integers $M_1,\dots,M_n$ so that for disjoint finite sets $A_1,\dots,A_n$ ...
6
votes
2
answers
838
views
Minimal graphs of prescribed girth and chromatic number
The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...
20
votes
3
answers
792
views
Basis removal gives a basis
Let $V$ be a vector space. Let us say that a finite set $X$ of vectors in $V$ is harmonic if for $B \subseteq X$,
$$
B \text{ is a basis of } V \implies X \setminus B \text{ is a basis of }V.
$$
Let ...