Skip to main content

Problems and results on 1-cross-intersecting set pair systems

Zoltán Füredi, András Gyárfás, Zoltán Király
Füredi Z, Gyárfás A, and Király Z (2023). Problems and results on 1-cross-intersecting set pair systems. Combinatorics, Probability and Computing 32, 691–702.

Random interlacement is a factor of i.i.d.

Márton Borbényi, Balázs Ráth, Sándor Rokob

The random interlacement point process (introduced in [47], generalized in [ 50 ]) is a Poisson point process on the space of labeled doubly infinite nearest neighbour trajectories modulo time-shift on a transient graph G. We show that the random interlacement point process on any transient transitive graph G is a factor of i.i.d., i.e., it can be constructed from a family of i.i.d. random variables indexed by vertices of the graph via an equivariant measurable map.

State-controlled epidemic in a game against a novel pathogen

József Garay, Ádám Kun, Zoltán Varga, Manuel Gámez, Ana Belén Castaño-Fernández, Tamás F. Móri

The pandemic reminded us that the pathogen evolution still has a serious effect on human societies. States, however, can prepare themselves for the emergence of a novel pathogen with unknown characteristics by analysing potential scenarios. Game theory offers such an appropriate tool.

Locally common graphs

Endre Csóka, Tamás Hubai, László Lovász

Goodman proved that the sum of the number of trianglesin a graph onnnodes and its complement is at least n3 / 24; in other words, this sum is minimized, asymptotically, by a random graph with edge density 1/2. Erdős conjectured that a similar inequality will hold for K4 in place of K3, but this was disproved by Thomason. But ananalogous statement does hold for some other graphs,which are called common graphs. Characterization ofcommon graphs seems, however, out of reach.

Percolation of worms

Balázs Ráth, Sándor Rokob

We introduce a new correlated percolation model on the d-dimensional lattice Zd called the random length worms model. Assume given a probability distribution on the set of positive integers (the length distribution) and v ∈ (0, ∞) (the intensity parameter). From each site of Zd we start POI(v) independent simple random walks with this length distribution. We investigate the connectivity properties of the set Sv of sites visited by this cloud of random walks.

Upper bounds for the necklace folding problems

Endre Csóka, Zoltán L.Blázsik , Zoltán Király, Dániel Lenger

A necklace can be considered as a cyclic list of n red and n blue beads in an arbitrary order. In the necklace folding problem the goal is to find a large crossing-free matching of pairs of beads of different colors in such a way that there exists a “folding” of the necklace, that is a partition into two contiguous arcs, which splits the beads of any matching edge into different arcs.

Longer-term seeding effects on epidemic processes: a network approach

Gergely Ódor, Domonkos Czifra, Júlia Komjáthy, László Lovász, Márton Karsai
In this paper we touch upon three phenomena observed in real life as well as in simulations; in one case, we state mathematical results about the appearance of the phenomenon on arbitrary graphs (networks) under rather general conditions. We discuss a phenomenon of critical fluctuations, demonstrating that an epidemic can behave very differently even if it runs on the same network, with the same transmission probabilities and started from the same initial seeds.

Multigraph limits, unbounded kernels, and Banach space decorated graphs

Dávid Kunszenti-Kovács, László Lovász, Balázs Szegedy

We present a construction that allows us to define a limit object of Banach space decorated graph sequences in a generalized homomorphism density sense. This general functional analytic framework provides a universal language for various combinatorial limit notions.

Twin-width and generalized coloring numbers

Jan Dreier, Jakub Gajarský, Yiting Jiangc, Patrice Ossona de Mendez, Jean-Florent Raymond
In Twin-width and generalized coloring numbers paper, we prove that a graph \(G\) with no \(K\, s,s\,\)-subgraph and twin-width \(d\) has \(r\)-admissibility and \(r\)-coloring numbers bounded from above by an exponential function of \(r\) and that we can construct graphs achieving such a dependency in \(r\).

Towards solving the 7-in-a-row game

Domonkos Czifra, Endre Csóka, Zsolt Zombori, Géza Makay

Our paper explores the game theoretic value of the 7-in-a-row game. We reduce the problem to solving a finite board game, which we target using Proof Number Search. We present a number of heuristic improvements to Proof Number Search and examine their effect within the context of this particular game. Although our paper does not solve the 7-in-a-row game, our experiments indicate that we have made significant progress towards it.