Publication

The Probability That a Random Graph is Even‐Decomposable

2025

Abstract

A graph with an even number of edges is called even‐decomposable if there is a sequence such that for each , has an even number of edges and is an independent set in . The study of this property was initiated recently by Versteegen, motivated by connections to a Ramsey‐type problem and questions about graph codes posed by Alon. Resolving a conjecture of Versteegen, we prove that all but an proportion of the ‐vertex graphs with an even number of edges are even‐decomposable. Moreover, answering one of his questions, we determine the order of magnitude of the smallest for which the probability that the random graph is even‐decomposable (conditional on it having an even number of edges) is at least . We also study the following closely related property. A graph is called even‐degenerate if there is an ordering of its vertices such that each has an even number of neighbours in the set . We prove that all but an proportion of the ‐vertex graphs with an even number of edges are even‐degenerate, which is tight up to the implied constant.

Official source

https://infoscience.epfl.ch/entities/publication/69332fda-df5c-49bb-b246-9bc13dfc050c

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2025

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/69332fda-df5c-49bb-b246-9bc13dfc050c

About this result

Related concepts (32)

Vertex (graph theory)

In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Related publications (32)

The Probability That a Random Graph is Even‐Decomposable

Chat with Graph Search

An Optimal Algorithm for Stochastic Vertex Cover

A Unified Framework for Modelling Modern Relational Network Data

The Spectral Graph Wavelet Transform: Fundamental Theory and Fast Computation