18.12.2024

Coloring the plane with neural networks

04.12.2024

Milos Stojakovic (University of Novi Sad)

Maker-Breaker games on random boards

28.11.2024

Christoph Spiegel (Zuse-Institut Berlin)

An Unsure Talk on an Un-Schur Problem

21.11.2024

Aldo Kiem (Zuse-Institut Berlin)

Forcing Graphs and Graph Algebra Operators (Part II)

14.11.2024

Aldo Kiem (Zuse-Institut Berlin)

Forcing Graphs and Graph Algebra Operators

21.10.2024
(14:15 - 15:45 in T9/046)

Victor Falgas-Ravry (Umea University)

17.10.2024

Joseph Fehribach (Worcester Polytechnic Institute)

Joseph Fehribach (Worcester Polytechnic Institute)

Families of Kirchhoff Graphs

Abstract: Given a set of n vectors in any vector space over the rationals, suppose that k<n are linear independent. Kirchhoff graphs are vector graphs (graphs whose edges are these vectors), whose cycles represent the dependencies of these vectors and whose vertex cuts are orthogonal to these cycles. This presentation discusses the uniformity of vector 2-connected Kirchhoff graphs, and how graph tiling can generate families of Kirchhoff graphs. These families are composed of prime graphs (those having no Kirchhoff subgraphs), and composite graphs (not prime), all generated by a set of fundamental Kirchhoff graphs (smallest prime Kirchhoff graphs that can generate other prime and composite graphs for our set of vectors).

Victor Falgas-Ravry (Umea University)

1-independent percolation on high dimensional lattices

Abstract: The celebrated Harris-Kesten theorem states that if each edge of the square integer lattice is open with probability p, independently of all other edges, then for p at most 1/2 almost surely all connected components of open edges are finite, while if p>1/2 almos surely there exists a unique infinite connected component of open edges. 
What if one allows the state of an edge (open or closed) to depend on that of neighbouring edges? Could one use such local dependencies to delay the emergence of an infinite component? Such questions lead to fascinating problems at the interface between extremal combinatorics and percolation theory.  In this talk, I will present recent work related to one such decade-old and still open problem of Balister and Bollobás on 1-independent percolation on high-dimensional integer lattices.
Joint work with Vincent Pfenninger (TU Graz)

Aldo Kiem (Zuse-Institut Berlin)

Forcing Graphs and Graph Algebra Operators

Abstract: 

We report on recent progress on Sidorenko's conjecture and the forcing conjecture. Our main observation is that graph operators such as subdivisions, blow-ups or adding disjoint vertices correspond to order-preserving operators on Graph Algebras. This way we easily obtain some new results, in particular that the proper balanced blow-ups of Sidorenko graphs are forcing. This is joint work with Olaf Parczyk and Christoph Spiegel. The talk will survey our results and assume no prerequisites with graph algebras and categories.

Christoph Spiegel (Zuse-Institut Berlin)

An Unsure Talk on an Un-Schur Problem

Abstract: 

Graham, Rödl, and Ruciński originally posed the problem of determining the minimum number of monochromatic Schur triples that must appear in any 2-coloring of the first $n$ integers. This question was subsequently resolved independently by Datskovsky, Schoen, and Robertson and Zeilberger. In this talk we will study a natural anti-Ramsey variant of this question and establish the first non-trivial bounds by proving that the maximum fraction of Schur triples that can be rainbow in a given $3$-coloring of the first $n$ integers is at least $0.4$ and at most $0.66656$. We conjecture the lower bound to be tight. This question is also motivated by a famous analogous problem in graph theory due to Erdős and Sós regarding the maximum number of rainbow triangles in any $3$-coloring of $K_n$, which was settled by Balogh et al. The contents of this talk are joint work with Olaf Parczyk.

Milos Stojakovic (University of Novi Sad)

Maker-Breaker games on random boards

Abstract: 

In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph H). Breaker wins otherwise.
We take a closer look at various Maker-Breaker games played on the edge sets of random graphs.

Christoph Spiegel (Zuse-Institut Berlin)

Coloring the plane with neural networks

Abstract:

We present two novel six-colorings of the Euclidean plane that avoid monochromatic pairs of points at unit distance in five colors and monochromatic pairs at another specified distance din the sixth color. Such colorings have previously been known to exist for 0.41 < √2−1 ≤d ≤1/√5 < 0.45. Our results significantly expand that range to 0.354 ≤d ≤0.657, the first improvement in 30 years. The constructions underlying this notably were derived by formalizing colorings suggested by a custom machine learning approach. This is joint work with Sebastian Pokutta, Konrad Mundiger, and Max Zimmer.