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.

Filter by
Sorted by
Tagged with
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 $...
Alexandru Papiu's user avatar
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 ...
TOM's user avatar
  • 2,218
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 ...
Anton Kapustin's user avatar
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 ...
Benjamin Steinberg's user avatar
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 ...
Włodzimierz Holsztyński's user avatar
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 ...
user avatar
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 < ...
john mangual's user avatar
  • 22.6k
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 ...
László Kozma's user avatar
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''$...
Jean Raimbault's user avatar
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 ...
Aline Parreau's user avatar
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 ...
Felix Goldberg's user avatar
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?
user avatar
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 ...
Per Alexandersson's user avatar
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, $...
Gil Kalai's user avatar
  • 24.2k
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,\...
Shahrooz's user avatar
  • 4,746
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?
Bob's user avatar
  • 23
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 ...
JM Landsberg's user avatar
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}$...
Sebastien Palcoux's user avatar
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 ...
marker's user avatar
  • 125
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 ...
Colin McLarty's user avatar
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'...
MRD1729's user avatar
  • 373
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)$...
Paul Wollan's user avatar
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 ...
ARi's user avatar
  • 841
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}$?
AatG's user avatar
  • 922
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(...
Amritanshu Prasad's user avatar
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,...,...
Konstantinos Gaitanas's user avatar
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 ...
Rekha Biswal's user avatar
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 ...
Gjergji Zaimi's user avatar
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 ...
Felix Goldberg's user avatar
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 $...
alezok's user avatar
  • 418
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 ...
Turbo's user avatar
  • 13.7k
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:...
user1748601's user avatar
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$ ...
Li Yutong's user avatar
  • 3,362
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 ...
Giorgio Camerani's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
xzhh's user avatar
  • 35
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 ...
SashaKolpakov's user avatar
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 ...
Mairtin's user avatar
  • 31
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 ...
Erik Aas's user avatar
  • 406
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 ...
Ben's user avatar
  • 167
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 ...
Gjergji Zaimi's user avatar
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}...
funda's user avatar
  • 244
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 "...
Sergiy Kozerenko's user avatar
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 ...
caw's user avatar
  • 21
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$...
Stefan Kohl's user avatar
  • 19.5k
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$ ...
Fedor Petrov's user avatar
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 ...
Jernej's user avatar
  • 3,433
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 ...
Anton Klyachko's user avatar

1
157 158
159
160 161
211