All Questions
Tagged with co.combinatorics extremal-combinatorics
197 questions
2
votes
1
answer
91
views
Number of disjoint set triplets in a union-closed family
Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the ...
- 990
7
votes
4
answers
497
views
Distinguishing finite families of sets by algebras of bounded size
Say that an algebra of sets $K$ distinguishes set $B$ from set $C$ provided that for some $A\in K$, we have exactly one of $A\cap B$ and $A\cap C$ non-empty. Given families $F$ and $G$ of sets, say ...
- 2,555
0
votes
0
answers
56
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
0
votes
0
answers
58
views
Searching another example related to the union-closed sets conjecture
Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.
Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (...
- 990
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 349
6
votes
3
answers
550
views
Conjecture about commutative semigroups
Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, ...
- 990
4
votes
0
answers
114
views
A slight strengthening of the union-closed sets conjecture
Consider a union-closed family $\mathcal{F}=\{A_1,…,A_n\}$ of $n \gt 1$ finite sets.
I was not able to find a counterexample to the following conjecture:
there exist two sets $A,B \in \mathcal{F}$ ...
- 990
4
votes
1
answer
371
views
Looking for a counterexample to a strengthening of the union-closed sets conjecture
[Now crossposted at math.stackexchange]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ ...
- 990
0
votes
1
answer
118
views
Configurations of signs in a matrix under certain conditions
I have a combinatorial question which is out of my research area.
Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible ...
- 619
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 349
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 349
1
vote
2
answers
386
views
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 990
5
votes
0
answers
137
views
Looking for a certain finite lattice
I don't think it actually exists, and it should be difficult proving that it doesn't (some background here), but is it possible to build a finite lattice $L$ where the only meet-irreducible elements ...
- 990
2
votes
1
answer
142
views
Bounds for ground set of Steiner system (inverse EKR style problem)
Imagine we have $r$ subsets of a ground set $S$, each of size $k$, such that each set of size $l$ is contained in at most one of the $r$ sets. What can we say about the minimum value of $|S|$? I am ...
- 83
0
votes
0
answers
67
views
Do there exist at least two disjoint sets in a certain union-closed family of sets?
This is a strengthened dual version of this answered question. Here we are adding to that question requirement $3$ below.
Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can ...
- 990
0
votes
0
answers
67
views
Proving we can minimize the number of crossings by having a planar embedding of $K_{2,2}$ encircle another out of any 2 such embeddings
Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $...
- 1
0
votes
1
answer
53
views
Square submatrix of a binary matrix with all columns having the same sum
Let $M$ be a $m \times n$ matrix with binary entries (i.e. a matrix all whose entries belong to the set $\{0,1\}$), with $m\geq n$. Suppose each row of $M$ contains exactly $k$ ones. Given $n$ ...
0
votes
1
answer
234
views
Minimum number of elements needed to represent a lattice with a union-closed family of sets
I know that it is possible to represent every finite lattice $L$ with a union-closed family $\mathcal{F}$ containing the empty set: for every $x\in L$, let $S_x=\{y\in L\, :\, y\not\geq x\}$ and $\...
- 990
2
votes
1
answer
232
views
Is the small Davenport constant for $S_n$, $d(S_n)=n(n-1)/2$?
The Davenport constant $D(G)$ of a finite group $G$ is the minimal $d$ such that any sequence/multiset of length $d$ is one-product, i.e., identity can be obtained as a product (in some order) of some ...
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 990
1
vote
0
answers
63
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 349
3
votes
1
answer
296
views
Do there exist at least two sets whose union gives the universe in a certain intersection-closed family of sets?
[Crossposted at math.stackexchange.]
Originally I posted a slightly more complicated version of this question. I decided to edit and put it in this simplified form, because I think that if we can ...
- 990
0
votes
0
answers
164
views
One-product free sequences for $A_n$
I am working on computing the Davenport constant $D(G)$ for $S_n$ and $A_n$, i.e., the minimal number $d$ such that every sequence (multiset) of $d$ elements contains some subsequence giving identity ...
3
votes
1
answer
259
views
Davenport constant $D(S_5)=10$ or $11$?
I am working on computing the Davenport constant $D(G)$
of symmetric groups, which is the minimal number $d$
such that every sequence of $d$
elements, possibly with repetitions, is one-product, i.e. ...
3
votes
0
answers
155
views
Correspondence between even and odd permutations in $S_5$
I am working on the Davenport constant for symmetric groups, $D(G)$
, which is the minimal number $d$
such that every sequence of $d$
elements in the group G
is one-product sequence, i.e, we can ...
0
votes
0
answers
43
views
Locally uniformly convexity in kernels (generalized definition of graphon) with cut norm
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 349
1
vote
0
answers
164
views
Combinatorial question related to Hankel-type matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $n\geq 2, d$ be positive integers. I would like a lower bound on the largest integer $r$ for which the following property holds:
For any ...
- 980
8
votes
1
answer
1k
views
Looking for another difficult case for the union-closed sets conjecture
[Now crossposted at math.stackexchange.]
Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.
Let $\mathcal{H} \subseteq \mathcal{F}$ be the ...
- 990
3
votes
1
answer
115
views
Lower bound for sets couples such that $A \subset B$ or $B \subset A$ in some union-closed families
Consider a union-closed family of sets $\mathcal{F}$, with $n = \vert\mathcal{F}\vert$ and thus $n \choose 2$ unordered couples of distinct sets $\{A, B\}$, $A,B \in \mathcal{F}$.
In general, the ...
- 990
4
votes
2
answers
557
views
Conjecture about union-closed families of sets - attempt 3
Version 2 of the conjecture was disproved. In this version 3 of the conjecture I am adding a further requirement to obtain from $\mathcal{H}$ a "minimal" family $\mathcal{G}$.
I have already ...
- 990
4
votes
1
answer
442
views
Conjecture about union-closed families of sets - attempt 2
[Update: this one has been disproved, but I have started conjecture attempt 3]
My previous question had an error, I am sorry for that. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/...
- 990
12
votes
2
answers
742
views
Looking for a counterexample for a conjecture about union-closed families of sets
(I have posted a corrected version of this question. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/2 \rceil$.)
I have already asked basically the same question here, but now I have ...
- 990
0
votes
0
answers
52
views
Does "epsilon-regular" equal to "cut distance less than epsilon"?
Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?
$G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
- 349
0
votes
0
answers
49
views
Property of edge-vertex transitive graphs
Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
- 349
3
votes
1
answer
154
views
Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?
Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...
- 349
0
votes
0
answers
39
views
Does this "linear-approximated" version of Graph Counting Lemma hold?
Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
- 349
5
votes
1
answer
219
views
How many base elements can a sunflower-free system have?
A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdős and Rado says that there is a constant $C_t$ such ...
- 18.7k
2
votes
0
answers
99
views
A variant of the social golfer problem and the kirkman schoolgirl problem
I came across the following simple question that seems to be open:
Let $U$ be a set of $n$ elements.
Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $...
1
vote
0
answers
45
views
How small must partitions be to ensure overlapping blocks?
Consider the set family $F$ of all $t$-element subsets of $[n]$, for some positive integer $n$.
Let $P_1$ be a partition of $F$ into $k$ blocks.
Let $P_2 \ne P_1$ be another partition of $F$ into $k$ ...
5
votes
2
answers
600
views
Minimum number of transpositions to make two multiset permutations equal
I think this problem should have a known solution, but I wasn't able to find any reference.
Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.
...
- 990
5
votes
2
answers
657
views
Minimum number of swaps to make multisets elements sums close
This problem was originally posted at math.stackexchange but there is no answer there, even after a (now expiring) bounty.
Choose $4$ multisets of size $n$ with elements $x \in \mathbb{R}$, $0 \le x \...
- 990
1
vote
1
answer
75
views
Lower bound for the sum of the number of vertices of some subgraphs of a directed graph
Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.
Let $C(V_i)$ be the union of ...
- 990
7
votes
1
answer
382
views
Large sets of nearly orthogonal integer vectors
This question is motivated by the Question 5 from the 2017 Asia Pacific Mathematical Olympiad. To paraphrase, the question asks what is the largest cardinality of a set $S \subset \mathbb{Z}^n$ such ...
- 26.9k
8
votes
0
answers
226
views
A variation of necklace splitting
Our problem is the following:
Let $n$ and $k$ be integers.
We are given two (unclasped) necklaces, each with $n$ colored stones: a top necklace which has $k$ colors and a bottom necklace which has 2 ...
- 81
3
votes
2
answers
276
views
Continuous version of the union-closed sets conjecture
Let $F = \{f_1, \ldots, f_n\}$ be a set of continuous functions $f_i: [0,1] \rightarrow [0,1]$,
$i = 1, \ldots, n$, such that $f_i \in F \land f_j \in F \implies \max(f_i,f_j) \in F$.
I would like to ...
- 990
2
votes
1
answer
206
views
Conjecture about families of subsets of $\{1,\ldots,2n+1\}$ of size $n+1$
Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n+1$, $n \ge 1$. The size of $\mathcal{A}$ is therefore $\binom{2n+1}{n+1}$.
For any family $\mathcal{...
- 990
4
votes
0
answers
113
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
- 557
0
votes
0
answers
182
views
Another conjecture about couples of disjoint two-element sets
Let $\{A_1,B_1\},\ldots,\{A_k,B_k\}$ be all the distinct unordered couples of subsets, with $A_i \cap B_i = \emptyset, 1 \le i \le k$, that can formed from a set $\{C_1,\ldots,C_q\}$, $q \le \binom{n}{...
- 990
0
votes
0
answers
115
views
Simpler lower bound for couples of disjoint sets
This is similar to a previous question, but simpler, I suppose.
Let $\mathcal{B}$ be the family of all subsets of $[n]=\{1,2,\ldots,n\} $ of size $2$. Let $\mathcal{F} = \{\mathcal{A}_1,\ldots,\...
- 990
0
votes
0
answers
104
views
Lower bound for couples of disjoint sets in some partitions of the power set
Originally posted on MathStackExchange but without answers.
Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n])...
- 990