Zobrazeno 1 - 10
of 735
pro vyhledávání: '"Kwan, Matthew"'
Publikováno v:
Comptes Rendus. Mathématique, Vol 361, Iss G2, Pp 565-575 (2023)
We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt{3}/2-3}(1+\sqrt{3})/2$. This is the final piece of the puzzle fo
Externí odkaz:
https://doaj.org/article/167138ee6c0a42da98a433d2544332d4
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification is provided by a classical theorem of Babai, Erd\H
Externí odkaz:
http://arxiv.org/abs/2410.06095
One of the foundational theorems of extremal graph theory is Dirac's theorem, which says that if an n-vertex graph G has minimum degree at least n/2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by S\'arkoz
Externí odkaz:
http://arxiv.org/abs/2408.09589
Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state $|\psi\rangle$. Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform $|\psi\
Externí odkaz:
http://arxiv.org/abs/2406.03335
In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erd\H{o}s-R\'enyi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthe
Externí odkaz:
http://arxiv.org/abs/2402.05851
Autor:
Kwan, Matthew, Sauermann, Lisa
Consider a quadratic polynomial $Q(\xi_{1},\dots,\xi_{n})$ of independent Rademacher random variables $\xi_{1},\dots,\xi_{n}$. To what extent can $Q(\xi_{1},\dots,\xi_{n})$ concentrate on a single value? This quadratic version of the classical Little
Externí odkaz:
http://arxiv.org/abs/2312.13826
Autor:
Kwan, Matthew, Wigderson, Yuval
The inertia bound and ratio bound (also known as the Cvetkovi\'c bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number $\alpha(G)$ of a graph $G$ in terms of spectral inform
Externí odkaz:
http://arxiv.org/abs/2312.04925
Autor:
Koval, Illya, Kwan, Matthew
As a discrete analogue of Kac's celebrated question on "hearing the shape of a drum", and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency
Externí odkaz:
http://arxiv.org/abs/2309.09788
An ordered $r$-matching is an $r$-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of $r$-dimensional orders. The theory of ordered 2-matchings is well-developed and has con
Externí odkaz:
http://arxiv.org/abs/2308.12268
There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a
Externí odkaz:
http://arxiv.org/abs/2307.06453