20 votes
Accepted

Does the hypergraph of subgroups determine a group?

In the comments to the question, I notice something which might be an error, or at least is an incomplete response. It is pointed out in the comments that there exist nonisomorphic groups with ...
Keith Kearnes's user avatar
11 votes

Does the hypergraph of subgroups determine a group?

For large prime $p$, there are uncountably many non-isomorphic Tarski monsters of exponent $p$. For these groups $G$, the subgroups lattice consists of basically a partition of $G\smallsetminus\{1\}$...
YCor's user avatar
  • 60.1k
11 votes
Accepted

Singular cardinal $\kappa$ with projective plane such that all edges have cardinality $<\kappa$

The answer is no. Let $\kappa$ be any infinite cardinal, regular or singular, and assume for a contradiction that there is a set $E\subseteq\mathcal P(\kappa)$ satisfying your conditions. I will call ...
bof's user avatar
  • 11.9k
10 votes
Accepted

Chromatic number of a connected Hausdorff space

The answer is no. A space is called resolvable if it contains two disjoint dense subspaces. Clearly $X$ is resolvable if and only if $\chi(X)=2$. Lets prove by induction on $n \geq 2$ that if $\chi(X)...
Ramiro de la Vega's user avatar
9 votes
Accepted

Infinite projective plane with small edges

Update. Here is a new simpler answer that works for all regular $\kappa$, including $\kappa=\omega$. And I have omitted the use of Fodor's lemma, using instead merely the pigeon-hole principle. ...
Joel David Hamkins's user avatar
9 votes
Accepted

Subset of $[\omega]^\omega$ that can be "colored" with $3$, but not $2$ colors

Partition $\omega$ into three infinite subsets $A_0,A_1,A_2$. Let $S$ consists of subsets which intersects precisely two of the $A_i$ at infinitely many elements. It can obviously be $3$-colored. ...
Wojowu's user avatar
  • 27.4k
9 votes

n sets, each is large, the intersection of every three is small, what is the size of the union?

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are ...
domotorp's user avatar
  • 18.4k
9 votes
Accepted

Coloring the uncountable Lebesgue-measurable sets of $\mathbb{R}$

It is continuum. The coloring with continuum many colors is clear (all points may have different color). Assume that we have $\kappa<c$ colors. Consider the Cantor set $K$. All its subsets are ...
Fedor Petrov's user avatar
8 votes
Accepted

Ramsey type theorem

Yes, your conjecture is true. Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f(...
Adam P. Goucher's user avatar
8 votes
Accepted

Simple way to calculate the eigenvalues of a $2 \times 2 \times 2$ tensor

As explained in a previous MO question, there is no unique generalization of the eigenvalue of an $n\times n$ matrix to an $n\times n\times n$ tensor. One approach is to construct a higher-order ...
Carlo Beenakker's user avatar
7 votes

Non-isomorphic hypergraphs on $\omega$

Others have already answered, but I think the following counting argument is worth pointing out: there are $2^{2^{\aleph_0}}$ hypergraphs on $\omega$ (since a hypergraph on $\omega$ is just a ...
Gro-Tsen's user avatar
  • 30k
7 votes
Accepted

Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?

This is essentially done by the Bernstein set construction: if one has $\kappa$ many sets each of size $\kappa$, then order them into ordinal $\kappa$ and recursively choose 2 points from each, so ...
Péter Komjáth's user avatar
7 votes
Accepted

Intersecting subsets of $\{1,\ldots,n\}$

No, there isn't. This is essentially the dual version of the De Bruijn-Erdos theorem if the elements of $\mathcal C$ are the points, and the elements from $\{1,\ldots,n\}$ are the lines. The original ...
domotorp's user avatar
  • 18.4k
7 votes

VC dimension of vector spaces

I will turn my comment above into a self-contained answer. Given a hypergraph $H=(V,E)$ and $X \subseteq V$, we say that $X$ is shattered if for all $X' \subseteq X$, there exists $e \in E$ such that $...
Tony Huynh's user avatar
  • 31.5k
7 votes
Accepted

Discrepancy of random bipartite graphs

The expected degree of a vertex is $k$, which we are keeping fixed as $n\to\infty$. As $n\to\infty$, the vertex degree distribution converges to Poisson($k$). In particular, a proportion roughly $e^{-...
James Martin's user avatar
  • 3,787
6 votes
Accepted

A generalization of Erdős-Ko-Rado theorem

The case $s=1$ is Erdős hypergraph mathcing conjecture from Paul Erdős (1965). A problem on independent $r$-tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95. users.renyi.hu/~...
Thomas Kalinowski's user avatar
6 votes
Accepted

Maximum intersecting set families of $\{1,\ldots,n\}$

The intersecting family in your example has $\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$ members by Sperner's theorem. An example that achieves a larger value would be to take all the subsets of $[n]$ ...
Gjergji Zaimi's user avatar
6 votes

Does the hypergraph of subgroups determine a group?

As @Keith Kearnes says, the negative answer ought to be somewhere in Roland Schmidt's book. Unless I'm mistaken, it suffices to find two non isomorphic groups with isomorphic coset lattices. Indeed, ...
Russ Woodroofe's user avatar
6 votes
Accepted

Injective choice function for "lines" in an infinite cardinal

Observe that $|\mathcal L|\leq\lambda$, since mapping $k$ to the pair of its two smallest elements gives an injection $\mathcal L\to\lambda^2$. Enumerate elements of $\mathcal L$ as $k_\alpha,\alpha&...
Wojowu's user avatar
  • 27.4k
6 votes
Accepted

Independence number of $4$-uniform regular hypergraph

In general no. Partition the vertices onto $n/k$ subsets (I call them classes) of size $k$, where $k$ grows as $n^{2/3}$. Take into your hypergraph all 4-edges with the vertices in the same class. It ...
Fedor Petrov's user avatar
6 votes
Accepted

$1$-factorizability for "complete" finite hypergraphs

This is Baranyai's theorem. Other than in Baranyai's original paper you can also find a cool proof in the article "Uniform hypergraphs" by Brouwer and Schrijver which uses max-flow min-cut.
Gjergji Zaimi's user avatar
6 votes
Accepted

A sequence of cardinal characteristics constructed with hypergraph coloring

The cardinals $\bf k_n$ ($2\le n\lt\omega$) are all equal. Lemma. Let $\kappa$ be an infinite cardinal. Given a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt n$, we can ...
bof's user avatar
  • 11.9k
6 votes
Accepted

Strategies for bounding the spectral norm of a tensor?

I will show, with some non-rigorous steps, that a bound of this form that is valid for arbitrary tensors and useful for sparse tensors (fewer than $n^{k/2}$ nonvanishing entries) does not exist. First ...
Will Sawin's user avatar
  • 137k
6 votes
Accepted

n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$. For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of ...
Kevin P. Costello's user avatar
6 votes
Accepted

Property ${\bf B}$ for families of large sets with small intersection

EDIT: I'll leave my previous answer up for now (at the end of this one), but here's an easier answer that doesn't need assumptions like CH that go beyond ZFC. It's well-known that there is a family of ...
Andreas Blass's user avatar
6 votes
Accepted

How much can we "shrink" intersecting families

Counterexample. Let $X=\{1,2,3,\dots,n\}$ where $n\ge8$, and let $$\mathcal S=\{\{1,2\},\ \{1,3\},\ \{2,3\}\}\cup\{\{2,3,x\}:3\lt x\le n\}\subset\mathcal P(X).$$ Then $\mathcal S$ is an intersecting ...
bof's user avatar
  • 11.9k
5 votes

Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Here is another way of thinking about the problem. Suppose for simplicity that your hypergraph $\mathcal{H}$ has exactly $|V(\mathcal{H})|$ hyperedges (as was mentioned by Dominic, we can immediately ...
Jon Noel's user avatar
  • 761
5 votes
Accepted

Minimal covers in hypergraphs with finite edges

Let $V:=\omega\times\omega$ and $E=\{E_{n,m}:n,m\in\omega\}$ where $$E_{n,m}:=(\{0,\dots,n\}\times\{m\})\cup\{(2n,m+1)\}.$$ It seems that the hypergraph $(V,E)$ has no minimal cover. A simplification ...
Taras Banakh's user avatar
  • 40.9k
5 votes
Accepted

How does the high-dimensional combinatorial Laplacian work?

A lot is lost in the abstract definitions of coboundary maps and cohomology (at least in the finite dimensional case, which I'm restricting to in my answer). But of course, any finite dimensional ...
Russ Woodroofe's user avatar
5 votes
Accepted

Clutters with no maximum-size matchings

Yes, this is possible. For each prime $p$ and $c \in \{0,1, \dots, p-1\}$ let $A_{c,p}=\{c+kp \mid k \in \mathbb{Z}\}$. Clearly, the set of all $A_{c,p}$ is a clutter $\mathcal C$ with ground set $\...
Tony Huynh's user avatar
  • 31.5k

Only top scored, non community-wiki answers of a minimum length are eligible